Implement Queue using Stacks

EASY

Description

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

Checkout 2 different approaches to solve Implement Queue using Stacks. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Initialize two stacks: input and output
For push(x):
- Push x to input stack
For pop():
- If output is empty, transfer all elements from input to output
- Pop and return top element from output
For peek():
- If output is empty, transfer all elements from input to output
- Return top element from output
For empty():
- Return true if both stacks are empty

In this approach, we maintain two stacks:

Input stack: Used for pushing new elements
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:

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.

Complexity Analysis

Time Complexity: Push: O(1), Pop/Peek: O(n) in worst case when output stack is emptySpace Complexity: O(n) where n is the number of elements in the queue

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Implement Queue using Stacks. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Implement Queue using Stacks

Patterns:

Design

Data Structures:

StackQueue

Companies:

Infosys |Oracle |Qualcomm |Netflix |