题解 | 用两个栈实现队列

1、解题思路

1. 栈的特性：后进先出（LIFO）。
2. 队列的特性：先进先出（FIFO）。
3. 双栈实现队列 ：Push 操作：直接压入 stack1。Pop 操作 ：如果 stack2 为空，则将 stack1 中的所有元素依次弹出并压入 stack2，此时 stack2 的栈顶元素即为队列的头部元素。如果 stack2 不为空，则直接弹出 stack2 的栈顶元素。

2、代码实现

C++

class Solution {
  public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int node = stack2.top();
        stack2.pop();
        return node;
    }

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

Java

import java.util.*;
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

Python

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

    def push(self, node):
        # write code here
        self.stack1.append(node)

    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

3、复杂度分析

1. 空间复杂度：O(n)，存储所有元素。
2. 时间复杂度： push：O(1)。pop：均摊 O(1)。