# Implement Stack using Queues
**Difficulty:** EASY
[External](https://leetcode.com/problems/implement-stack-using-queues)
Canonical: https://scaleengineer.com/dsa/problems/implement-stack-using-queues
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Stack, Queue
**Companies:** [Google](https://scaleengineer.com/companies/google), [Oracle](https://scaleengineer.com/companies/oracle), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (`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()` Returns `true` if the stack is empty, `false` otherwise.

**Notes:**

* You must use **only** standard operations of a queue, which means that only `push to back`, `peek/pop from front`, `size` and `is 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.

**Example 1:**

**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

**Constraints:**

* `1 <= x <= 9`
* At most `100` calls will be made to `push`, `pop`, `top`, and `empty`.
* All the calls to `pop` and `top` are valid.

**Follow-up:** Can you implement the stack using only one queue?

# Approaches
## Two Queues Approach - Push Efficient
This approach uses two queues to implement a stack. The main idea is to keep one queue as the main storage and use the second queue as temporary storage during pop operations.
**Time:** Push: O(1), Pop/Top: O(n) where n is the number of elements in the stack · **Space:** O(n) where n is the number of elements in the stack
**Pros:** Push operation is O(1); Implementation is straightforward; Memory usage is proportional to the number of elements
**Cons:** Pop and Top operations are inefficient O(n); Requires two queues; Extra space needed for temporary storage during operations
### Explanation
In this approach, we maintain two queues: q1 and q2. The push operation is straightforward - we simply add elements to q1. For pop operations, we move all elements except the last one from q1 to q2, get the last element from q1, and then swap q1 and q2.

```java
class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        q1.offer(x);
    }
    
    public int pop() {
        // Move all elements except last from q1 to q2
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        
        // Get the last element
        int result = q1.poll();
        
        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        
        return result;
    }
    
    public int top() {
        // Move all elements except last from q1 to q2
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        
        // Get the last element
        int result = q1.peek();
        
        // Move the last element to q2
        q2.offer(q1.poll());
        
        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
        
        return result;
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}
```
### Algorithm
1. Initialize two queues q1 and q2
2. For push operation:
   - Add element to q1
3. For pop operation:
   - Move all elements except last from q1 to q2
   - Get and remove the last element from q1
   - Swap q1 and q2
4. For top operation:
   - Similar to pop but return the last element without removing
5. For empty operation:
   - Check if q1 is empty

## Single Queue Approach
This approach uses only one queue to implement a stack. The main idea is to reorder the elements after each push operation to maintain stack order.
**Time:** Push: O(n), Pop/Top: O(1) where n is the number of elements in the stack · **Space:** O(n) where n is the number of elements in the stack
**Pros:** Uses only one queue; Pop and Top operations are O(1); Less space overhead compared to two-queue approach
**Cons:** Push operation is inefficient O(n); Requires reordering of elements after each push; May not be suitable for large number of push operations
### Explanation
In this approach, we use a single queue. When pushing a new element, we first add it to the queue, then we rotate the queue by moving all elements except the newly added one to the back of the queue. This ensures that the newest element is always at the front of the queue.

```java
class MyStack {
    private Queue<Integer> queue;
    
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.offer(x);
        // Rotate the queue to move the new element to front
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}
```
### Algorithm
1. Initialize one queue
2. For push operation:
   - Add new element to queue
   - Rotate queue by moving all elements except the new one to the back
3. For pop operation:
   - Simply remove and return the front element
4. For top operation:
   - Return the front element without removing
5. For empty operation:
   - Check if queue is empty

# Solutions
### Java

```java
import java.util.Deque ; class MyStack { private Deque < Integer > q1 = new ArrayDeque <>(); private Deque < Integer > q2 = new ArrayDeque <>(); public MyStack () { } public void push ( int x ) { q2 . offer ( x ); while (! q1 . isEmpty ()) { q2 . offer ( q1 . poll ()); } Deque < Integer > q = q1 ; q1 = q2 ; q2 = q ; } public int pop () { return q1 . poll (); } public int top () { return q1 . peek (); } public boolean empty () { return q1 . isEmpty (); } } /** * 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(); * boolean param_4 = obj.empty(); */
```

### CPP

```cpp
class MyStack { public: MyStack () { } void push ( int x ) { q2 . push ( x ); while ( ! q1 . empty ()) { q2 . push ( q1 . front ()); q1 . pop (); } swap ( q1 , q2 ); } int pop () { int x = q1 . front (); q1 . pop (); return x ; } int top () { return q1 . front (); } bool empty () { return q1 . empty (); } private: queue < int > q1 ; queue < int > 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(); */
```

### Python

```python
# one queue ''' push(1), [1] push(2), [1,2] => [2,1] push(3), [2,1,3] => [1,3,2] => [3,2,1] push(4), [3,2,1,4] => switch 3 time to get [4,3,2,1] push(5), [4,3,2,1,5] => switch 4 time to get [5,4,3,2,1] ''' class Stack : def __init__ ( self ): self . _queue = collections . deque () def push ( self , x ): q = self . _queue q . append ( x ) for _ in range ( len ( q ) - 1 ): q . append ( q . popleft ()) def pop ( self ): return self . _queue . popleft () def top ( self ): return self . _queue [ 0 ] def empty ( self ): return not len ( self . _queue ) # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty() ############ from collections import deque # two queues class MyStack : def __init__ ( self ): self . q1 = deque () self . q2 = deque () def push ( self , x : int ) -> None : self . q1 . append ( x ) def pop ( self ) -> int : while len ( self . q1 ) != 1 : self . q2 . append ( self . q1 . popleft ()) val = self . q1 . popleft () self . q1 , self . q2 = self . q2 , self . q1 return val def top ( self ) -> int : while len ( self . q1 ) != 1 : self . q2 . append ( self . q1 . popleft ()) # tried to re-use while part, but seems not achievable, since val is retrieved in-between val = self . q1 [ 0 ] self . q2 . append ( self . q1 . popleft ()) # note: add back to q2, so q1 will always be empty self . q1 , self . q2 = self . q2 , self . q1 return val def empty ( self ) -> bool : return not self . q1 # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
```