# Implement Queue using Stacks
**Difficulty:** EASY
[External](https://leetcode.com/problems/implement-queue-using-stacks)
Canonical: https://scaleengineer.com/dsa/problems/implement-queue-using-stacks
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Stack, Queue
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Netflix](https://scaleengineer.com/companies/netflix)
---
## Problem
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (`push`, `peek`, `pop`, and `empty`).

Implement the `MyQueue` class:

* `void push(int x)` Pushes element x to the back of the queue.
* `int pop()` Removes the element from the front of the queue and returns it.
* `int peek()` Returns the element at the front of the queue.
* `boolean empty()` Returns `true` if the queue is empty, `false` otherwise.

**Notes:**

* You must use **only** standard operations of a stack, which means only `push to top`, `peek/pop from top`, `size`, and `is empty` operations are valid.
* Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

**Example 1:**

**Input**
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
**Output**
[null, null, null, 1, 1, false]

**Explanation**
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

**Constraints:**

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

**Follow-up:** Can you implement the queue such that each operation is **[amortized](https://en.wikipedia.org/wiki/Amortized%5Fanalysis)** `O(1)` time complexity? In other words, performing `n` operations will take overall `O(n)` time even if one of those operations may take longer.

# Approaches
## Two Stacks with Push O(1) and Pop O(n)
Use two stacks - one for pushing elements (input stack) and another for popping elements (output stack). Push operation is straightforward, while pop operation requires transferring elements between stacks.
**Time:** Push: O(1), Pop/Peek: O(n) in worst case when output stack is empty · **Space:** O(n) where n is the number of elements in the queue
**Pros:** Simple implementation; Push operation is O(1); Space efficient as elements are stored only once
**Cons:** Pop and peek operations can be O(n) in worst case; Not optimal for frequent pop operations
### Explanation
In this approach, we maintain two stacks:
1. Input stack: Used for pushing new elements
2. Output stack: Used for popping and peeking elements

When pushing an element, we simply add it to the input stack. For pop and peek operations, if the output stack is empty, we transfer all elements from input stack to output stack (reversing their order in the process). This ensures the first-in-first-out property of the queue.

Here's the implementation:

```java
class MyQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    public void push(int x) {
        input.push(x);
    }
    
    public int pop() {
        peek();
        return output.pop();
    }
    
    public int peek() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }
    
    public boolean empty() {
        return input.empty() && output.empty();
    }
}
```

When we need to pop or peek and the output stack is empty, we transfer all elements from input to output stack. This reverses their order, making the first-pushed element available at the top of output stack.
### Algorithm
1. Initialize two stacks: input and output
2. For push(x):
   - Push x to input stack
3. For pop():
   - If output is empty, transfer all elements from input to output
   - Pop and return top element from output
4. For peek():
   - If output is empty, transfer all elements from input to output
   - Return top element from output
5. For empty():
   - Return true if both stacks are empty

## Optimized Two Stacks with Amortized O(1) Operations
Similar to the previous approach but with amortized time complexity analysis. Each element is pushed and popped exactly once from each stack, making the amortized time complexity O(1) for all operations.
**Time:** Amortized O(1) for all operations (push, pop, peek) · **Space:** O(n) where n is the number of elements in the queue
**Pros:** Amortized O(1) time complexity for all operations; Efficient for both push and pop operations; Space efficient as elements are stored only once
**Cons:** Individual pop operations can still take O(n) time in worst case; Requires understanding of amortized analysis for performance guarantees
### Explanation
This approach uses the same implementation as the previous one, but we analyze it differently. While a single pop operation might take O(n) time when we need to transfer elements, subsequent pop operations will be O(1) until the output stack is empty again.

The key insight is that each element is:
1. Pushed once to the input stack (during push operation)
2. Popped once from input stack and pushed to output stack (during transfer)
3. Popped once from output stack (during pop operation)

Here's the implementation:

```java
class MyQueue {
    private Stack<Integer> input;
    private Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    public void push(int x) {
        input.push(x);
    }
    
    public int pop() {
        peek();
        return output.pop();
    }
    
    public int peek() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }
    
    public boolean empty() {
        return input.empty() && output.empty();
    }
}
```

The amortized analysis shows that for n operations, we perform at most 3n stack operations (push/pop), making the amortized cost O(1) per operation.
### Algorithm
1. Initialize two stacks: input and output
2. For push(x):
   - Push x to input stack
3. For pop():
   - If output is empty, transfer all elements from input to output
   - Pop and return top element from output
4. For peek():
   - If output is empty, transfer all elements from input to output
   - Return top element from output
5. For empty():
   - Return true if both stacks are empty

# Solutions
### Java

```java
public class Implement_Queue_using_Stacks { class MyQueue { private Stack < Integer > stack1 ; private Stack < Integer > stack2 ; public MyQueue () { this . stack1 = new Stack < Integer >(); this . stack2 = new Stack < Integer >(); } // Push element x to the back of queue. public void push ( int x ) { stack1 . push ( x ); } // Removes the element from in front of queue. public int pop () { if (! stack2 . isEmpty ()) { return stack2 . pop (); // stack is queue-order, queue-head at this-stack-top } else { while (! stack1 . isEmpty ()) { stack2 . push ( stack1 . pop ()); } return stack2 . pop (); } } // Get the front element. public int peek () { int ret = 0 ; if (! stack2 . isEmpty ()) { ret = stack2 . peek (); } else { while (! stack1 . isEmpty ()) { stack2 . push ( stack1 . pop ()); } ret = stack2 . peek (); } return ret ; } // Return whether the queue is empty. public boolean empty () { return stack1 . isEmpty () && stack2 . isEmpty (); } } } ############ class MyQueue { private Deque < Integer > stk1 = new ArrayDeque <>(); private Deque < Integer > stk2 = new ArrayDeque <>(); public MyQueue () { } public void push ( int x ) { stk1 . push ( x ); } public int pop () { move (); return stk2 . pop (); } public int peek () { move (); return stk2 . peek (); } public boolean empty () { return stk1 . isEmpty () && stk2 . isEmpty (); } private void move () { while ( stk2 . isEmpty ()) { while (! stk1 . isEmpty ()) { stk2 . push ( stk1 . pop ()); } } } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
```

### Python

```python
class MyQueue : def __init__ ( self ): self . stk1 = [] self . stk2 = [] # reversed order def push ( self , x : int ) -> None : self . stk1 . append ( x ) def pop ( self ) -> int : self . move () return self . stk2 . pop () def peek ( self ) -> int : self . move () return self . stk2 [ - 1 ] def empty ( self ) -> bool : return not self . stk1 and not self . stk2 def move ( self ): if not self . stk2 : # only when skt2 is empty while self . stk1 : self . stk2 . append ( self . stk1 . pop ()) # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty() ############ class MyQueue : def __init__ ( self ): self . sk = [] self . rsk = [] # reversed def push ( self , x : int ) -> None : self . sk . append ( x ); def pop ( self ) -> int : self . peek () return self . rsk . pop () def peek ( self ) -> int : if self . rsk : return self . rsk [ - 1 ] else : while self . sk : self . rsk . append ( self . sk . pop ()) return self . rsk [ - 1 ] def empty ( self ) -> bool : return not ( self . sk or self . rsk ) # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/implement-queue-using-stacks // Time: O(1) amortized. // Space: O(1) class MyQueue { stack < int > in , out ; public: MyQueue () {} void push ( int x ) { in . push ( x ); } int pop () { int val = peek (); out . pop (); return val ; } int peek () { if ( out . empty ()) { while ( in . size ()) { out . push ( in . top ()); in . pop (); } } return out . top (); } bool empty () { return in . empty () && out . empty (); } };
```