225. Implement Stack using Queues
# Easy
Last updated
Was this helpful?
# Easy
Last updated
Was this helpful?
Three methods:
straight froward method: use queue 1 as main storage and queue 2 as helper. Use q2 when do pop()
.
smart method: use two queues, q1 stores all elements except top element, q2 only stores top element.
one queue method: only complicated when doing push()
, change the order to the stack order.
reference:
class MyStack {
public:
/** 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() {
while(q1.size() != 1) {
int tmp = q1.front();
q1.pop();
q2.push(tmp);
}
int res = q1.front();
q1.pop();
while(q2.size() != 0) {
int tmp = q2.front();
q2.pop();
q1.push(tmp);
}
return res;
}
/** Get the top element. */
int top() {
int res = pop();
q1.push(res);
return res;
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
private:
queue<int> q1, q2;
};
/**
* 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();
*/