Scale Engineer

Implement Stack using Queues

Easy
#0213Time: Push: O(1), Pop/Top: O(n) where n is the number of elements in the stackSpace: O(n) where n is the number of elements in the stack3 companies
Patterns
Design
Data structures
StackQueue
Companies
GoogleOracleDE Shaw

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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.

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

Complexity

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

Trade-offs

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

Solutions

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

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 →

Next problem