目录
队列概念
方法
队列模拟实现
链表实现队列
入队列
出队列
获取队头元素
数组实现队列
入队列
出队列
返回头队列
返回尾队列
完整代码
双链表实现队列
数组实现队列（设计循环队列）
队列概念
队列：只允许在一段进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出的特点，就像是排队一样，先排队的先出去。
入队列：进行插入操作的一段称为队尾。
出队列：进行删除操作的一段称为队头。
方法
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
队列模拟实现
队列可以通过链表和数组实现
链表实现队列
这里实现队列采用的双向链表，所以定义一些基本变量如下，useSize记录队列中数据个数。
java">public class MyQueue {//双向链表实现static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode first = null; //队头public ListNode last = null; //队尾public int useSize = 0;
}入队列
offer方法
在往链表中放数据时，要考虑链表是否为空，当链表为空，队头和队尾都等于这个数据。
这时可以写一个isEmpty方法来判断，对于判断是否为空的条件，可以看useSize是否为0，也可以时first是否为0。
java"> public boolean isEmpty(){return useSize == 0;//return first == 0;}当链表不为空时，这时实现的是尾插，所以offer方法完整部分为：
java"> public void offer(int val){ListNode node = new ListNode(val);if(isEmpty()){first = last = node;}else{last.next = node;node.prev = last;last = last.next;}useSize++;}出队列
poll方法
出队列时也要考虑是否为空，用链表实现出队列要做的是把头节点往后挪一个位置。
当链表中只有一个节点，就没有必要再空置前一个结点了。
java"> public int poll(){if(isEmpty()){return -1;}int val = first.val;first = first.next;//一个节点，就没必要再置空前一个节点if(first != null){first.prev = null;}useSize--;return val;}
获取队头元素
peek方法
获取队头元素思路很清晰，只要返回first对应的值即可。也要进行是否为空的判断。
java"> public int peek(){if(isEmpty()){return -1;}return first.val;}数组实现队列
这里主要做得是：设计循环队列，我们可以把循环队列设想成一个环，在一个有限的环里实现队列。设定front为头位置，rear为尾位置。
判断数组是否为满有三种方法：
- 定义size
- 添加标记 定义boolean类型
- 浪费一个空间，即：确保一个空间里面不放元素，判断：rear下一个是不是front
这里我们采用的是最后一种方法：浪费一个空间。
不过还要解决一个问题： rear或者front 下标如何从 7位置 到 0位置？
对应的解决方案为：（rear +1）% 数组长度，front同理。
因为采用数组来实现循环队列，所以第一步是定义基础变量。
java">class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {this.elem = new int[k+1];}
}因为需要浪费一个位置，所以申请 k+1个位置。
入队列
enQueue方法
主要的思路是把数据放到rear位置，然后rear后移一个位置。
不过要考虑数组是否为满，这是可以写一个isFull方法。
判断的条件是：rear 的下一个位置 是否是 front。
java"> public boolean isFull() {return (rear+1) % elem.length == front;}enQueue方法完整为下：
java"> //入队列public boolean enQueue(int value) {if(isFull()){return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}注意：rear后移一个位置不是rear++，而是(rear+1) % elem.length。
出队列
deQueue方法
出队列的主要思路是：把front后移一个位置，前面的数据会被后面逐渐放进去的rear覆盖。
此时还要考虑数组是否为空，写一个isEmpty方法。判断条件是：front和rear是否相等。
java"> public boolean isEmpty() {return front == rear;}出队列的完整代码为：
java"> //出队列public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;return true;}返回头队列
Front方法
- 判断是否为空
- 返回front位置的数据
java"> //返回头队列public int Front() {if(isEmpty()){return -1;}return elem[front];}返回尾队列
Rear方法
- 判断是否为空
- 判断rear 是否为 0
之所以要判断rear == 0，是因为当rear == 0时，返回的是elem.length - 1，而rear ！= 0时，返回rear - 1；
完整代码为：
java"> public int Rear() {if(isEmpty()){return -1;}int index = (rear == 0) ? elem.length - 1 : rear-1;return elem[index];}完整代码
双链表实现队列
java">public class MyQueue {//双向链表实现static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode first = null;public ListNode last = null;public int useSize = 0;public void offer(int val){ListNode node = new ListNode(val);if(isEmpty()){first = last = node;}else{last.next = node;node.prev = last;last = last.next;}useSize++;}public int poll(){if(isEmpty()){return -1;}int val = first.val;first = first.next;//一个节点，就没必要再置空前一个节点if(first != null){first.prev = null;}useSize--;return val;}public int peek(){if(isEmpty()){return -1;}return first.val;}public boolean isEmpty(){return useSize == 0;//return first == 0;}
}数组实现队列（设计循环队列）
java">class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {this.elem = new int[k+1];}//入队列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;}front = (front+1) % elem.length;return true;}//返回头队列public int Front() {if(isEmpty()){return -1;}return elem[front];}//返回尾队列public int Rear() {if(isEmpty()){return -1;}int index = (rear == 0) ? elem.length - 1 : rear-1;return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {return (rear+1) % elem.length == front;}
}
