算法 004：线性表：栈和队列

数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用。

知识点

栈 - LIFO

栈是一种后进先出（Last In First Out）的线性表，示意图如下（原文图片丢失，据文字重绘）：

flowchart TB
    subgraph stack["栈"]
        direction TB
        top["栈顶 top（入栈 / 出栈都在这一端）"]
        e3["元素 3（最后入栈）"]
        e2["元素 2"]
        e1["元素 1（最先入栈，最后出栈）"]
        bottom["栈底 bottom"]
    end
    in["入栈 push"] --> top
    top --> out["出栈 pop"]

实现上：

使用数组实现的叫静态栈；
使用链表实现的叫动态栈。

队列 - FIFO

队列是一种先进先出（First In First Out）的线性表，示意图如下（原文图片丢失，据文字重绘）：

flowchart LR
    in["入队 offer"] --> rear["队尾 rear"]
    subgraph queue["队列"]
        direction LR
        q1["元素 1"] --> q2["元素 2"] --> q3["元素 3"]
    end
    rear -.-> q3
    q1 -.-> front["队头 front"]
    front --> out["出队 poll"]

实现上：

使用数组实现的叫静态队列；
使用链表实现的叫动态队列。

JDK 中实现

JDK 中关于栈和队列的实现，请参考集合源码 004：Stack & Queue 源码解析。

栈和队列相关题目

用栈实现队列

Implement Queue using Stacks (Easy)

栈的顺序为后进先出，而队列的顺序为先进先出。使用两个栈实现队列，一个元素需要经过两个栈才能出队列，在经过第一个栈时元素顺序被反转，经过第二个栈时再次被反转，此时就是先进先出顺序：

class MyQueue {
    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();

    public void push(int x) {
        in.push(x);
    }

    public int pop() {
        in2out();
        return out.pop();
    }

    public int peek() {
        in2out();
        return out.peek();
    }

    private void in2out() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

用队列实现栈

Implement Stack using Queues (Easy)

在将一个元素 x 插入队列时，为了维护原来的后进先出顺序，需要让 x 插入队列首部。而队列的默认插入顺序是队列尾部，因此在将 x 插入队列尾部之后，需要让除了 x 之外的所有元素出队列，再入队列：

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        int cnt = queue.size();
        while (cnt-- > 1) {
            queue.add(queue.poll());
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

最小值栈

Min Stack (Easy)

用一个数据栈搭配一个最小值栈，两个栈同步压入弹出，最小值栈的栈顶始终是当前数据栈中的最小值：

class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    private int min;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        dataStack.add(x);
        min = Math.min(min, x);
        minStack.add(min);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
        min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

对于实现最小值队列问题，可以先将队列使用栈来实现，然后就将问题转换为最小值栈，这个问题出现在编程之美 3.7。

用栈实现括号匹配

Valid Parentheses (Easy)

Input: "()[]{}"
Output: true

遇到左括号入栈，遇到右括号弹出栈顶并检查是否配对，最后栈为空说明全部匹配：

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char cStack = stack.pop();
            boolean b1 = c == ')' && cStack != '(';
            boolean b2 = c == ']' && cStack != '[';
            boolean b3 = c == '}' && cStack != '{';
            if (b1 || b2 || b3) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

数组中元素与下一个比它大的元素之间的距离

Daily Temperatures (Medium)

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

在遍历数组时用栈把数组中的数（下标）存起来，如果当前遍历的数比栈顶元素来的大，说明栈顶元素的下一个比它大的数就是当前元素——这是典型的单调栈解法：

flowchart TD
    a["遍历到 73，栈空，下标 0 入栈"] --> b["遍历到 74 > 73，弹出 0，dist[0]=1，下标 1 入栈"]
    b --> c["遍历到 75 > 74，弹出 1，dist[1]=1，下标 2 入栈"]
    c --> d["遍历到 71、69，均小于栈顶，依次入栈"]
    d --> e["遍历到 72，依次弹出 69、71 并结算距离，72 入栈"]
    e --> f["遍历到 76，弹出栈内所有更小元素并结算距离"]
    f --> g["遍历到 73，入栈；结束后栈内元素距离为 0"]

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] dist = new int[n];
    Stack<Integer> indexs = new Stack<>();
    for (int curIndex = 0; curIndex < n; curIndex++) {
        while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
            int preIndex = indexs.pop();
            dist[preIndex] = curIndex - preIndex;
        }
        indexs.add(curIndex);
    }
    return dist;
}

循环数组中比当前元素大的下一个元素

Next Greater Element II (Medium)

与 739. Daily Temperatures (Medium) 不同的是，数组是循环数组，并且最后要求的不是距离而是下一个元素。

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.

通过下标取模的方式把循环数组”拉直”，遍历两遍即可：

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] next = new int[n];
    Arrays.fill(next, -1);
    Stack<Integer> pre = new Stack<>();
    for (int i = 0; i < n * 2; i++) {
        int num = nums[i % n];
        while (!pre.isEmpty() && nums[pre.peek()] < num) {
            next[pre.pop()] = num;
        }
        if (i < n) {
            pre.push(i);
        }
    }
    return next;
}

题目与解法复杂度小结

题目	解法思路	时间复杂度	空间复杂度
232. 用栈实现队列	双栈，out 空时一次性导入	均摊 O(1)	O(N)
225. 用队列实现栈	入队后循环旋转	均摊 O(1)	O(N)
155. 最小值栈	数据栈 + 最小值栈同步	O(1)	O(N)
20. 括号匹配	左括号入栈、右括号弹栈配对	O(N)	O(N)
739. 每日温度	单调栈存下标	O(N)	O(N)
503. 下一个更大元素 II	循环数组取模遍历两遍 + 单调栈	O(N)	O(N)

参考文章

系列导航

上一篇：线性表：链表
下一篇：散列表：哈希表
相关篇：LinkedList 源码解析（Deque 的底层实现）、PriorityQueue 源码解析（队列的堆实现）

CHARLIE SAYS