[leetcode] 225. Implement Stack using Queues
原创
文章标签 先进后出 参考文献 先进先出 文章分类 Hadoop 大数据
©著作权归作者所有：来自51CTO博客作者是念的原创作品，请联系作者获取转载授权，否则将追究法律责任
Description
Implement the following operations of a stack using queues.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Example:
MyStack stack = new MyStack();stack.push(1);stack.push(2); stack.top(); // returns 2stack.pop(); // returns 2stack.empty(); // returns false
Notes:
-
You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
-
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
-
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
分析
标题的意思是：用队列实现堆栈的操作。
[En]
The title means: use the queue to realize the operation of the stack.
- 队列先进先出，堆栈先进先出。
[En]
queues are first-in, first-out, while stack is first-in, first-out.*
- 每次在前面插入新添加的数字，这样队列的保存顺序与堆栈的顺序相反，取出的方式也是相反的，所以相反的是我们需要的顺序。
[En]
insert the newly added numbers in front of each time, so that the order in which the queue is saved is the opposite of the order of the stack, and the way they are taken out is also reverse, so the reverse is the order we need.*
- 我们需要一个辅助队列tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素存回来，这样就是我们要的顺序了，其他三个操作也就直接调用队列的操作即可，
代码
class MyStack {private: queue q1;public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { queue tmp; while(!q1.empty()){ tmp.push(q1.front()); q1.pop(); } q1.push(x); while(!tmp.empty()){ q1.push(tmp.front()); tmp.pop(); } } /** Removes the element on top of the stack and returns that element. */ int pop() { int t=top(); q1.pop(); return t; } /** Get the top element. */ int top() { return q1.front(); } /** Returns whether the stack is empty. */ bool empty() { return q1.empty(); }};/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * bool param_4 = obj.empty(); */参考文献
- 赞
- 收藏
- 评论
- *举报
上一篇：[leetcode] 28. Implement strStr()
下一篇：[leetcode] 208. Implement Trie (Prefix Tree)
Original: https://blog.51cto.com/u_9453611/5569063
Author: 是念
Title: [leetcode] 225. Implement Stack using Queues
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/508231/
转载文章受原作者版权保护。转载请注明原作者出处！