Collection与数据结构 Stack与Queue(二):队列与Queue

1. 队列

1.1 概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）.
在这里插入图片描述
这样的数据结构有些像我们平时在食堂排队打饭的操作.

1.2 队列的使用

在Java中,Queue是一个接口,底层是通过链表来实现的.所以在实例化的时候,必须用LinkedList来实例化.
在这里插入图片描述

方法	功能
boolean oﬀer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

offer和poll操作的时间复杂度都是O(1),所以在使用单向链表实现队列的时候,必须使用头插尾插.如果说是尾删头插的话,删掉的时候不知道该结点的pre是谁(因为是单向链表),所以要重新遍历寻找最后一个结点,时间复杂度就不是O(1).

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);                  // 从队尾入队列System.out.println(q.size());System.out.println(q.peek());  // 获取队头元素q.poll();System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

1.3 队列的模拟实现

我们根据队列底层的逻辑:使用LinkedList来实现队列.

public class MyQueue {public static class ListNode{ListNode next;ListNode pre;int val;public ListNode(int val) {this.val = val;}}ListNode first;ListNode last;int size = 0;/*** 入队列,在双向链表的尾部插入新结点* @param e*/public void offer (int e){ListNode listNode = new ListNode(e);if (first == null){first = listNode;last = listNode;}else {listNode.pre = last;last.next = listNode;last = listNode;}size++;}/*** 出队列,在链表头部删除结点* @return*/public int poll(){int value = 0;if (first == null){return -1;} else if (first == last) {value = first.val;//需要先把value记录下来,以便最后返回first = null;last = null;//return value;//不可以直接返回first.val,否者空指针异常}else {value = first.val;first = first.next;first.pre.next = null;first.pre = null;//return value;}size --;//在返回之前size--return value;}/*** 返回队头元素* @return*/public int peek(){if (first == null){return -1;}return first.val;}/*** 获取队列大小* @return*/public int size(){return this.size;}/*** 判断队列是否为空* @return*/public boolean isEmpty(){return size == 0;}
}

1.4 环形队列

在实际中,我们经常用的一种队列还有一种,叫做循环队列,环形队列通常由数组实现.
在这里插入图片描述
既然是环形队列,所以我们在存放元素的时候,就要按循环下标的方式来添加元素,数组下标循环公式:
(当前位置+偏移量)%数组大小.
eg:
区分空与满的问题:
在一个队列中,一定会有队头和队尾,在队列空的时候,队列头和尾指向同一位置:
在这里插入图片描述
在队列满的时候,头和尾也会指向同一位置:

如果按上述的方法,我们就没有办法区别队列是空还是满了,那么我们提供以下解决方案:

通过添加size属性
保留一个位置(牺牲空间法)
使用标记

在下面,我们只以第二种方法为例:我们令头为front,尾为rear
在这里插入图片描述
在满的时候,我们通过把最后一个位置空出来,以front = (rear+1)%array.length来表示队列满.
下面我们来通过上述方式设计循环队列:

OJ链接

class MyCircularQueue {public int front;//队头public int rear;//队尾public int[] elem;public MyCircularQueue(int k) {front = 0;rear = 0;elem = new int[k+1];//使用牺牲空间法来区分满和空,初始化空间的时候就要多一个空间}public boolean enQueue(int value) {if(isFull()){return false;//队列为满,返回false}else{elem[rear] = value;rear = (rear+1)%elem.length;}return true;}public boolean deQueue() {if(front == rear){return false;//队列为空,删除失败}else{elem[front] = 0;front = (front+1)%elem.length;}return true;}public int Front() {if(rear == front){return -1;}else{return elem[front];}}public int Rear() {if(rear == front){return -1;}else{return rear == 0? elem[elem.length-1]:elem[rear-1];}//分两种情况,一种是rear为0,一种是不为0的时候,为0返回数组的最后一个元素,否者返回rear指向的前一个元素}//队尾放的最后一个元素总是比rear指针向前一个位置,因为在插入操作的时候,最后进行了rear = (rear+1)%elem.length操作public boolean isEmpty() {if(rear == front){return true;//头和尾重合的时候,就是空}else{return false;}}public boolean isFull() {if(front == (rear+1)%elem.length){return true;//中间空出一个空间的时候,就是满}return false;}}
}

2. 双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
在这里插入图片描述
Deque是一个接口,必须使用LinkedList实例化对象.

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

3. 队列与栈的综合

3.1 用栈实现队列

在用栈实现队列的时候,核心思想把握住一句话:出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素.
在这里插入图片描述

OJ链接

class MyQueue2 {//需要用两个栈来实现一个队列Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue2() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);//入队列的时候就入第一个栈就可以}public int pop() {int value = 0;if (stack2.empty()){//如果stack2为空的时候,就把stack1的元素全部倒到2中//是因为出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素while(!stack1.empty()){stack2.push(stack1.pop());}value = stack2.peek();stack2.pop();//出2的栈顶元素}else {//如果不为空,直接出栈顶元素value = stack2.peek();stack2.pop();}return value;}public int peek() {int value = 0;if (stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}value = stack2.peek();}else {value = stack2.peek();}return value;//和pop原理一样,只不过没有元素出栈}public boolean empty() {//两个栈都为空的时候,队列为空if (stack1.empty() && stack2.empty()){return true;}else {return false;}}}

3.2 用队列实现栈

这道题的核心是:队列中最后一个元素对应栈顶的元素,所以要让队尾的元素露出来.
在这里插入图片描述
OJ链接

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;//使用两个队列来完成栈的实现public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if (empty()){//空就往任意一个队列中添加queue1.offer(x);return;//记得返回}if (!queue1.isEmpty()){//谁不为空,就往谁添加queue1.offer(x);}else {queue2.offer(x);}}public int pop() {if (empty()){return -1;}if (queue1.isEmpty()){while(queue2.size() != 1){//poll到队列中只有1个元素,目的是让队列中的元素与栈顶元素对应起来queue1.offer(queue2.poll());}return queue2.poll();//弹出只剩一个元素的队列}else {while(queue1.size() != 1){queue2.offer(queue1.poll());}return queue1.poll();}}public int top() {if (empty()){return -1;}int value = 0;//利用vlaue保存peek的值if (queue1.isEmpty()){while(queue2.size() != 1){queue1.offer(queue2.poll());}value = queue2.peek();queue1.offer(queue2.poll());//先peek保存,再poll到另一个队列中return value;}else {while(queue1.size() != 1){queue2.offer(queue1.poll());}value = queue1.peek();queue2.offer(queue1.poll());return value;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}}