数据结构*队列

队列

什么是队列

是一种线性的数据结构，和栈不同，队列遵循“先进先出”的原则。如下图所示：

在集合框架中我们可以看到LinkedList类继承了Queue类（队列）。

普通队列（Queue）

Queue中的方法

方法	功能
add()	入队列
offer()	入队列
remove()	出队列
poll()	出队列
element()	获取队头元素
peek()	获取队头元素

add()和offer()都是添加数据、remove()和poll()都是删除数据、element()和peek()都是获取队列头部元素信息这些方法有什么区别呢？（下面都是豆包总结的，可以参考一下）


总结：
add()、remove()、element()方法对于满和空队列的时候会抛出异常。而offer()、poll()、peek()方法不会，它们更具有灵活性。我们则常用offer()、poll()、peek()方法来对队列进行操作。

其他方法

在Collection接口中还有size()、isEmpty()等其他方法我们可以使用。

模拟实现队列

用链表实现

public class MyQueue {static class ListNode{private final int val;private ListNode next;private ListNode prev;private ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;/*** 入队操作：尾插法* @param val*/public void offer(int val) {ListNode node = new ListNode(val);if(empty()) {first = last = node;}last.next = node;node.prev = last;last = last.next;}/*** 出队操作：删除头节点* @return*/public int poll() {if(empty()) {return -1;}int value = first.val;if(first == last) {first = last = null;return value;}else {first = first.next;first.prev = null;return first.val;}}/*** 获得头节点不删除* @return*/public int peek() {if(empty()) {return -1;}return first.val;}/*** 获得有效数据* @return*/public int size() {ListNode cur = first;int usedSize = 0;while (cur != null) {usedSize++;cur = cur.next;}return usedSize;}/*** 判断是否为空* @return*/public boolean empty() {return first == null;}
}

循环队列

对于普通的数组来说，再用队列的思想时，很容易造成数组下标越界等问题。这时候我们可以将数组循环起来。如下图所示：

这时候就产生问题了。

1、rear 和 front 如何访问从最后一个下标访问到0下标？

由于循环，可以将（下标+偏移量）/ length。这里的偏移量为1（每次只走一格）。也就是对于有关下标的需要用(rear+1) / len 和 (front+1) / len。

2、如何判断数组是否满了。

解决的方法有：
1、使用size个数，当等于数组长度，则说明满了；
2、用一个boolean值来标记是否满了。初始时，front == rear，isFull == false。当每次添加数据时判断 front == rear，当相等时isFull == true，说明满了。在删除数据时，不可能满了，将isFull == false；
3、留出一个空间来判断是否满了。当rear的下一个是front的时候，就说明是满的。

在入队时，放一个元素，rear往后走，一开始 rear == front。当rear的下一个是front的时候，也就只存放了 len - 1个数据。

代码展示：

采用预留空间的方法

class MyCircularQueue {public int[] elem;int rear = 0;int front = 0;public MyCircularQueue(int k) {elem = new int[k];//由于采用预留空间的方法，使得实际数据只有k - 1个}/*** 向循环列队中插入一个元素* @param value* @return*/public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;//rear指向预留的空间rear = (rear + 1) % elem.length;//这样rear下标始终控制在合理范围return true;}/*** 删除循环列队中的一个元素* 由于队列是先进先出的，所以删除的是front下标的元素* @return*/public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % elem.length;//这样front下标始终控制在合理范围return true;}/*** 从队首获取元素* @return*/public int Front() {if(isEmpty()) {return -1;}return elem[front];}/*** 获取队尾元素* @return*/public int Rear() {if(isEmpty()) {return -1;}//rear并不是队尾元素，rear的上一个才是。//rear - 1就得到了，但当rear为0时，rear - 1 就会越界，这时候就要if判断了if(rear == 0) {return elem[elem.length - 1];}return elem[rear - 1];}/*** 判断循环队列是否为空* @return*/public boolean isEmpty() {return rear == front;}/*** 判断循环队列是否满了* @return*/public boolean isFull() {return (rear + 1) % elem.length == front;//rear为预留空间，下一个指向front}
}

双端队列（Deque）

它是一种特殊的队列，允许在队列的两端进行元素的插入与删除操作。这意味着既能在队列头部添加或移除元素，也能在队列尾部添加或移除元素。一般创建ArrayDeque、LinkedList这两个类的对象。
ArrayDeque是用数组实现的双端队列，LinkedList是用双向链表实现的双端队列。其中的优缺点和顺序表与链表的优缺点类似。
对于双端队列的方法是在Queue方法名中后面加上Last、First（例如：offerFirst()、pollFirst()、peekLast()等，但要注意的是：对于抛异常的获取元素并不是用的element()而是getFirst()和getLast() ）。

代码展示：

public static void test1() {Deque<Integer> deque = new ArrayDeque<>();deque.offerFirst(1);deque.offerFirst(10);deque.offerFirst(100);deque.offerFirst(1000);deque.offerLast(2);deque.offerLast(20);System.out.println(deque);deque.pollFirst();//出队列的头元素：1000System.out.println(deque);deque.pollLast();//出队列的尾元素：20System.out.println(deque);System.out.println(deque.peekFirst());System.out.println(deque.peekLast());System.out.println(deque);
}

public static void test2() {Deque<Integer> deque = new LinkedList<>();deque.offerFirst(1);deque.offerFirst(10);deque.offerFirst(100);deque.offerFirst(1000);deque.offerLast(2);deque.offerLast(20);System.out.println(deque);deque.pollFirst();//出队列的头元素：1000System.out.println(deque);deque.pollLast();//出队列的尾元素：20System.out.println(deque);System.out.println(deque.peekFirst());System.out.println(deque.peekLast());System.out.println(deque);
}

ArrayDeque、LinkedList两个实现的效果是一样的。

用队列实现栈

首先一个队列肯定是实现不了栈的，两个运行逻辑都不一样，一个先进先出，一个先进后出。此时需要两个队列来实现栈。

对于出"栈"方法：将其余数据依次放入空队列中（对非空队列进行出"栈"操作）。

对于入"栈"，只需要将元素放入非空的队列中即可。

对于拿到"栈"顶的元素，前面和出"栈"一样：将其余数据依次放入空队列中，直接输出剩下的元素，在将剩下的元素放到另一个队列中。

代码展示：

import java.util.LinkedList;
import java.util.Queue;class MyStack {public Queue<Integer> queue1;public Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}/*** 入栈* @param x*/public void push(int x) {if(!queue1.isEmpty()) {queue1.offer(x);}else if(!queue2.isEmpty()) {queue2.offer(x);}else {queue1.offer(x);}}/*** 出栈* @return*/public int pop() {//当都为空时，说明"栈"中没有元素if(empty()) {return -1;}//对于非空队列进行操作if(!queue1.isEmpty()) {int size = queue1.size();//将其余元素移到空队列while (size != 1) {queue2.offer(queue1.poll());size--;}//返回队列中仅有的元素，并删除return queue1.poll();}else {//下面是!queue2.isEmpty()的情况int size = queue2.size();while (size != 1) {queue1.offer(queue2.poll());size--;}return queue2.poll();}}/*** 获取"栈"顶元素* @return*/public int top() {//判断栈是否为空if(empty()) {return -1;}if(!queue1.isEmpty()) {int size = queue1.size();while (size != 1) {queue2.offer(queue1.poll());size--;}//上述操作和出栈一样，下面只需输出元素，并不删除数据int value = queue1.poll();queue2.offer(value);//将元素入队，避免丢失return value;}else {int size = queue2.size();while (size != 1) {queue1.offer(queue2.poll());size--;}int value = queue2.poll();queue1.offer(value);return value;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();//当队列都为空时，说明"栈"为空}
}

用栈实现队列

同样的，也是需要两个栈的。

对于出"队列"，只需要将非空栈（stack1）中的元素全部放到另一个栈中（stack2），再从stack2中出元素。

当stack2为空，则将stack1全部放入stack2中。

对于入"队列"来说，只需要将元素放到stack1中。

代码展示：

import java.util.Stack;class MyQueue {public Stack<Integer> stack1;public 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.empty()) {while (!stack1.empty()) {//需要将stack1中的元素 全部 放到stack2中（用while循环）stack2.push(stack1.pop());}}return stack2.pop();//stack2栈中有元素，直接调用方法}public int peek() {if(empty()) {return -1;}if (stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}