剑指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:# 入队时直接将元素压入 stack1self.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:// 入队操作，将元素压入 stack1void push(int x) {stack1.push(x);}// 出队操作，实现队列的先进先出int pop() {// 如果 stack2 为空，将 stack1 中的元素依次弹出并压入 stack2if (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;
};