Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push
, top
, pop
, and empty
).
Implement the MyStack
class:
-
void push(int x)
Pushes element x to the top of the stack. -
int pop()
Removes the element on the top of the stack and returns it. -
int top()
Returns the element on the top of the stack. -
boolean empty()
Returnstrue
if the stack is empty,false
otherwise.
Notes:
- You must use only standard operations of a queue, which means only
push to back
,peek/pop from front
,size
, andis empty
operations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue), as long as you use only a queue's standard operations.
Follow-up: Can you implement the stack such that each operation is amortized O(1)
time complexity? In other words, performing n
operations will take overall O(n)
time even if one of those operations may take longer.
Example 1:
<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: var(--dark-bg); border-color: rgb(51, 51, 51); color: var(--font) !important; padding: 10px 15px; line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
</pre>
Constraints:
1 <= x <= 9
- At most
100
calls will be made topush
,pop
,top
, andempty
. - All the calls to
pop
andtop
are valid.
class MyStack {
public:
queue<int> q1;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
q1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
queue<int> q2;
while (q1.size() > 1) {
q2.push(q1.front());
q1.pop();
}
int ans = q1.front();
q1 = q2;
return ans;
}
/** Get the top element. */
int top() {
return q1.back();
}
/** 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();
*/
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Implement Stack using Queues.
Memory Usage: 7.3 MB, less than 13.87% of C++ online submissions for Implement Stack using Queues.
网友评论