一、 队列(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 q = new LinkedList<>();
Queue 的方法有以下六种，每两种都是一样的功能（添| 删 |查），但是还是存在一定的差异
差异：
（1）add，remove，element都是Collection的通用方法
offer，poll，peek是队列专有的方法
（2）Collection实现的通用方法中 有些情况会报异常
而队列专有的方法中 不会报异常
eg：如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false
1. public static void main(String[] args) { 2. Queue<Integer> q = new LinkedList<>(); 3. q.offer(1); 4. q.offer(2); 5. q.offer(3); 6. q.offer(4); 7. q.offer(5); // 从队尾入队列 8. System.out.println(q.size()); 9. System.out.println(q.peek()); // 获取队头元素 10. 11. q.poll(); 12. System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 13. 14. if(q.isEmpty()){ 15. System.out.println("队列空"); 16. } else { 17. System.out.println(q.size()); 18. } 19. }
1.3 队列模拟实现
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。同学们思考下：队列的实现使用顺序结构还是链式结构好？
（1）单链表模拟实现：为了保证时间复杂度为O（1）
肯定不能从队头进，队尾出，这样删尾节点时间复杂度就为O（N）
所以采用从队尾进，队头出，但是这个时候就需要last指针来指向队尾 ，这样的尾插，头删才满足条件
（2） 双向链表模拟实现：无论从队头进，队尾出，还是从队尾进，队头出，都是可以的
双向链表就是神一般的存在 LinkedList：可以当作双向链表，栈，队列
（3）数组模拟实现：可以用来实现循环队列，如果实现普通队列，就会存在删除元素的前面（front指针的前面）无法再进行添加元素
下面这个代码是由双向链表(尾插，头删）实现队列：
1. import java.security.PublicKey; 2. //双向链表(尾插，头删）实现队列 3. public class MyQueue { 4. static class ListNode { 5. public int val; 6. public ListNode prev; 7. public ListNode next; 8. 9. public ListNode(int val) { 10. this.val = val; 11. } 12. 13. } 14. public ListNode head; 15. public ListNode last; 16. 17. //入队 18. public void offer(int val) { 19. ListNode node = new ListNode(val); 20. //尾插 21. if(head == null) { 22. head = last = node; 23. } else { 24. last.next = node; 25. node.prev = last; 26. last = node; 27. } 28. } 29. 30. //出队 31. public int poll() { 32. //空队列 33. if(head == null) { 34. return -1; 35. } 36. //一个节点 37. int val = -1; 38. if (head.next == null) { 39. val = head.val; 40. head = null; 41. last = null; 42. return val; 43. } 44. val = head.val; 45. head = head.next; 46. head.prev = null; 47. return val; 48. } 49. 50. //判断是否为空 51. public boolean empty() { 52. return head == null; 53. } 54. 55. public int peek() { 56. if (head == null) { 57. return -1; 58. } 59. return head.val; 60. } 61. }
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）（这个也比较简单）
1. class MyCircularQueue { 2. public int[] elem; 3. public int front; 4. public int rear; 5. 6. public MyCircularQueue(int k) { 7. elem = new int[k + 1];// 浪费一个空间，也就是需要多开一个元素的空间 8. } 9. 10. // 入队操作 11. public boolean enQueue(int value) { 12. if (isFull()) { 13. return false; 14. } 15. elem[rear] = value; 16. rear = (rear + 1) % elem.length;// 注意点1：不可直接rear+1 17. return true; 18. } 19. 20. // 删除队头元素（空不空 + front移动） 21. public boolean deQueue() { 22. if (isEmpty()) { 23. return false; 24. } 25. front = (front + 1) % elem.length; // 注意点2：不可直接front+1 26. return true; 27. } 28. 29. // 得到队头元素 不删除 30. public int Front() { 31. if (isEmpty()) { 32. return -1; 33. } 34. return elem[front]; 35. } 36. 37. // 得到队尾元素 不删除 38. public int Rear() { 39. if (isEmpty()) { 40. return -1; 41. } 42. // rear=0说明刚刚走过一圈以上，那么队尾就为elem.length-1 43. // rear!=0说明还没到跨越的位置，直接-1即可 44. int index = (rear == 0) ? elem.length - 1 : rear - 1; 45. return elem[index]; 46. } 47. 48. // 判空 front和rear都在起始点 49. public boolean isEmpty() { 50. return front == rear; 51. } 52. 53. public boolean isFull() { 54. return (rear + 1) % elem.length == front; 55. } 56. }
1.5 双端队列 (Deque)
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
Deque是一个接口，使用时必须创建LinkedList的对象（所以他可以当作双向链表|栈使用）
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口
Deque stack = new ArrayDeque<>(); //双端队列的线性实现
Deque queue = new LinkedList<>(); //双端队列的链式实现
Stack这个类不是唯一的，可以是栈，LinkedList ，也可以是ArrayDeque
二、面试题
1. 用队列实现栈
思考：一个普通的队列能否实现一个栈？ 肯定是不可以的，一个是先进先出 ，一个是先进后出
思路：
（1）当两个队列都是空的时候 放到第一个队列
（2）再次" 入栈 “ 的时候，放到不为空的队列
（3）“出栈”的时候，出不为空的队列 ，出size -1 个元素 ，剩下的元素就是要出栈的元素
1. class MyStack { 2. private Queue<Integer> qu1; 3. private Queue<Integer> qu2; 4. 5. public MyStack() { 6. qu1 = new LinkedList(); 7. qu2 = new LinkedList(); 8. 9. } 10. 11. public void push(int x) { 12. //当两个队列都是空的时候放到第一个队列 13. if(empty()) { 14. qu1.offer(x); 15. return; 16. } 17. //入栈，放到不为空的队列 18. if(!qu1.isEmpty()) { 19. qu1.offer(x); 20. } else { 21. qu2.offer(x); 22. } 23. 24. } 25. 26. public int pop() { 27. if(empty()) { 28. return -1; 29. } 30. //找到不为空的队列 ，出size-1个元素 31. if(!qu1.isEmpty()) { 32. int size = qu1.size(); 33. for(int i =0;i<size-1;i++) { //这里不能写成i<qu1.size(),因为qu1.size()一直在变 34. //出size-1个元素都放到另一个队列 35. qu2.offer(qu1.poll()); 36. } 37. //最后出本队列的最后一个元素 38. return qu1.poll(); 39. } else { 40. int size = qu2.size(); 41. for(int i =0;i<size-1;i++) { 42. qu1.offer(qu2.poll()); 43. } 44. return qu2.poll(); 45. } 46. } 47. 48. public int top() { 49. if(empty()) { 50. return -1; 51. } 52. //找到不为空的队列 ，出size个元素 53. if(!qu1.isEmpty()) { 54. int size = qu1.size(); 55. int tmp = -1; 56. for(int i =0;i<size;i++) { 57. //出size个元素都放到另一个队列,并用tmp记录下这个数 58. tmp = qu1.poll(); 59. qu2.offer(tmp); 60. } 61. //返回最后出本队列的元素 62. return tmp; 63. } else { 64. int size = qu2.size(); 65. int tmp = -1; 66. for(int i =0;i<size;i++) { 67. tmp = qu2.poll(); 68. qu1.offer(tmp); 69. } 70. return tmp; 71. } 72. } 73. 74. //两个队列都是空代表栈为空 75. public boolean empty() { 76. return qu1.isEmpty() && qu2.isEmpty(); 77. } 78. }
2. 用栈实现队列
思路：
（1）“入队”:把数据放到第一个栈当中
（2）“出队”：出 s2 这个栈当中栈顶的元素即可，如果 s2 为空，把 s1 里面所有元素全部放到 s2
（3）当两个栈都为空 说明模拟的队列为空
1. class MyQueue { 2. 3. private Stack<Integer> s1; 4. private Stack<Integer> s2; 5. 6. public MyQueue() { 7. s1 = new Stack<>(); 8. s2 = new Stack<>(); 9. } 10. 11. public void push(int x) { 12. s1.push(x); 13. } 14. 15. public int pop() { 16. if(empty()) { 17. return -1; 18. } 19. if(s2.isEmpty()) { 20. //s2为空，把s1中所有的元素放入s2中 21. while(!s1.isEmpty()) { 22. s2.push(s1.pop()); 23. } 24. } 25. return s2.pop(); 26. 27. } 28. 29. public int peek() { 30. if(empty()) { 31. return -1; 32. } 33. if(s2.isEmpty()) { 34. //s2为空，把s1中所有的元素放入s2中 35. while(!s1.isEmpty()) { 36. s2.push(s1.pop()); 37. } 38. } 39. return s2.peek(); 40. } 41. 42. public boolean empty() { 43. return s1.isEmpty() && s2.isEmpty(); 44. } 45. }
