Implement Queue using Stacks

Easy

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

Patterns

Design

Data structures

Stack Queue

Companies

Infosys Oracle Qualcomm Netflix

Prompt

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

2 approaches with complexity analysis and trade-offs.

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

Walkthrough

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:

1class MyQueue {2    private Stack<Integer> input;3    private Stack<Integer> output;4 5    public MyQueue() {6        input = new Stack<>();7        output = new Stack<>();8    }9    10    public void push(int x) {11        input.push(x);12    }13    14    public int pop() {15        peek();16        return output.pop();17    }18    19    public int peek() {20        if (output.empty()) {21            while (!input.empty()) {22                output.push(input.pop());23            }24        }25        return output.peek();26    }27    28    public boolean empty() {29        return input.empty() && output.empty();30    }31}

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

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

Trade-offs

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

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.

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

Walkthrough

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:

Pushed once to the input stack (during push operation)
Popped once from input stack and pushed to output stack (during transfer)
Popped once from output stack (during pop operation)

Here's the implementation:

1class MyQueue {2    private Stack<Integer> input;3    private Stack<Integer> output;4 5    public MyQueue() {6        input = new Stack<>();7        output = new Stack<>();8    }9    10    public void push(int x) {11        input.push(x);12    }13    14    public int pop() {15        peek();16        return output.pop();17    }18    19    public int peek() {20        if (output.empty()) {21            while (!input.empty()) {22                output.push(input.pop());23            }24        }25        return output.peek();26    }27    28    public boolean empty() {29        return input.empty() && output.empty();30    }31}

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.

Complexity

Time

Amortized O(1) for all operations (push, pop, peek)

Space

O(n) where n is the number of elements in the queue

Trade-offs

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

Solutions

Solution

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

1class 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()

1// 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 (); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem