225 - Implement Stack using Queues
Written on November 3, 2015
Tweet
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.
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.pop(0))
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.q.pop(0)
def top(self) -> int:
"""
Get the top element.
"""
return self.q[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.q) == 0
class MyStack {
public:
queue<int> q1;
queue<int> q2;
MyStack() {
}
void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
while (!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
}
int pop() {
int x = q1.front();
q1.pop();
return x;
}
int top() {
return q1.front();
}
bool empty() {
return q1.empty();
}
};