Implement the following operations of a queue using stacks.
- push(x) — Push element x to the back of queue.
- pop() — Removes the element from in front of queue.
- peek() — Get the front element.
- empty() — Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false
Notes:
- You must use only standard operations of a stack — which means only
push to top
,peek/pop from top
,size
, andis empty
operations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
Solution: Use two stacks
amortized cost: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class MyQueue { public: /** Initialize your data structure here. */ MyQueue() {} /** Push element x to the back of queue. */ void push(int x) { s1_.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { if (s2_.empty()) move(); int top = s2_.top(); s2_.pop(); return top; } /** Get the front element. */ int peek() { if (s2_.empty()) move(); return s2_.top(); } /** Returns whether the queue is empty. */ bool empty() { return s1_.empty() && s2_.empty(); } private: stack<int> s1_; stack<int> s2_; void move() { while (!s1_.empty()) { s2_.push(s1_.top()); s1_.pop(); } } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment