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

一、栈 Stack

1、什么是栈

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

2、栈概念的例题

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

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

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

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

3、栈的使用

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

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

4、顺序栈的实现 MyStack

4.1、栈的实现方法

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

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

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

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

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

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

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

4.2、代码

MyStack：

java">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 能够处理。

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

单元测试：

java">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()); // 输出栈的大小，3
            System.out.println(stack.peek()); // 输出栈顶元素，但不弹出，3
            System.out.println(stack.pop()); // 弹出栈顶元素，3
            System.out.println(stack.pop()); // 2
            System.out.println(stack.pop()); // 1
            System.out.println(stack.isEmpty()); // 判断栈是否为空，true
            System.out.println(stack.pop()); // 打印异常
        } catch (StackEmptyException e) {
            e.printStackTrace();
        }
    }
}

5、面试题练习

5.1、有效的括号

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

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

思路：遍历每个括号：

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

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

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

java">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*+

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

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

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

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

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

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

java">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、出栈、入栈次序匹配

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

思路：

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

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

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

java">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);
            // 依次取出出栈序列元素，如果匹配，就出栈，直到栈为空。如果不匹配，就继续压栈，直到压完都没有匹配的，最后栈不为空，存在不匹配
            // 这两个条件不能交换，防止栈为空了还进行 peek
            while (!stack.isEmpty() // 直到栈为空退出
                    && stack.peek() == popV[j]) { // 匹配 
                stack.pop(); // 出栈
                j++; // 匹配下一个
            }
        }
        return stack.isEmpty();
    }
}

5.4、最小栈

155. 最小栈 - 力扣（LeetCode）

注意是常数时间。

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

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

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

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

java">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

java">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：浪费一个空间区分队空和队满。

java">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 标记队满。

java">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；元素先入队为空队列，再将不为空队列全部出队，入队到只有栈顶元素的队列中，这样，后续先出队的必是栈顶元素。

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

java">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。否则入不为空的栈。

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

java">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()) { // 倒给栈2
            stack2.push(stack1.pop());
        }
        int head = stack2.pop(); // 栈2的栈顶就是队头元素
        while(!stack2.isEmpty()) { // 倒回给栈1
            stack1.push(stack2.pop());
        }
        return head;
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        while(!stack1.isEmpty()) { // 倒给栈2
            stack2.push(stack1.pop());
        }
        int head = stack2.peek(); // 栈2的栈顶就是队头元素
        while(!stack2.isEmpty()) { // 倒回给栈1
            stack1.push(stack2.pop());
        }
        return head;
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}