【数据结构】(7) 栈和队列

一、栈 Stack

1、什么是栈

        栈是一种特殊的线性表，它只能在固定的一端（栈顶）进行出栈、压栈操作，具有后进先出的特点。

2、栈概念的例题

答案为 C，以C为例进行讲解：

第一个出栈的是3，那么 1、2、3 必须已经依次入栈，出栈 3，此时栈为 1、2。

第二个出栈的是1，显然不可能，因为必须出栈 2 后，才能出栈1。因此 C 不可能是出栈序列。

栈还可以模拟递归，因为栈具有后进先出的特点。比如：逆序打印链表。

3、栈的使用

LinkedList 也能当作栈使用：（原因下一节说明）

LinkedList<Integer> stack = new LinkedList<>(); // 创建栈
其他操作与 Stack 集合类一致

4、顺序栈的实现 MyStack

4.1、栈的实现方法

        实现栈的两种方法：因为追求效率，我们期望出栈、压栈的操作的时间复杂度都为 O(1)。

① 用数组实现栈（顺序栈）：

        显然，在数组一端进行入栈、出栈、查看栈顶操作都是 O(1)，只需 top 标记指向栈顶下标。

② 用链表实现栈（链式栈）：

        如果使用单链表，只能在头部出栈、压栈；如果是尾部需要找到尾结点，复杂度为O(N)，就算设置尾指针，也因为获取不到前驱，而无法实现出栈。

        如果使用双链表，因为包含尾指针、能获取结点的前驱，因此在任意一端压栈出栈都能是 O(1)。故 LinkedList 可用作栈使用。

        总结：数组、单链表、双链表（LinkedList）都能实现栈，但单链表只能在头部进行操作。

4.2、代码

MyStack：

public class MyStack {private  int[] arr;private int top;private static final int DEFAULT_SIZE = 10;public MyStack() {arr = new int[DEFAULT_SIZE];top = -1;}private void grow() { // 扩容arr = Arrays.copyOf(arr, (int)(arr.length * 1.5));}private boolean isFull() {return top == arr.length - 1;}public boolean isEmpty() {return top == -1;}public void push(int value) {if (isFull()) {grow();}arr[++top] = value;}public int pop() {if (isEmpty()) {throw new StackEmptyException("栈未空异常");}return arr[top--];}public int peek() {if (isEmpty()) {throw new StackEmptyException("栈未空异常");}return arr[top];}public int size() {return top + 1;}
}

栈空异常：运行时异常，不强制要求对异常进行处理，所以 pop 和 peek 可以不声明异常抛出，JVM 能够处理。

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

单元测试：

public class Test {public static void main(String[] args) {try {
//            Stack<Integer> stack = new Stack<>(); // 创建栈MyStack stack = new MyStack(); // 创建栈stack.push(1); // 压入元素stack.push(2);stack.push(3);System.out.println(stack.size()); // 输出栈的大小，3System.out.println(stack.peek()); // 输出栈顶元素，但不弹出，3System.out.println(stack.pop()); // 弹出栈顶元素，3System.out.println(stack.pop()); // 2System.out.println(stack.pop()); // 1System.out.println(stack.isEmpty()); // 判断栈是否为空，trueSystem.out.println(stack.pop()); // 打印异常} catch (StackEmptyException e) {e.printStackTrace();}}
}

5、面试题练习

5.1、有效的括号

20. 有效的括号 - 力扣（LeetCode）

分析：每遇到一个右括号，都需要与其左边最近的左括号进行匹配。如果所有右括号都匹配上，并且没有剩余的左括号，就说明括号有效；否则无效。因为要求右括号的左边最近的左括号（后进先出），所以可以用栈来存放遇到过的所有左括号。

思路：遍历每个括号：

① 压栈：遇到一个左括号就压栈。

② 出栈：遇到一个右括号就出栈。如果栈未空或者弹出的左括号不匹配，则表示括号无效。

③ 当括号遍历结束，栈不为空，说明左括号有多余的，括号也无效。

class Solution {public boolean isValid(String s) { // s 仅由 '()[]{}' 组成Stack<Character> stack = new Stack<>(); // 左括号栈String left = "([{"; // 左括号字符String right = ")]}"; // 右括号字符int len = s.length();for(int i = 0; i < len; i++) {char ch = s.charAt(i);if(left.indexOf(ch) > -1) { // 如果是左括号，则入栈stack.push(ch);}else { // 弹出栈顶左括号，与当前右括号匹配if(stack.isEmpty() || left.indexOf(stack.pop()) != right.indexOf(ch)) { // 栈为空、栈顶左括号不匹配，则无效return false;}}}if(!stack.isEmpty()) { // 遍历结束，栈不为空，则无效return false;}return true;}
}

注：判断是否是左括号时，为什么用 indexOf 而不用 contains，因为 contains 的参数不能是字符。为什么 indexOf 的参数可以是包装类，因为自动拆箱，Character 自动转为 char。

5.2、逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

        表达式的形式可分为前缀表达式（波兰）、中缀表达式、后缀表达式（逆波兰）。

① 中缀表达式：a+b*c+(d*e+f)*g

② 前缀表达式：中缀转前缀，手动转法

根据算术符号优先级，添括号：((a+(b*c))+(((d*e)+f)*g))

把算术符号提到对应括号前面：+(+(a*(bc))*(+(*(de)f)g))

去掉括号：++a*bc*+*defg

③ 后缀表达式：中缀转后缀，手动转法

把算术符号提到对应括号后面：((a(bc)*)+(((de)*f)+g)*)+

去掉括号：abc*+de*f+g*+

用代码转换的算法，有点难度，有兴趣可以学习。

本题目的是根据后缀表达式求值。

思路：遍历表达式的每个字符，可以观察到，每个运算符是跟左边最近的两个操作数（后入先出）匹配的，因此可以用栈。

① 压栈：遇到操作数就压栈。每次的中间计算结果也要压栈。

② 出栈：遇到运算符就两次出栈，取出两个操作数作运算（第一个取出的是右操作数），将结果计算结果压栈。

遍历结束，出栈，取出最终结果。

class Solution {private boolean isOperation(String s) {String operations = "+-*/";return operations.contains(s);} public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>(); // 操作数栈for(String token : tokens) {if(!isOperation(token)) { // 如果是操作数，则入栈stack.push(Integer.valueOf(token));}else { // 如果是操作数，则取出两个操作数，并将计算结果压栈Integer num1 = stack.pop();Integer num2 = stack.pop();switch(token) {case "+":stack.push(num2+num1);break;case "-":stack.push(num2-num1);break;case "*":stack.push(num2*num1);break;case "/":stack.push(num2/num1);break;}}}return stack.pop();}
}

5.3、出栈、入栈次序匹配

栈的压入、弹出序列_牛客题霸_牛客网

思路：

① 从左到右，从入栈序列中取出一个元素，并压入栈。

② 从出栈序列中取出一个元素，与栈顶对比，如果匹配则弹出栈顶，重复②，直到栈为空；如果不匹配，或者栈为空，则重复①，直到遍历完入栈序列。

③ 最后，入栈序列的每个元素都压过栈。如果栈不为空，说明存在不匹配；如果栈为空，说明全部匹配完。

public class Solution {/*** @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>(); // 用于模拟出栈入栈过程int j = 0; // 用于记录出栈序列的当前下标int len = pushV.length;// 遍历入栈序列，并依次压入栈for (int k : pushV) {stack.push(k);// 依次取出出栈序列元素，如果匹配，就出栈，直到栈为空。如果不匹配，就继续压栈，直到压完都没有匹配的，最后栈不为空，存在不匹配// 这两个条件不能交换，防止栈为空了还进行 peekwhile (!stack.isEmpty() // 直到栈为空退出&& stack.peek() == popV[j]) { // 匹配 stack.pop(); // 出栈j++; // 匹配下一个}}return stack.isEmpty();}
}

5.4、最小栈

155. 最小栈 - 力扣（LeetCode）

注意是常数时间。

思路：创建两个栈，一个是正常栈，一个是最小值栈。

① 入栈：如果栈为空，最小栈要入；如果不是第一次入栈，先跟最小栈栈顶比较，如果小于，则入最小栈。等于的情况也要入最小栈，防止正常栈有多个相同元素。（如果等于的情况不入，那么出栈的时候，正常栈出了一个相同值，并且这个值还是最小值，那么最小栈就把唯一的一个相同值出了，但正常栈中依旧有相同值且为最小值。）

② 出栈：如果正常栈栈顶元素等于最小栈栈顶元素，则需要出最小栈。

③ 获取栈中最小值：最小栈的栈顶元素。

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {if(stack.isEmpty() || val <= minStack.peek()) { // 最小栈为空，或者 val ≤ 最小值栈栈顶，最小值栈要入minStack.push(val);}stack.push(val); // 正常栈必入}public void pop() {int val = stack.pop();if(val == minStack.peek()) { // 如果正常栈栈顶 = 最小栈栈顶，要出最小栈minStack.pop();}// if(stack.pop() == minStack.peek()) 不要这样写，两边都是 Integer 类型，比较的是对象的地址// 上面的写法，因为 val 是 int，右边的 Integer 会自动拆箱}public int top() {return stack.peek();}public int getMin() {return  minStack.peek();}
}

二、队列

1、什么是队列

        队列也是一种特殊的顺序表，但只能在固定的一端（队尾，tail/rear）入队，另一端（队头，head/front）出队，具有先进先出的特点。

2、队列的使用

        可从集合类框架图看到，Queue 只是个接口，想实例化队列必须使用 LinkedList 实例化。

        Queue 中声明的方法：

        add(当设置了容量，超过此容量时，会抛出 IllegalStateException 异常)、remove(当队列为空时，抛出 NoSuchElementException 异常)、element(当为空，抛出NoSuchElementException 异常)为一组，offer(一般都是添加成功，返回 true。如果有添加失败，返回 false)、poll(当队列为空，返回 null)、peek(当队列为空，返回 null)为一组，我们通常使用 offer、poll、peek。

3、队列的实现

3.1、队列的实现方法

        队列的实现也分为两种：我们想入队、出队操作也是O(1)时间复杂度。

① 数组（顺序队列）：数组用 rear、front 标记存储队尾、队头下标即可实现，但存在空间浪费问题。因此，延伸出循环队列的概念，在下一小节有讲到。

② 链表（链式队列）：对于单链表，必须要有 tail 指针，并只能头删、尾插；对于头插、尾删是不可行的，因为不能通过 tail 得到其前驱结点，尾删则不能在O(1)内实现。对于双向链表，任意一端作为队尾都可行，另一端作为队头。

        总结：数组、单链表、双向链表（LinkedList）都可实现队列。但存在限制：普通数组会造成空间浪费，建议使用循环队列；单链表要求有 tail 指针，且必须头删尾插。

3.2、循环队列

        普通数组实现队列，会造成空间浪费：

        循环队列，解决了顺序队列空间浪费问题：

        产生2个问题：

① 如何从队尾跨越到队头。

        向后移动 offset：index = (index+1)%arr.length

        向前移动 offset：index = (index + arr.length -1) % arr.length

② 队空和队满都是 front == rear，如何区分队空和队满。

        方法一：设置 size ，保存当前已用容量长度。当 size 等于数组长度时，则满；当 size 等于 0 时则空。

        方法二：设置 isFull 标记，true 表示满。初始时，isFull 设 false；每次出队后，isFull 设 false；每次入队后，如果 front == rear，isFull 设为 true。

        方法三：浪费一个空间，队满时，让 rear 停在 front 之前。

3.3、链式队列的实现 MyQueue

public class MyQueue {private static class Node {int data;Node next;Node prev;public Node(int data) {this.data = data;}}private Node head; // 队头private Node tail; // 队尾private int size; // 队列大小public void offer(int data) {Node newNode = new Node(data);if (tail == null) { // 队列为空head = tail = newNode;}else {tail.next = newNode;newNode.prev = tail;tail = newNode;}size++;}public int poll() {if (head == null) { // 队列为空return -1;}int data = head.data;head = head.next;if (head != null) {head.prev = null;} else { // 队列中只有一个元素tail = null;}size--;return data;}public int peek() {if (head == null) { // 队列为空return -1;}return head.data;}public boolean isEmpty() {return head == null;}public int size() {return size;}
}

3.4、循环队列的实现 MyCircularQueue

622. 设计循环队列 - 力扣（LeetCode）

方法1：浪费一个空间区分队空和队满。 

class MyCircularQueue {private int[] arr;private int front;private int rear;public MyCircularQueue(int k) {arr = new int[k+1]; // 需要浪费一个空间}public boolean enQueue(int value) {if(isFull()) {return false;}arr[rear] = value;rear = (rear + 1) % arr.length;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % arr.length;return true;}public int Front() {if(isEmpty()) {return -1;}return arr[front];}public int Rear() {if(isEmpty()) {return -1;}return arr[(rear + arr.length - 1) % arr.length]; // 这里要注意}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear + 1) % arr.length == front;}
}

方法2：使用 isFull 标记队满。

class MyCircularQueue {private int[] arr;private int front;private int rear;private boolean isFull;public MyCircularQueue(int k) {arr = new int[k];}public boolean enQueue(int value) {if(isFull()) {return false;}arr[rear] = value;rear = (rear + 1) % arr.length;if(rear == front) { // 入队后，rear == front 则队满isFull = true;}return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % arr.length;isFull = false; // 一旦出队，就说明不满return true;}public int Front() {if(isEmpty()) {return -1;}return arr[front];}public int Rear() {if(isEmpty()) {return -1;}return arr[(rear + arr.length - 1) % arr.length];}public boolean isEmpty() {return rear == front && !isFull; // rear == front 并且队不满}public boolean isFull() {return isFull; // 直接返回队满标记}
}

4、双端队列

        双端队列（Double Queue）就是两端都能入队和出队，即队头能出队入队，队尾能出队入队。deque 是一个接口，实例化使用 ArrayDeque（顺序实现） 或者 LinkedList（链式实现） 。

5、面试题练习

5.1、用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

分析：栈后进先出，队列先进先出。我们想实现后进的先出，那么可以把后进元素移到队头：

① 入栈：两队都为空，默认入队列1；元素先入队为空队列，再将不为空队列全部出队，入队到只有栈顶元素的队列中，这样，后续先出队的必是栈顶元素。

② 出栈：不为空的队列，出队一个元素。

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);}else { // 元素先入队到为空的队列，再把不为空的全入队到为空的队列。栈顶元素就放到了队头if(queue1.isEmpty()) {queue1.offer(x);while(!queue2.isEmpty()) {queue1.offer(queue2.poll());}}else {queue2.offer(x);while(!queue1.isEmpty()) {queue2.offer(queue1.poll());}}}}public int pop() {// 栈为空，错误if(empty()) {return -1;}// 不为空的出队一个元素if(queue1.isEmpty()) {return queue2.poll();}else {return queue1.poll();}}public int top() {// 栈为空，错误if(empty()) {return -1;}// 不为空的队列一直出队，另一个队列入队，最后一个出队的元素就是栈顶if(queue1.isEmpty()) {return queue2.peek();}else {return queue1.peek();}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

5.2、用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

分析：想实现先进先出，而栈是后进先出：想办法把后入的放到栈底

① 入栈：都为空，默认入栈1。否则入不为空的栈。

② 出栈：把不为空的出栈到另一个栈，序列就倒了过来，栈顶就是队头元素，出栈顶，然后再倒回去。

class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {// 都为空，默认入栈1// if(empty()) {//     stack1.push(x);// }// else { // 入不为空的那个必为栈1//     stack1.push(x);// }stack1.push(x);}public int pop() {if(empty()) {return -1;}while(!stack1.isEmpty()) { // 倒给栈2stack2.push(stack1.pop());}int head = stack2.pop(); // 栈2的栈顶就是队头元素while(!stack2.isEmpty()) { // 倒回给栈1stack1.push(stack2.pop());}return head;}public int peek() {if(empty()) {return -1;}while(!stack1.isEmpty()) { // 倒给栈2stack2.push(stack1.pop());}int head = stack2.peek(); // 栈2的栈顶就是队头元素while(!stack2.isEmpty()) { // 倒回给栈1stack1.push(stack2.pop());}return head;}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}