1.概念
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队（Head/Front），队列可以通过数组和链表两种方式来实现。
队列的基本操作：入队（Offer）、出队（Poll）和获取队头元素（Peek）。其中，入队操作将元素放到队尾，出队操作将对头元素移除并返回其值，获取队头元素则是获取栈顶元素的值但是不移除队头元素。
另外，队列还有一些其他的常用操作，如：判断队列是否为空（IsEmpty）、获取队列中元素的个数（Size）、清空队列中的所有元素（Clear）等。
2.常用的队列方法
2.1 方法
| 方法 | 功能 |
|---|---|
| offer() | 入队列 |
| poll() | 出队列，队列为空，抛出NoSuchElementException异常 |
| peek() | 获得队头元素，抛出NoSuchElementException异常 |
| size() | 获得队列元素个数 |
| isEmpty() | 检测队列是否为空 |
2.2 代码
public static void main(String[] args) {
Queue<Character> queue = new LinkedList<>();
queue.offer('A');//A
queue.offer('B');//B A
queue.offer('C');//C B A
System.out.println(queue.poll());//A
System.out.println(queue.peek());//B
System.out.println(queue.poll());//B
queue.offer('D');//D C
System.out.println(queue.size());//2
System.out.println(queue.isEmpty());//fasle
}
注意：
队列操作的poll(),peek()的执行条件是队列不为空。
3.自己实现队列
自己实现队列可以使用线性结构和链式结构实现，具体使用哪种结构取决于实际需求和场景。
顺序结构的优点是实现简单，易于理解和维护，内存利用率高，适用于元素个数固定、连续存储空间较大时的情况。但是，在元素插入和删除时需要移动大量元素，所以当队列操作频繁时，效率可能较低。
链式结构的优点是插入和删除操作时只需修改指针，效率较高，适用于元素个数不确定、动态增长的情况。但是，链式结构需要更多的内存空间来存储指针，且代码实现相对复杂，对于较小的队列可能会浪费一些内存空间。
因此，根据具体需求和场景来选择队列的实现方式。队列可以使用顺序结构和链式结构来实现，具体使用哪种结构取决于实际需求和场景。
顺序结构的优点是实现简单，易于理解和维护，内存利用率高，适用于元素个数固定、连续存储空间较大时的情况。但是，在元素插入和删除时需要移动大量元素，所以当队列操作频繁时，效率可能较低。
链式结构的优点是插入和删除操作时只需修改指针，效率较高，适用于元素个数不确定、动态增长的情况。但是，链式结构需要更多的内存空间来存储指针，且代码实现相对复杂，对于较小的队列可能会浪费一些内存空间。
因此，根据具体需求和场景来选择队列的实现方式。
3.1 构造MyQueue
我们可以使用链表构建队列，链表是节点组成，所以我们创建节点，用next记录下一个节点，prev记录前一个节点。
public class MyQueue {
public int val;
public MyQueue next;
public MyQueue prev;
public MyQueue first;//队头
public MyQueue last;//队尾
public int size;//元素个数
public MyQueue(){}
public MyQueue(int val){
this.val = val;
}
}
3.2 入队列offer()
入队列的时候，如果队列大小为0，则队头队尾都等于这个节点。不为0，则直接队尾插入这个节点。
//入队列
public void offer(int val){
MyQueue myQueue = new MyQueue(val);
if(size == 0){
first = myQueue;
last = myQueue;
size++;
return;
}
last.next = myQueue;
myQueue.prev = last;
last = last.next;
size++;
}
3.3 出队列poll()
出队列的时候，判断队列大小是否为0，为零则抛出异常，不为0则删除队头元素，并返回。
//出队列
public int poll(){
if(first == null){
throw new NoSuchElementException();
}
MyQueue myQueue = first;
if(first == last){
last = null;
first = null;
}else {
first = first.next;
first.prev = null;
}
size--;
return myQueue.val;
}
3.4 获得队头peek()
获得队头元素，若队列为空，直接抛出异常，反之直接返回队头元素。
//获得队头元素
public int peek(){
if(first == null){
throw new NoSuchElementException();
}
return first.val;
}
3.5 是否为空isEmpty()
判断队列是否为空，就是判断size是否为0。
//是否为空队列
public boolean isEmpty(){
return size == 0;
}
3.6 获得队列大小size()
获得队列大小，直接返回size即可。文章来源：https://www.toymoban.com/news/detail-469142.html
//队列元素个数
public int getSize(){
return size;
}
4.循环队列
4.1 概念
用数组来实现，是一种队列数据结构，它通过维护两个指针front和rear，使得在队列头和队列尾之间形成一个环状的结构。当队列满时，新元素无法插入队列，但是可以从队头删除元素来腾出空间。与普通队列相比，循环队列可以更有效地利用存储空间。另外，循环队列还有一些特殊操作，如队列的遍历和求队列长度，它们需要特殊的算法来实现。文章来源地址https://www.toymoban.com/news/detail-469142.html
4.2 解析
- MyCircularQueue类有三个私有成员变量：elem表示循环队列的存储数组，front、rear分别表示队头和队尾的位置。
- 构造函数MyCircularQueue(int capacity)用于创建一个容量为k的循环队列。在构造函数中，初始化存储数组elem、队头front、队尾rear。
- enQueue方法用于向队列中添加元素element。如果队列已满，则返回false；否则将元素添加到队尾，并将队尾指针rear移动到下一个位置，同时更新队列大小size。注意，队列满时，rear可能会回到数组的开始位置，这时可以用取模运算实现。rear = (rear + 1) % elem.length;
- deQueue()方法用于从队列中删除元素，并返回被删除的元素。如果队列为空，则抛出NoSuchElementException。否则将队头元素删除，并将队头指针front移动到下一个位置。同样地，如果队头指针front回到数组的开始位置，则也需要用取模运算实现。frond = (frond + 1) % elem.length;
peek()方法用于返回队头元素，但不删除它。如果队列为空，则抛出NoSuchElementException。
4.3 如何判断队列满
- 通过添加 size 属性记录（当size等于队列长度，满）
- 保留一个位置（当队尾加1 mod 队列长度等于队头，队列满）
- 使用标记（在循环队列中添加一个标记 flag，用来区分队列空和队列满的状态。）
4.4 代码（保留一个位置实现）
class MyCircularQueue {
private int[] elem;
private int rear;
private int frond;
public MyCircularQueue(int k) {
this.elem = new int[k];
}
public boolean enQueue(int value) {
if(isFull()){
return false;
}
elem[rear] = value;
rear = (rear + 1) % elem.length;
return true;
}
public boolean deQueue() {
if(isEmpty()){
return false;
}
frond = (frond + 1) % elem.length;
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
return elem[frond];
}
public int Rear() {
if(isEmpty()){
return -1;
}
return elem[rear];
}
public boolean isEmpty() {
return frond == rear;
}
public boolean isFull() {
return (rear + 1) % elem.length == frond;
}
}
到了这里，关于Queue 队列的实现与应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
