# 225. Implement Stack using Queues
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 2
stack.pop(); // returns 2
stack.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).
# Solution
Approach 1: One queue or two queues.
# Code (Python)
Approach 1:
from collections import deque
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = deque([])
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.queue.append(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
for i in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
return self.queue.popleft()
def top(self) -> int:
"""
Get the top element.
"""
for i in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
val = self.queue.popleft()
self.queue.append(val)
return val
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.queue) == 0
# Code (C++)
Approach 1:
class MyStack {
private:
queue<int> q1;
queue<int> q2;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
// Two Queues, push - O(1), pop O(n).
// One Queues, push - O(1), pop O(n).
q1.push(x);
/*
// Two Queues, push - O(n), pop O(1).
q2.push(x);
while (!q1.empty())
{
q2.push(q1.front());
q1.pop();
}
queue<int> tmp = q1;
q1 = q2;
q2 = tmp;
*/
/*
// One Queues, push - O(n), pop O(1).
int q1Size = q1.size();
q1.push(x);
for (int i = 0; i< q1Size; ++i)
{
q1.push(q1.front());
q1.pop();
}
*/
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
/*
// Two Queues, push - O(1), pop O(n).
while (q1.size() > 1)
{
q2.push(q1.front());
q1.pop();
}
int top = q1.front();
q1.pop();
queue<int> tmp = q1;
q1 = q2;
q2 = tmp;
return top;
*/
// One Queues, push - O(1), pop O(n).
int q1Size = q1.size();
for (int i = 0; i < q1Size - 1; ++i)
{
q1.push(q1.front());
q1.pop();
}
int top = q1.front();
q1.pop();
return top;
/*
// Two Queues, push - O(n), pop O(1).
// One Queues, push - O(n), pop O(1).
int top = q1.front();
q1.pop();
return top;
*/
}
/** Get the top element. */
int top() {
// Two Queues, push - O(1), pop O(n).
// One Queues, push - O(n), pop O(1).
return q1.back();
/*
// Two Queues, push - O(n), pop O(1).
// One Queues, push - O(n), pop O(1).
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();
*/