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即可。
//队列元素个数 public int getSize(){ return size; }
4.循环队列
4.1 概念
用数组来实现，是一种队列数据结构，它通过维护两个指针front和rear，使得在队列头和队列尾之间形成一个环状的结构。当队列满时，新元素无法插入队列，但是可以从队头删除元素来腾出空间。与普通队列相比，循环队列可以更有效地利用存储空间。另外，循环队列还有一些特殊操作，如队列的遍历和求队列长度，它们需要特殊的算法来实现。
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; } }
