一、什么是队列？
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点， 进行插入操作的一端称为 队尾，进行删除操作的一端称为队头 。
二、队列的使用
在Java中，Queue是个接口，底层是通过链表实现的。
| 方法 | 功能 |
boolean offer(E e) |
入队列 |
E poll() |
出队列 |
peek() |
获取队头元素 |
int size() |
获取队列中有效元素个数 |
boolean isEmpty() |
检测队列是否为空 |
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
三、队列的模拟实现（单链表实现、用数组实现循环队列）
单链表模拟实现队列：
在java当中的队列，其实底层是使用双向链表开实现队列的。
在这里我使用单向链表来实现。但是如果这是一个单纯的单链表，那么会有以下两个问题：
1）从头入队：入队的时间复杂度为O(1),出队的时间复杂度为O(N)。
2) 从尾入队：入队的时间复杂度为O(N)，出队的时间复杂度为O(1)。
但是我们可以给单链表新增一个tail 引用，永远指向尾节点。入队的时候，从tail 后面进行插入，相当于尾插法；出队的时候，从链表的头出队，相当于删除链表的头结点。
代码如下：
static class ListNode{ int val; ListNode next; public ListNode(int val){ this.val = val; } } public ListNode head; public ListNode tail; public int usedSize; public void offer(int val){ ListNode node = new ListNode(val); if (head == null){ head = node; tail = node; }else { tail.next = node; tail = node; } usedSize++; } public int poll(){ if (head == null){ return -1; } int ret = head.val; head = head.next; if (head == null){ tail = null; } usedSize--; return ret; } public int peek(){ if (head == null)return -1; return head.val; } public boolean isEmpty(){ return usedSize == 0; } public int getUsedSize(){ return usedSize; }
用数组实现循环队列：
在一些场景时我们会用到循环队列，比如在使用生产者消费者模型的时候就会使用循环队列。
关键点是如何实现循环，代码如下：
rear = (rear+1) % elem.length; front = (front+1)%elem.length;
完整代码如下：
class MyCircularQueue { public int[] elem; public int front;//头部 public int rear;//尾部 public MyCircularQueue(int k) { 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; 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; } }
四、双端队列
双端队列（ deque ）是指允许两端都可以进行入队和出队操作的队列， deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。Deque 是一个接口，使用时必须创建 LinkedList 的对象。
这种数据结构，在实际开发中使用的并不是非常多。
五、用队列实现栈
用队列实现栈：完整代码如下
class MyStack { private Queue<Integer> queue1; private Queue<Integer> queue2; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x) { if (!queue1.isEmpty()){ queue1.offer(x); }else if (!queue2.isEmpty()){ queue2.offer(x); }else { queue1.offer(x); } } public int pop() { if (empty())return -1; if (!queue1.isEmpty()){ int len1 = queue1.size(); for (int i = 0; i < len1 -1; i++) { queue2.offer(queue1.poll()); } return queue1.poll(); }else { int len2 = queue2.size(); for (int i = 0; i < len2-1; i++) { queue1.offer(queue2.poll()); } return queue2.poll(); } } public int top() { if (empty())return -1; if (!queue1.isEmpty()){ int len1 = queue1.size(); int tmp = -1; for (int i = 0; i < len1; i++) { tmp = queue1.poll(); queue2.offer(tmp); } return tmp; }else { int len2 = queue2.size(); int tmp = -1; for (int i = 0; i < len2; i++) { tmp = queue2.poll(); queue2.offer(tmp); } return tmp; } } public boolean empty() { return queue1.isEmpty() && queue2.isEmpty(); } }
六、用栈实现队列
用栈实现队列：完整代码如下
class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void push(int x) { stack1.push(x); } public int pop() { if (empty())return -1; if (!stack2.isEmpty()){ return stack2.pop(); }else { while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.pop(); } } public int peek() { if (empty())return -1; if (!stack2.isEmpty()){ return stack2.peek(); }else { while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.peek(); } } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }
