## # 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):
"""
"""
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;
*/
// 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();
/*
// Two Queues, push - O(n), pop O(1).
// One Queues, push - O(n), pop O(1).
int top = q1.front();
q1.pop();
*/
}

/** 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();
*/
``````