【LeetCode】-- 225. 用队列实现栈

简介: 【LeetCode】-- 225. 用队列实现栈

1. 题目

225. 用队列实现栈 - 力扣(LeetCode)

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

       void push(int x) 将元素 x 压入栈顶。

       int pop() 移除并返回栈顶元素。

       int top() 返回栈顶元素。

       boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

注意:

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

2. 示例

输入:

       ["MyStack", "push", "push", "top", "pop", "empty"]

       [[], [1], [2], [], [], []]

输出:

       [null, null, null, 2, 2, false]

说明:  

       MyStack myStack = new MyStack();

       myStack.push(1);

       myStack.push(2);

       myStack.top(); // 返回 2

       myStack.pop(); // 返回 2

       myStack.empty(); // 返回 False

3. 分析

(1)栈的性质,后进先出,当用两个队列模拟栈时,要达到后进先出的效果

(2)入栈时,要入到不为空的队列中

(3)出栈时,为了保证出非空队列中最后一个元素,得先把其他元素全部存放到另一个队列中,再出非空队列的最后一个元素,这样就能保证再入栈时,将元素入到不为空的队列中,保证进栈顺序一致

 

(4)返回栈顶元素,栈顶元素其实就是队尾元素

(5)栈判空,两个队列同时为空则栈为空

4. 代码实现

1. class MyStack {
2. public:
3. MyStack() {
4.    //构造函数不用对q1和q2初始化,会调用queue的默认构造函数进行初始化
5.     }
6. 
7. void push(int x) {
8.    //入栈时,向非空队列入栈
9. if(!_q1.empty())
10.         {
11.             _q1.push(x);
12.         }
13. else
14.         {
15.             _q2.push(x);
16.         }
17.     }
18. 
19. 
20. int pop() {
21.     //出栈时,由于队列先进先出,前面的元素挡着最后一个元素(栈顶元素),先把前面元素挪到非空队列中
22.         queue<int>* empty = &_q1;
23.         queue<int>* nonEmpty = &_q2;
24. 
25.     //确定哪个队列为空,哪个队列非空
26. if(!_q1.empty())
27.         {
28. swap(empty,nonEmpty);
29.         }
30. 
31.     //把除栈顶元素之外的所有元素都挪到非空队列
32. while(nonEmpty->size()>1)
33.         {
34.             empty->push(nonEmpty->front());
35.             nonEmpty->pop();
36.         }
37. 
38.     //返回栈顶元素
39. int top = nonEmpty->front();//现在非空队列只剩下最后一个元素了
40.         nonEmpty->pop();//出最后一个元素也就是出栈顶元素
41. return top;
42.     }
43. 
44. int top() {
45.     //返回非空队列的队尾元素
46. if(!_q1.empty())
47.         {
48. return _q1.back();
49.         } 
50. else
51.         {
52. return _q2.back();
53.         } 
54.     }
55. 
56. bool empty() {
57.     //q1和q2同时为空时栈才为空
58. return _q1.empty() && _q2.empty();
59.     }
60. private:
61.     queue<int> _q1;
62.     queue<int> _q2;
63. };
64. 
65. /**
66.  * Your MyStack object will be instantiated and called as such:
67.  * MyStack* obj = new MyStack();
68.  * obj->push(x);
69.  * int param_2 = obj->pop();
70.  * int param_3 = obj->top();
71.  * bool param_4 = obj->empty();
72.  */


相关文章
|
3天前
|
存储 算法 数据可视化
力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)
力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)
|
3天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
3天前
|
存储 SQL 算法
LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历
LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历
|
3天前
|
SQL 算法 数据挖掘
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
|
17天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
17 0
|
23天前
|
机器学习/深度学习 存储 算法
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)(下)
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)
6 0
|
23天前
|
算法 前端开发 C语言
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)(上)
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)
13 0
|
23天前
|
缓存 算法 C语言
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)
8 0
|
29天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
12 0
|
29天前
|
C语言
Leetcode每日一题——“用栈实现队列”
Leetcode每日一题——“用栈实现队列”