一、 队列(Queue)

1.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

队列和栈的区别：队列是先进先出（队尾进，队头出），栈是先进后出

---

1.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的

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

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口   Queue<Integer> q = new LinkedList<>();

 Queue 的方法有以下六种，每两种都是一样的功能（添| 删 |查），但是还是存在一定的差异

差异：

（1）add，remove，element都是Collection的通用方法

        offer，poll，peek是队列专有的方法

（2）Collection实现的通用方法中 有些情况会报异常

        而队列专有的方法中 不会报异常 

        eg：如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false

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 队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。同学们思考下：队列的实现使用顺序结构还是链式结构好？

（1）单链表模拟实现：为了保证时间复杂度为O（1）

肯定不能从队头进，队尾出，这样删尾节点时间复杂度就为O（N）

所以采用从队尾进，队头出，但是这个时候就需要last指针来指向队尾 ，这样的尾插，头删才满足条件

（2） 双向链表模拟实现：无论从队头进，队尾出，还是从队尾进，队头出，都是可以的

双向链表就是神一般的存在 LinkedList：可以当作双向链表，栈，队列

 （3）数组模拟实现：可以用来实现循环队列，如果实现普通队列，就会存在删除元素的前面（front指针的前面）无法再进行添加元素

下面这个代码是由双向链表(尾插，头删）实现队列：

import java.security.PublicKey;
//双向链表(尾插，头删）实现队列
public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//入队public void offer(int val) {ListNode node = new ListNode(val);//尾插if(head == null) {head = last = node;} else {last.next = node;node.prev = last;last = node;}}//出队public int poll() {//空队列if(head == null) {return -1;}//一个节点int val = -1;if (head.next == null) {val = head.val;head = null;last = null;return val;}val = head.val;head = head.next;head.prev = null;return val;}//判断是否为空public boolean empty() {return head == null;}public int peek() {if (head == null) {return -1;}return head.val;}
}

---

1.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现

 数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

 2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

如何区分空与满

1. 通过添加 size 计数的方式来判断（这个较简单）

2. 保留一个位置，浪费空间来表示满（这个用的较多）

3. 使用标记boolean flg （开始前在同一位置标记为false，再次相遇标记为true）（这个也比较简单）

设计循环队列

class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem = new int[k + 1];// 浪费一个空间，也就是需要多开一个元素的空间}// 入队操作public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;// 注意点1：不可直接rear+1return true;}// 删除队头元素（空不空 + front移动）public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length; // 注意点2：不可直接front+1return true;}// 得到队头元素 不删除public int Front() {if (isEmpty()) {return -1;}return elem[front];}// 得到队尾元素 不删除public int Rear() {if (isEmpty()) {return -1;}// rear=0说明刚刚走过一圈以上，那么队尾就为elem.length-1// rear!=0说明还没到跨越的位置，直接-1即可int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}// 判空 front和rear都在起始点public boolean isEmpty() {return front == rear;}public boolean isFull() {return (rear + 1) % elem.length == front;}
}

---

1.5 双端队列 (Deque)

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队

 Deque是一个接口，使用时必须创建LinkedList的对象（所以他可以当作双向链表|栈使用）

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

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

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

 Stack这个类不是唯一的，可以是栈，LinkedList ，也可以是ArrayDeque

---

二、面试题

1. 用队列实现栈

 思考：一个普通的队列能否实现一个栈？  肯定是不可以的，一个是先进先出 ，一个是先进后出

思路：

（1）当两个队列都是空的时候 放到第一个队列

（2）再次" 入栈 “ 的时候，放到不为空的队列

（3）“出栈”的时候，出不为空的队列 ，出size -1 个元素 ，剩下的元素就是要出栈的元素

class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList();qu2 = new LinkedList();}public void push(int x) {//当两个队列都是空的时候放到第一个队列if(empty()) {qu1.offer(x);return;} //入栈，放到不为空的队列if(!qu1.isEmpty()) {qu1.offer(x);} else {qu2.offer(x);}}public int pop() {if(empty()) {return -1;} //找到不为空的队列 ，出size-1个元素if(!qu1.isEmpty()) {int size = qu1.size();for(int i =0;i<size-1;i++) { //这里不能写成i<qu1.size(),因为qu1.size()一直在变//出size-1个元素都放到另一个队列qu2.offer(qu1.poll());}//最后出本队列的最后一个元素return qu1.poll();} else {int size = qu2.size();for(int i =0;i<size-1;i++) {qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {if(empty()) {return -1;} //找到不为空的队列 ，出size个元素if(!qu1.isEmpty()) {int size = qu1.size();int tmp = -1;for(int i =0;i<size;i++) { //出size个元素都放到另一个队列,并用tmp记录下这个数tmp = qu1.poll();qu2.offer(tmp);}//返回最后出本队列的元素return tmp;} else {int size = qu2.size();int tmp = -1;for(int i =0;i<size;i++) { tmp = qu2.poll();qu1.offer(tmp);}return tmp;}}//两个队列都是空代表栈为空public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

2. 用栈实现队列

思路：

（1）“入队”:把数据放到第一个栈当中

（2）“出队”：出 s2 这个栈当中栈顶的元素即可，如果 s2 为空，把 s1 里面所有元素全部放到 s2

（3）当两个栈都为空 说明模拟的队列为空 

class MyQueue {private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if(empty()) {return -1;}if(s2.isEmpty()) {//s2为空，把s1中所有的元素放入s2中while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}public int peek() {if(empty()) {return -1;}if(s2.isEmpty()) {//s2为空，把s1中所有的元素放入s2中while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}