剑指Offer 队列&栈题目集合

用两个栈实现队列

刷题链接：
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6

题目描述

思路一：
使用两个栈来实现队列的功能。栈 1 用于存储入队的元素，而栈 2 用于存储出队的元素。
1.push方法将元素压入栈 1。
2.pop方法首先检查栈 2 是否为空。如果为空，则将栈 1 中的所有元素移到栈 2。然后，弹出栈 2 中的顶部元素并返回。

复杂度分析

时间复杂度：在最坏情况下，pop 操作的时间复杂度是 O(n)，但在平均情况下，当栈2中有元素时，pop 操作的时间复杂度是 O(1)。这是因为在平均情况下，元素不会每次都从栈1移动到栈2。总体而言，这个实现的 push 操作是 O(1)，而 pop 操作的最坏情况下是 O(n)，平均情况下是 O(1)。
空间复杂度： O(n)，辅助栈的空间，最差的情况下两个栈共存储N个元素。

python3

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        # 入队时直接将元素压入 stack1
        self.stack1.append(x)

    def pop(self) -> int:
        # 如果 stack2 为空，将 stack1 中的元素依次弹出并压入 stack2，实现队列的先进先出
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        # 弹出 stack2 的栈顶元素，即队列头部的元素
        return self.stack2.pop()

C++

class Solution {
  public:
    // 入队操作，将元素压入 stack1
    void push(int x) {
        stack1.push(x);
    }

    // 出队操作，实现队列的先进先出
    int pop() {
        // 如果 stack2 为空，将 stack1 中的元素依次弹出并压入 stack2
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        // 弹出 stack2 的栈顶元素，即队列头部的元素
        int frontElement = stack2.top();
        stack2.pop();
        return frontElement;
    }

  private:
    stack<int> stack1;
    stack<int> stack2;
};