当前位置:网站首页>队列题目:用队列实现栈
队列题目:用队列实现栈
2022-08-09 18:26:00 【伟大的车尔尼】
题目
标题和出处
标题:用队列实现栈
出处:225. 用队列实现栈
难度
4 级
题目描述
要求
请你仅使用两个队列实现一个后进先出的栈。实现的栈应该支持普通栈的全部操作( push \texttt{push} push、 pop \texttt{pop} pop、 top \texttt{top} top 和 empty \texttt{empty} empty)。
实现 MyStack \texttt{MyStack} MyStack 类:
- void push(int x) \texttt{void push(int x)} void push(int x) 将元素 x \texttt{x} x 压入栈顶。
- int pop() \texttt{int pop()} int pop() 移除并返回栈顶元素。
- int top() \texttt{int top()} int top() 返回栈顶元素。
- boolean empty() \texttt{boolean empty()} boolean empty() 如果栈是空的,返回 true \texttt{true} true;否则,返回 false \texttt{false} false。
注意:
- 你只能使用队列的基本操作,只有在队尾添加元素、在队首查看和删除元素、返回元素个数和判断是否为空的操作是有效的。
- 你所使用的语言也许不支持队列。你可以使用列表或者双端队列来模拟一个队列,只要所有的操作都是标准的队列操作即可。
示例
示例 1:
输入:
["MyStack", "push", "push", "top", "pop", "empty"] \texttt{["MyStack", "push", "push", "top", "pop", "empty"]} ["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []] \texttt{[[], [1], [2], [], [], []]} [[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false] \texttt{[null, null, null, 2, 2, false]} [null, null, null, 2, 2, false]
解释:
MyStack myStack = new MyStack(); \texttt{MyStack myStack = new MyStack();} MyStack myStack = new MyStack();
myStack.push(1); \texttt{myStack.push(1);} myStack.push(1);
myStack.push(2); \texttt{myStack.push(2);} myStack.push(2);
myStack.top(); \texttt{myStack.top();} myStack.top(); // 返回 2 \texttt{2} 2
myStack.pop(); \texttt{myStack.pop();} myStack.pop(); // 返回 2 \texttt{2} 2
myStack.empty(); \texttt{myStack.empty();} myStack.empty(); // 返回 False \texttt{False} False
数据范围
- 1 ≤ x ≤ 9 \texttt{1} \le \texttt{x} \le \texttt{9} 1≤x≤9
- 最多调用 100 \texttt{100} 100 次 push \texttt{push} push、 pop \texttt{pop} pop、 top \texttt{top} top 和 empty \texttt{empty} empty
- 每次调用 pop \texttt{pop} pop 和 top \texttt{top} top 都是有效的
进阶
你能否仅使用一个队列实现栈?
解法一
思路和算法
由于栈的特点是后进先出,因此使用队列实现栈时,需要维护队列内的元素顺序,使得队首元素是最后入队的元素。
使用两个队列实现时, queue 1 \textit{queue}_1 queue1 的作用是存储元素, queue 2 \textit{queue}_2 queue2 的作用是辅助操作。
为了实现栈的功能,需要保证每次入栈操作之后, queue 1 \textit{queue}_1 queue1 的队首元素总是新添加的元素。因此入栈操作如下:
将待添加的元素入队到 queue 2 \textit{queue}_2 queue2;
将 queue 1 \textit{queue}_1 queue1 的全部元素依次出队并入队到 queue 2 \textit{queue}_2 queue2;
将 queue 1 \textit{queue}_1 queue1 和 queue 2 \textit{queue}_2 queue2 互换。
完成上述操作后, queue 2 \textit{queue}_2 queue2 为空, queue 1 \textit{queue}_1 queue1 的队首元素是新添加的元素, queue 1 \textit{queue}_1 queue1 内的其余元素和顺序不变。因此上述操作的效果是在 queue 1 \textit{queue}_1 queue1 的队首增加了新添加的元素, queue 1 \textit{queue}_1 queue1 的队首和队尾分别对应栈顶和栈底。
由于每次入栈操作都维护了 queue 1 \textit{queue}_1 queue1 内的元素顺序,因此出栈操作和查看栈顶元素操作可以简单实现。出栈操作只需要将 queue 1 \textit{queue}_1 queue1 的队首元素移除并返回即可,查看栈顶元素操作只需要返回 queue 1 \textit{queue}_1 queue1 的队首元素即可。
由于 queue 1 \textit{queue}_1 queue1 的作用是存储元素,因此判断栈是否为空操作只需要判断 queue 1 \textit{queue}_1 queue1 是否为空即可。
代码
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new ArrayDeque<Integer>();
queue2 = new ArrayDeque<Integer>();
}
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
复杂度分析
时间复杂度:构造方法的时间复杂度是 O ( 1 ) O(1) O(1),入栈操作的时间复杂度是 O ( n ) O(n) O(n),出栈、查看栈顶元素和判断栈是否为空操作的时间复杂度都是 O ( 1 ) O(1) O(1),其中 n n n 是栈内元素个数。
入栈操作需要将 queue 1 \textit{queue}_1 queue1 的 n n n 个元素出队,并将 n + 1 n + 1 n+1 个元素入队到 queue 2 \textit{queue}_2 queue2,共有 2 n + 1 2n + 1 2n+1 次操作,每次出队和入队操作的时间复杂度都是 O ( 1 ) O(1) O(1),因此入栈操作的时间复杂度是 O ( n ) O(n) O(n)。
出栈、查看栈顶元素和判断栈是否为空操作都是常规队列操作,时间复杂度都是 O ( 1 ) O(1) O(1)。空间复杂度: O ( n ) O(n) O(n),其中 n n n 是栈内元素个数。需要使用队列存储元素。
解法二
思路和算法
也可以使用一个队列实现栈。
使用一个队列实现时,同样需要维护队列内的元素顺序,使得队首元素是最后入队的元素,因此需要保证每次入栈操作之后,队首元素总是新添加的元素。
使用一个队列实现的入栈操作和使用两个队列实现的入栈操作有所区别,由于只有一个队列,所有的元素都需要存储在队列内。入栈操作如下:
计算队列内的元素个数 size \textit{size} size;
将待添加的元素入队;
将队列内的前 size \textit{size} size 个元素依次出队并入队。
完成上述操作后,队首元素是新添加的元素,队列内的其余元素和顺序不变。因此上述操作的效果是在队首增加了新添加的元素,队首和队尾分别对应栈顶和栈底。
出栈操作、查看栈顶元素操作和判断栈是否为空操作和解法一相同,只需要在队列上执行相应操作即可。
代码
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new ArrayDeque<Integer>();
}
public void push(int x) {
int size = queue.size();
queue.offer(x);
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
复杂度分析
时间复杂度:构造方法的时间复杂度是 O ( 1 ) O(1) O(1),入栈操作的时间复杂度是 O ( n ) O(n) O(n),出栈、查看栈顶元素和判断栈是否为空操作的时间复杂度都是 O ( 1 ) O(1) O(1),其中 n n n 是栈内元素个数。
入栈操作需要将队列的 n n n 个元素出队,并将 n + 1 n + 1 n+1 个元素入队,共有 2 n + 1 2n + 1 2n+1 次操作,每次出队和入队操作的时间复杂度都是 O ( 1 ) O(1) O(1),因此入栈操作的时间复杂度是 O ( n ) O(n) O(n)。
出栈、查看栈顶元素和判断栈是否为空操作都是常规队列操作,时间复杂度都是 O ( 1 ) O(1) O(1)。空间复杂度: O ( n ) O(n) O(n),其中 n n n 是栈内元素个数。需要使用队列存储元素。
边栏推荐
猜你喜欢
Samsung's flagship discount is 1,800, Apple's discount is over 1,000, and the domestic flagship is only reduced by 500 to send beggars
YOLO v3源码详解
字节二面,差点倒在了MySQL上面
论文精读:VIT - AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE
2021 RoboCom 世界机器人开发者大赛-本科组(决赛)
2022深圳(软考高级)信息系统项目管理师认证报名
国产抗新冠口服药每瓶不超300元/ 我国IPv6网络全面建成/ 谷歌入局折叠屏手机...今日更多新鲜事在此...
说了半天跨平台,今儿咱就来跨跨!(完结篇)——Kubenetes上手实践
没有 accept,TCP 连接可以建立成功吗?
C#/VB.NET: Extract text and pictures from PowerPoint document
随机推荐
An overview of Office 365 Groups and how to create them
2022 RoboCom 世界机器人开发者大赛-本科组(省赛)-RC-u5 树与二分图
Leetcode 739.每日温度 单调栈
AWS CodePipeLine deploys ECS across accounts
优秀的 Verilog/FPGA开源项目介绍(三十一)- OFDM
MQTT X Web:在线的 MQTT 5.0 客户端工具
Office 365 Group概述以及创建方法
5.3.6 原子操作对非原子的操作排序
宝塔面板安装使用
与同步传递相关的获取-释放序列
关于加强专业学位研究生课程体系建设的意见
Mysql table structure change scheme comparison and analysis
面试官:当Redis大的时候,要如何处理key?
VIT transformer详解
21天学习挑战赛--第四天打卡(横竖屏切换)
Start cleaning up the long-term divers in the electronic chart development group again
[免费专栏] Android安全之动态代码注入技术(利用JDB调试APK)
Ros简介
五种常用的排序方法
Tims中国上市进入倒计时:年亏3.8亿 估值降至14亿美元