校园网站平台建设,中英文网站英文,广州知名网站建设有哪些,国内购物网站排名目录 用两个栈实现队列 用两个栈实现队列
刷题链接#xff1a; https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6
题目描述
思路一#xff1a; 使用两个栈来实现队列的功能。栈 1 用于存储入队的元素#xff0c;而栈 2 用于存储出队的元素。 1.push… 目录 用两个栈实现队列 用两个栈实现队列
刷题链接 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:stackint stack1;stackint stack2;
};
