Java数据结构（五）——栈和队列

栈和队列

栈

基本概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，即 “先进后出”

栈顶，即进行数据插入和删除操作的一端；栈底，即与栈顶相对的另一端。

栈的插入操作叫做压栈/进栈/入栈；栈的删除操作叫做出栈/退栈/弹出。栈的插入和删除操作都在栈顶一端。

---

了解了基本的概念后，我们尝试做一道小题，体会栈的先进后出的特性：

进栈序列为1，2，3，4 ，并且进栈的过程中可以出栈，则不可能的出栈序列是（）

A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1

想象现在有一个栈，最好还是画图，对于A：1进1出2进3进4进4出3出2出，满足；对于B：1进2进2出3进3出4进4出1出，满足；对于C：1进2进3进3出，此时栈顶元素为2，只能先出2才能出1，所以该序列不可能为出栈序列，不满足；对于D：1进2进3进3出4进4出2出1出，满足

所以，答案为：C

---

栈的模拟实现

了解了栈以及栈的特性，思考，怎么实现一个栈，使其满足栈的特性？

其实，使用数组和链表都可以，我们需要实现的方法包括：

• 入栈操作
• 出栈操作
• 获取栈顶元素
• 获取栈中的有效元素个数
• 判断栈是否为空

接下来我们就分别使用数组和链表实现一个栈：

【数组实现栈】

实现一个类，类中定义一个数组成员变量，为了满足栈的特性，数组只允许尾插和尾删：

大体框架如下：

public class MyStackByArray {public int[] elem;//栈public int capacity;//栈的容量public int usedSize;//栈的有效元素个数public MyStackByArray() {this.elem = new int[10];this.capacity = 10;}//入栈public void push(int data) {}//出栈并返回出栈元素public int pop() {}//获取栈顶元素public int peek() {}//获取栈中的有效元素public int size() {}//检测栈是否为空public boolean empty() {}
}

---

public int size()

返回成员变量usedSize即可

    //获取栈中的有效元素public int size() {return this.usedSize;}

---

public boolean empty()

    //检测栈是否为空public boolean empty() {return this.usedSize == 0;}

---

public void push(int data)

由于数组下标从0开始，所以成员变量usedSize其实就是下一次入栈的下标位置。入栈前，我们要判断栈是否满，满了要扩容，之后进行入栈即可：

    //入栈public void push(int data) {//栈满则扩容if(this.capacity == usedSize) {this.elem = Arrays.copyOf(elem, this.capacity * 2);this.capacity *= 2;}//入栈this.elem[this.usedSize] = data;this.usedSize++;}

---

public int pop()

出栈前，我们判断栈是否为空，当为空时，我们选择抛出一个自定义异常：StackIsException

public class StackIsEmptyException extends RuntimeException {public StackIsEmptyException(String message) {super(message);}
}

如果不为空，执行出栈，注意，出栈直接让usedSize--即可，不需要特意将栈顶元素置成0，因为当下次入栈时会覆盖掉此元素

    //出栈并返回出栈元素public int pop() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}//出栈this.usedSize--;return this.elem[this.usedSize];}

---

public int peek()

获取栈顶元素，判断为空？为空抛出异常，否则返回

    //获取栈顶元素public int peek() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}return this.elem[this.usedSize - 1];}

---

完整代码：

public class MyStackByArray {public int[] elem;public int capacity;public int usedSize;public MyStackByArray() {this.elem = new int[10];this.capacity = 10;}//入栈public void push(int data) {//栈满则扩容if(this.capacity == usedSize) {this.elem = Arrays.copyOf(elem, this.capacity * 2);this.capacity *= 2;}//入栈this.elem[this.usedSize] = data;this.usedSize++;}//出栈并返回出栈元素public int pop() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}//出栈this.usedSize--;return this.elem[this.usedSize];}//获取栈顶元素public int peek() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}return this.elem[this.usedSize - 1];}//获取栈中的有效元素public int size() {return this.usedSize;}//检测栈是否为空public boolean empty() {return this.usedSize == 0;}
}

---

【链表实现栈】

对于出栈，我们选择头删，因为尾删得遍历链表找到倒数第二个结点，效率较低

对于入栈，我们选择头插，因为出栈选择的是头删，要满足先进后出，必须选择头插。

代码比较简单，我们直接给出完整实现：

public class MyStackByLinkedList {//链表结点类static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//链表第一个结点的引用public ListNode head;//入栈public void push(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = newNode;return;}newNode.next = head;head = newNode;}//出栈并返回出栈元素public int pop() {if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}int ret = head.val;head = head.next;return ret;}//获取栈顶元素public int peek() {if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}return head.val;}//获取栈中的有效元素public int size() {int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}//检测栈是否为空public boolean empty() {return head == null;}
}

---

集合框架中的栈

集合框架中，顺序表对应ArrayList，链表对应LinkedList，那么栈对应什么呢？

栈的创建

栈对应三个：Stack、LinkedList、ArrayDeque，即这三个类都可以作为栈

• Stack类就是原生的栈类。只有无参构造方法
• LinkedList实现了Deque接口，Deque接口是双端队列接口，其中包含了操作栈的方法，所以LinkedList可作为链栈类。构造方法有两个：无参构造和利用其他容器的构造
• ArrayList也实现了Deque接口，实现了操作栈的方法，是基于数组的数据结构。构造方法有三个：无参构造、指定初始容量的构造、利用其他容器的构造
  

    public static void main(String[] args) {Stack<Integer> stack0 = new Stack<>();//StackLinkedList<Integer> stack1 = new LinkedList<>();//LinkedListArrayDeque<Integer> stack2 = new ArrayDeque<>();//ArrayDeque}

---

栈的方法

方法	功能
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中的有效元素的个数
boolean empty()	检测栈是否为空

• 注意：如果使用LinkedList或ArrayDeque实现栈，那么判空的方法为boolean isEmpty()，而不是boolean empty()

栈的遍历

关于栈的遍历，有三种方法，分别是迭代器、for-each和方法遍历：

• 对于Stack、LinkedList和ArrayDeque来说，利用方法遍历的结果是一致的，都是按照"先进后出’'的原则，并且这也是最常用的方法：

    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");while(!s1.empty()) {System.out.print(s1.pop() + " ");}System.out.println();System.out.println("=====LinkedList=====");while(!s2.isEmpty()) {System.out.print(s2.pop() + " ");}System.out.println();System.out.println("=====ArrayDeque=====");while(!s3.isEmpty()) {System.out.print(s3.pop() + " ");}System.out.println();}

• Stack使用迭代器打印的顺序是从栈底到栈顶，并不是出栈顺序，这是因为Stack是基于数组实现的，每次入栈都是在尾部；而LinkedList和ArrayDeque是按照出栈顺序打印的，这是因为它们入栈都是在头部/顶部进行的（头插）

    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");Iterator<Integer> it1 = s1.iterator();while(it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("=====LinkedList=====");Iterator<Integer> it2 = s2.iterator();while(it2.hasNext()) {System.out.print(it2.next() + " ");}System.out.println();System.out.println("=====ArrayDeque=====");Iterator<Integer> it3 = s3.iterator();while(it3.hasNext()) {System.out.print(it3.next() + " ");}System.out.println();}

• for-each遍历的结果与迭代器遍历的结果一致

    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");for(Integer x : s1) {System.out.print(x + " ");}System.out.println();System.out.println("=====LinkedList=====");for(Integer x : s2) {System.out.print(x + " ");}System.out.println();System.out.println("=====ArrayDeque=====");for(Integer x : s3) {System.out.print(x + " ");}System.out.println();}

---

栈的应用及相关练习

栈的"先进后出’'的特性，使得栈的应用场景十分广泛，比如，将序列逆序、递归转化为非递归等等。

下面是几道关于栈的经典题目：

括号匹配

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

class Solution {public boolean isValid(String s) {//补充代码}
}

【思路】

遍历字符串的每个字符，如果是左括号就入栈，如果是右括号，就从栈中弹出一个元素，看左右括号是否匹配。

最终结果不匹配的原因可能是：

• 只有左括号 或 只有右括号 或 左右括号数量不一致
• 左右括号类型不匹配

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();int i = 0;for(i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {if(stack.empty()) {return false;}else {char top = stack.pop();switch(top) {case '(':if(ch != ')') {return false;}break;case '[':if(ch != ']') {return false;}break;case '{':if(ch != '}') {return false;}break;}}}}if(!stack.empty()) {return false;}return true;}
}

原题链接：20. 有效的括号 - 力扣（LeetCode）

---

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

class Solution {public int evalRPN(String[] tokens) {//补充代码}
}

【思路】

逆波兰表达式，也叫后缀表达式，即将运算符写在操作数的后面。（我们平时习惯使用中缀表达式）举个简单的例子：

对于中缀表达式：(1 + 2) * 3，转化为后缀表达式：1 2 + 3 *

对于上面的后缀表达式的计算过程为： 寻找运算符，即找到了+，然后将+前的两个操作数执行+运算，得到3，此时表达式化简为3 3 *，继续向后找到*运算符，将前面两个操作数执行*运算，得到9，此时9就是表达式的结果。

了解了后缀表达式的求解，我们就可以解决这道题目：

遍历字符串数组，如果是数字就入栈，如果是运算符就不入栈并从栈中弹出两个元素，执行运算，将结果入栈，以此循环，最终栈中会剩余一个元素，这个元素就是表达式的结果

注意的问题：

• 题目给的是字符串数组，进行运算时，要将字符串类型转换为int类型
• 弹出时，先弹出的是右操作数，后弹出的是左操作数，注意两者的顺序，以免计算出错

class Solution {public int evalRPN(String[] tokens) {Stack<String> stack = new Stack<>();for(int i = 0; i < tokens.length; i++) {String s = tokens[i];if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {int op2 = Integer.valueOf(stack.pop());int op1 = Integer.valueOf(stack.pop());switch(s) {case "+":stack.push(String.valueOf(op1 + op2));break;case "-":stack.push(String.valueOf(op1 - op2));break;case "*":stack.push(String.valueOf(op1 * op2));break;case "/":stack.push(String.valueOf(op1 / op2));break;} }else {stack.push(s);}}return Integer.valueOf(stack.pop());}
}

原题链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

---

出栈入栈次序匹配

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {//补充代码}
}

【思路】

遍历入栈序列，每次将该次遍历到的元素入栈，然后判断当前的栈顶元素是否与出栈序列的元素相等，即是否可以出栈，如果可以，就出栈（出栈一次后，遍历出栈序列的指针也要后移），直到不能出栈了，继续遍历入栈序列，遍历完成后，如果栈为空说明匹配。

    public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(j < popV.length && !stack.isEmpty() && stack.peek() == popV[j]) {stack.pop();j++;}}return stack.isEmpty();}

注意：

• while循环判断是否可以出栈前，要判断栈是否为空，否则可能会抛出栈空异常
• j < popV.length在本题目中可以不写，因为题目保证两个序列长度相等，如果测试用例给出的长度不一定相等，那就需要加上

原题链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

---

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {public MinStack() {}public void push(int val) {}public void pop() {}public int top() {}public int getMin() {}
}

【思路】

维护两个栈，一个是普通的栈，一个是存放最小值的栈，它的栈顶元素就是当前状态下的普通栈中的最小值，具体操作：

当入栈时，普通的栈直接入栈，如果最小值栈为空或者最小值栈的栈顶元素>=入栈元素，那么最小值栈也入栈该元素

当出栈时，普通的栈直接出栈，同时判断普通栈的出栈元素是否与当前最小值栈的栈顶元素一致，如果一致，最小值栈也弹出元素一次

当想要获取当前栈中的最小元素时，直接返回最小值栈的栈顶元素

如此，维护了两个栈。

class MinStack {public Stack<Integer> stack;public Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty() || minStack.peek() >= val) {minStack.push(val);}}public void pop() {if(stack.empty()) {return;}if(stack.pop().equals(minStack.peek())) {minStack.pop();}}public int top() {if(stack.empty()) {return -1;}return stack.peek();}public int getMin() {if(minStack.empty()) {return -1;}return minStack.peek();}
}

注意：

• 最小值栈入栈的条件：当入栈元素与当前最小值栈的栈顶元素相等时，也要入栈，相当于有多个相等的最小值。

• 这一条是笔者在解决该问题时出现的问题，如果我将pop()方法改成如下代码，是否可行？

      public void pop() {if(stack.empty()) {return;}if(stack.pop() == minStack.peek()) {minStack.pop();}}
  

  不可行！

  因为，Stack类中的pop()和peek()方法返回的是类型实参的类型，即实现泛型时<>里传入的类型，是引用类型，如果像上面这样书写，本质上是对两个引用类型使用==比较，引用类型==比较的是地址，而不是值，所以不可行！

  但是，对于该题目，泛型实现时传入的是Integer类型，通过==比较时，可能会出现true的情况，这是因为Integer有缓存机制：

  缓存机制：

  • Java对于Integer类型的对象在值位于-128到127之间时有特殊的缓存处理。JVM会为这个范围的每个数字缓存一个Integer对象。

    例如，Integer a = 127; Integer b = 127; System.out.println(a == b); // 输出 true，因为a和b都指向同一个缓存的对象。

  • 对于超出该范围的数字，即使值相同，也会创建不同的对象实例，所以==会比较返回false。

    如 Integer c = 128; Integer d = 128; System.out.println(c == d); // 输出 false。

  我们无法保证题目给出的值在缓存区间内，所以不可以像上面那样书写，我们可以使用equals方法判断它们的值是否相等（就如答案所示），或者这么写：

      public void pop() {if(stack.empty()) {return;}int tmp = stack.pop();if(tmp == minStack.peek()) {minStack.pop();}}
  

  上面这个代码将Stack类中的pop方法的返回值用int类型的一个变量接收，返回值是Integer类型，所以会自动拆箱为int类型，再用int类型与peek方法返回值的Integer类型使用==比较，而当使用==比较Java中的Integer类型与int类型时，会将Integer类型拆箱为int类型，所以本质上是两个int类型的比较，可行！

  原题链接：155. 最小栈 - 力扣（LeetCode）

---

几个含"栈"概念的区分

区分栈、虚拟机栈和栈帧：

栈、虚拟机栈和栈帧是Java虚拟机（JVM）中的三个相关但不同的概念，它们在定义功能、数据结构以及生命周期等方面存在明显的区别：

1. 定义功能
   • Java栈：通常指的是一种后进先出（LIFO）的数据结构，用于存储程序执行过程中的临时数据。例如，方法的局部变量和返回地址等。
   • 虚拟机栈：特指JVM为每个线程分配的独立内存区域，用于存放栈帧，即方法调用的信息。它与线程同时创建和销毁，主要支持方法的调用和执行。
   • 栈帧：是虚拟机栈中的一个元素，对应于正在执行的每个方法。每个方法执行时都会创建一个对应的栈帧，包含局部变量表、操作数栈、动态链接以及方法出口等信息。
2. 数据结构
   • Java栈：作为一种数据结构，其实现可以基于数组或链表，主要用于算法中数据的临时存储。
   • 虚拟机栈：作为JVM内部的一个运行时数据区，其内部由多个栈帧组成，每个栈帧对应一个方法调用的相关信息。
   • 栈帧：具有固定的数据结构，包括局部变量表、操作数栈等，这些组成部分在编译期间就已经确定大小。
3. 生命周期
   • Java栈：根据程序逻辑进行入栈和出栈操作，使用完毕后即可销毁。
   • 虚拟机栈：与线程绑定，线程结束时对应的虚拟机栈也会被销毁。
   • 栈帧：在方法调用时创建，方法执行完毕或异常终止时销毁。
4. 存储内容
   • Java栈：可用于存储任何类型的对象，如基本类型、引用类型等。
   • 虚拟机栈：专门用于存储方法调用的相关信息，如局部变量、操作数等。
   • 栈帧：具体存储了方法的局部变量表、操作数栈、动态链接以及方法的返回地址等信息。
5. 应用场景
   • Java栈：广泛应用于各类算法中，如深度优先搜索、递归计算等。
   • 虚拟机栈：在JVM的执行引擎中应用，用于支持方法的调用和执行。
   • 栈帧：直接关联到每个方法的具体执行过程，记录了方法执行所需的全部信息。

总的来说，Java栈、虚拟机栈和栈帧各自承担着不同的功能和角色。Java栈是一个通用的数据结构，而虚拟机栈和栈帧则是JVM内部专门设计的机制，用于支持方法的调用和执行。这三者共同协作，确保了Java程序能够高效、安全地运行。

---

队列

基本概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，其特点概括为 “先进先出”，就像现实生活中的排队一样，在最早排队的总是先出队。

队头：进行删除操作的一端；队尾：进行插入操作的一端

注意区分栈和队列。

---

队列的模拟实现

了解了队列的基本概念后，思考怎样实现一个队列？使用数组还是链表？

假设使用数组，通常我们会定义一个队头变量和队尾变量，以方便入队和出队操作，入队操作使用尾插，那么出队操作就必须是头删。当队列不为空，每次出队，队头变量要不断地向后移动，最终会导致数组的前半部分空间都被浪费了，且队列容量越来越少，所以简单的数组实现队列是不方便的，如果要使用数组，那么最好实现成循环队列（后面会讲）。

一般来说，队列使用链表实现，问题是入队和出队操作怎么实现？对于单链表，定义两个引用，分别指向队头和队尾，如果出队采用尾删，那么我们就得遍历链表找到倒数第二个结点，让它的next为null，效率较低，所以出队采用头删，相应地，入队采用尾插，从而达到"先进先出"的特点，并且保证了入队和出队的时间复杂度都是O(1)。

但如果是双向链表，那么就不需要考虑上面的问题，入队出队操作都是O(1)，我们这里采用双向链表模拟实现一个队列：

实现如下（双向链表的头删、尾插操作，较为简单）：

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 tail;//队尾引用private int size;//队列有效元素个数//入队public void offer(int data) {ListNode newNode = new ListNode(data);if(tail == null) {head = newNode;tail = newNode;size++;return;}tail.next = newNode;newNode.prev = tail;tail = newNode;size++;}//出队并返回出队元素public int poll() {if(this.head == null) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}int ret = head.val;if(head == tail) {head = null;tail = null;}else {head.next.prev = null;head = head.next;}size--;return ret;}//获取队头元素public int peek() {if(this.head == null) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}return this.head.val;}//获取队列中的有效元素个数public int size() {return this.size;}//判断队列是否为空public boolean isEmpty() {return this.head == null;}}

---

循环队列

前面提到，单纯的数组实现队列会导致空间的浪费以及队列大小的缩减，这时候引出了循环队列的概念：

循环队列是一种优化的队列数据结构，旨在解决顺序队列中存在的“假溢出”问题。

循环队列采用了头尾相接的环状存储结构，通过将顺序队列的数组视为一个循环结构，使得当存储空间的最后一个位置已被使用时，新元素可以继续从第一个位置开始存储，形成一个逻辑上的环。这种设计极大地提高了存储空间的利用率。

接下来我们就讲解一下循环队列的思想，关于循环队列，我们要解决两大问题：

当存储空间的最后一个位置已被使用时，新元素怎样继续从第一个位置开始存储?

怎样区分循环队列的 空 和 满 两个状态？

---

【问题一】

在实现循环队列时，我们仍然会定义两个"指针"：rear(指向队尾，这个队尾实际上是下一次入队的位置，而不是指队尾元素)、front(指向队头，即队头元素)，于是就可能会出现下图的情况：

此时，存储空间的最后一个位置已被使用，rear指向了最后位置后面的一个位置（此位置不能入新元素了），而此时由于进行过出队操作，数组的前面还有剩余空间可以使用，我们就得想办法让空闲空间被利用到，即让rear重新回到数组开始的位置，怎么办？

传统的rear += 1肯定不行，我们采用这样的语句 rear = (rear + 1) % len，len就是数组长度。对于上面的情况，我们代入公式：

rear = (8 + 1) % 9，得到0，此时rear就重新回到了数组0下标位置，这个公式在任何位置都是可以的。有了这个公式，front和rear就可以循环起来了。

---

【问题二】

怎样区分循环队列的 空 和 满 两个状态？ 我们看如下图表示的情况，为了突出循环，我们将数组在视觉上改成环：

图1表示队列为空，图2表示队列已满，但是两种情况下都是rear == front，怎么区分呢？

我们有三种解决方案：

• 定义成员变量size表示队列中的有效元素个数：当size和数组长度相等时，表示满；为0时表示空
• 定义一个boolean类型的标记：最开始为false，当入队新元素后变为true，当出队元素后rear == front，说明最后一个元素出队了，将其置为false。这样，当rear == front && 标记为false时，表示空，当rear == front && 标记为true时，表示满
• 浪费一个空间：即留出一个空间不放元素，当rear == front时，表示空；当(rear + 1) % len == front(下一个位置是队头)时，表示满

---

解决完上面的两个问题，我们以第二种解决方案动手实现一下，（分析与注意事项在代码后面）：

public class CircularQueue {public int[] elem;//数组private boolean flag;//标记public int rear;//队尾指针public int front;//队头指针public CircularQueue() {elem = new int[10];}public void offer(int data) {if(rear == front && flag == true) {System.out.println("队列已满");return;}elem[rear] = data;rear = (rear + 1) % elem.length;flag = true;}public int poll() {if(isEmpty()) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}int ret = elem[front];front = (front + 1) % elem.length;if(rear == front) {flag = false;}return ret;}public int peek() {if(isEmpty()) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}return elem[front];}public int size() {if(rear > front) {return rear - front;}else if(rear < front) {return rear + (elem.length - front);}else {return flag == true ? elem.length : 0;}}public boolean isEmpty() {return rear == front && flag == false;}
}

• rear实际上指向下一次入队的位置，而不是指向队尾元素；而front是指向队头元素
• offer方法最后一定要将标记置为true
• poll方法内部在front因出队改变后，要检查是否要将标记置为false，即检查该次出队的是否是队列中最后一个元素
• size方法考虑的就比较多了，循环队列的思想导致rear和front的相对位置会发生变化，如代码：分为rear > front、rear < front以及rear == front，特别注意第三种相等的情况，可能是满了，也可能是空，这要根据标记判断。

---

不妨做个练习，尝试使用问题二中的其他方案设计循环队列：

class MyCircularQueue {public MyCircularQueue(int k) {}public boolean enQueue(int value) {}public boolean deQueue() {}public int Front() {}public int Rear() {}public boolean isEmpty() {}public boolean isFull() {}
}

给出以浪费一个空间方案完成该题目的代码：

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;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;}if(rear == 0) {return elem[elem.length - 1];}return elem[rear - 1];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear + 1) % elem.length == front;}
}

• 既然要浪费一个空间，那么我们在构造方法初始化数组时要创建一个比参数大1个空间的数组，保证一部分测试用例能够顺利通过。
• Rear方法要求返回队尾元素，由于我们的rear是队尾元素之后的一个位置，所以我们必须向前一个位置找，这里就有一个特殊情况，当rear == 0，此时不能减一，前一个应该是数组最后一个下标的位置，所以有如上代码。

原题链接：622. 设计循环队列 - 力扣（LeetCode）

---

双端队列

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

在集合框架中，双端队列对应Deque接口，在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

实现双端队列可以用LinkedList（链式实现）或ArrayDeque（线性实现）：

    public static void main(String[] args) {Deque<Integer> deque1 = new LinkedList<>();//链式实现Deque<Integer> deque2 = new ArrayDeque<>();//线性实现}

所以，到这里我们发现：

LinkedList可以作为链表、栈、(普通)队列、双端队列

ArrayList可以作为栈、(普通)队列、双端队列

---

集合框架中的队列

集合框架中的队列是Queue接口，Deque接口继承自它，LinkedList和ArrayDeque都实现了该接口。

队列的创建

我们可以通过ArrayDeque或者LinkedList创建一个队列：

    public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();//链式队列Queue<Integer> queue2 = new ArrayDeque<>();//线性队列}

---

队列的方法

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

---

队列的遍历

    public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();queue1.offer(1);queue1.offer(2);queue1.offer(3);queue1.offer(4);queue1.offer(5);System.out.println("=====for-each=====");for(Integer x : queue1) {System.out.print(x + " ");}System.out.println();System.out.println("=====迭代器=====");Iterator<Integer> it = queue1.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("=====while=====");while(!queue1.isEmpty()) {System.out.print(queue1.poll() + " ");}System.out.println();}

---

队列的应用及相关练习

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

class MyStack {public MyStack() {}public void push(int x) {}public int pop() {}public int top() {}public boolean empty() {}
}

【思路】

以画图+文字介绍：

现在我们要模拟出栈，如图向栈中依次加入21、56、23、11，此时栈顶元素应为11，出栈时要弹出11。

我们只有两个队列，所以让不为空的队列中的元素出队，直到只剩1个元素，这个元素就是"栈顶"元素，将它"弹出"；此时如果再次入队

此时，如果再添加新元素，继续向非空队列添加，而它就是新的"栈顶元素"，如果接着"出栈"，就重复上面的工作：将元素出队到空队列，直到只剩一个元素，弹出。

所以有：

入栈： 向非空队列中添加元素，初始都为空时随意选择

出栈： 非空队列将元素出到空队列中，直到只剩下一个元素，这个元素就是栈顶元素，弹出

class MyStack {public Queue<Integer> q1;public Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {if(!q1.isEmpty()) {q1.offer(x);}else if(!q2.isEmpty()){q2.offer(x);}else{q1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();for(int i = 0; i < size - 1; i++) {q2.offer(q1.poll());}return q1.poll();}else{int size = q2.size();for(int i = 0; i < size - 1; i++) {q1.offer(q2.poll());}return q2.poll();}}public int top() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();int ret = 0;for(int i = 0; i < size; i++) {ret = q1.poll();q2.offer(ret);}return ret;}else{int size = q2.size();int ret = 0;for(int i = 0; i < size; i++) {ret = q2.poll();q1.offer(ret);}return ret;}}public boolean empty() {return q1.isEmpty() && q2.isEmpty();}
}

原题链接：225. 用队列实现栈 - 力扣（LeetCode）

---

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

class MyQueue {public MyQueue() {}public void push(int x) {}public int pop() {}public int peek() {}public boolean empty() {}
}

【思路】

如上图，如果不再添加新元素，按照图解思路出队，得到序列：[10, 44, 31, 12, 101, 88, 36]，满足队列的先进先出。

class MyQueue {public Stack<Integer> sIn;public Stack<Integer> sOut;public MyQueue() {sIn = new Stack<>();sOut = new Stack<>();}public void push(int x) {sIn.push(x);}public int pop() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.pop();}public int peek() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.peek();}public boolean empty() {return sIn.empty() && sOut.empty();}
}

原题链接：232. 用栈实现队列 - 力扣（LeetCode）

---

完