Implement Stack using Queues (LC 225)

Implement a stack using two queues with O(1) amortized time complexity for all operations.

Language Selection

Choose your preferred programming language

Showing: Python

Implement Stack using Queues

Problem Statement

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 onto the stack
  • int pop() Removes the element on top of the stack and returns it
  • int top() Returns the element on top of the stack
  • boolean empty() Returns true if the stack is empty, false otherwise

Examples

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

Approach 1: Two Queues (Costly Push)

Algorithm

A queue is first-in-first-out, so to make it behave like a stack the newest element must always sit at the front. Keep the stack in outputQueue with the top element at its front, and use inputQueue as scratch space.

Steps:

  1. push(x): add x to the empty inputQueue
  2. Move every element of outputQueue behind it, preserving their order
  3. Swap the two queues, so outputQueue now holds the new element at the front followed by the older ones
  4. pop and top read the front of outputQueue, and empty checks whether it is empty

Implementation

Python:

from collections import deque

class MyStack:
    """
    Stack implementation using two queues
    Time: O(n) push, O(1) pop/top/empty
    Space: O(n)
    """
    
    def __init__(self):
        self.input_queue = deque()
        self.output_queue = deque()
    
    def push(self, x: int) -> None:
        """Push element x onto stack"""
        self.input_queue.append(x)
        self._transfer_if_needed()
    
    def pop(self) -> int:
        """Remove element on top of stack and return it"""
        return self.output_queue.popleft()
    
    def top(self) -> int:
        """Return element on top of stack"""
        return self.output_queue[0]
    
    def empty(self) -> bool:
        """Return true if stack is empty"""
        return len(self.input_queue) == 0 and len(self.output_queue) == 0
    
    def _transfer_if_needed(self):
        """Move older elements behind the new one, then swap so output front is the top"""
        while self.output_queue:
            self.input_queue.append(self.output_queue.popleft())
        self.input_queue, self.output_queue = self.output_queue, self.input_queue

Java:

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    /**
     * Stack implementation using two queues
     * Time: O(n) push, O(1) pop/top/empty
     * Space: O(n)
     */
    
    private Queue<Integer> inputQueue;
    private Queue<Integer> outputQueue;
    
    public MyStack() {
        inputQueue = new LinkedList<>();
        outputQueue = new LinkedList<>();
    }
    
    public void push(int x) {
        inputQueue.offer(x);
        transferIfNeeded();
    }
    
    public int pop() {
        return outputQueue.poll();
    }
    
    public int top() {
        return outputQueue.peek();
    }
    
    public boolean empty() {
        return inputQueue.isEmpty() && outputQueue.isEmpty();
    }
    
    private void transferIfNeeded() {
        // Move older elements behind the new one, then swap so output front is the top
        while (!outputQueue.isEmpty()) {
            inputQueue.offer(outputQueue.poll());
        }
        Queue<Integer> temp = inputQueue;
        inputQueue = outputQueue;
        outputQueue = temp;
    }
}

Go:

type MyStack struct {
    inputQueue  []int
    outputQueue []int
}

// Constructor - Initialize stack
func Constructor() MyStack {
    return MyStack{
        inputQueue:  make([]int, 0),
        outputQueue: make([]int, 0),
    }
}

// Push - Push element x onto stack
func (this *MyStack) Push(x int) {
    this.inputQueue = append(this.inputQueue, x)
    this.transferIfNeeded()
}

// Pop - Remove element on top of stack and return it
func (this *MyStack) Pop() int {
    top := this.outputQueue[0]
    this.outputQueue = this.outputQueue[1:]
    return top
}

// Top - Return element on top of stack
func (this *MyStack) Top() int {
    return this.outputQueue[0]
}

// Empty - Return true if stack is empty
func (this *MyStack) Empty() bool {
    return len(this.inputQueue) == 0 && len(this.outputQueue) == 0
}

// transferIfNeeded - Move older elements behind the new one, then swap so output front is the top
func (this *MyStack) transferIfNeeded() {
    for len(this.outputQueue) > 0 {
        front := this.outputQueue[0]
        this.outputQueue = this.outputQueue[1:]
        this.inputQueue = append(this.inputQueue, front)
    }
    this.inputQueue, this.outputQueue = this.outputQueue, this.inputQueue
}

JavaScript:

/**
 * Stack implementation using two queues
 * Time: O(n) push, O(1) pop/top/empty
 * Space: O(n)
 */
class MyStack {
    constructor() {
        this.inputQueue = [];
        this.outputQueue = [];
    }
    
    push(x) {
        this.inputQueue.push(x);
        this.transferIfNeeded();
    }
    
    pop() {
        return this.outputQueue.shift();
    }
    
    top() {
        return this.outputQueue[0];
    }
    
    empty() {
        return this.inputQueue.length === 0 && this.outputQueue.length === 0;
    }
    
    transferIfNeeded() {
        // Move older elements behind the new one, then swap so output front is the top
        while (this.outputQueue.length > 0) {
            this.inputQueue.push(this.outputQueue.shift());
        }
        [this.inputQueue, this.outputQueue] = [this.outputQueue, this.inputQueue];
    }
}

C#:

using System.Collections.Generic;

public class MyStack {
    /// <summary>
    /// Stack implementation using two queues
    /// Time: O(n) push, O(1) pop/top/empty
    /// Space: O(n)
    /// </summary>
    
    private Queue<int> inputQueue;
    private Queue<int> outputQueue;
    
    public MyStack() {
        inputQueue = new Queue<int>();
        outputQueue = new Queue<int>();
    }
    
    public void Push(int x) {
        inputQueue.Enqueue(x);
        TransferIfNeeded();
    }
    
    public int Pop() {
        return outputQueue.Dequeue();
    }
    
    public int Top() {
        return outputQueue.Peek();
    }
    
    public bool Empty() {
        return inputQueue.Count == 0 && outputQueue.Count == 0;
    }
    
    private void TransferIfNeeded() {
        // Move older elements behind the new one, then swap so output front is the top
        while (outputQueue.Count > 0) {
            inputQueue.Enqueue(outputQueue.Dequeue());
        }
        (inputQueue, outputQueue) = (outputQueue, inputQueue);
    }
}

Complexity Analysis

  • Time Complexity: O(n) for push, O(1) for pop, top and empty
  • Space Complexity: O(n) for the two queues

Key Insights

  1. Two Queue Approach: Use input queue for push, output queue for pop/top
  2. Amortized Analysis: Transfer elements only when output queue is empty
  3. Lazy Transfer: Defer expensive operations until necessary
  4. LIFO Behavior: Maintain last-in-first-out order using queue operations
  5. Space Efficiency: Use two queues to simulate stack behavior

Edge Cases

  1. Empty Stack: All operations on empty stack
  2. Single Element: Stack with one element
  3. Multiple Operations: Mix of push, pop, top operations
  4. Large Input: Many consecutive push operations
  5. Alternating Operations: Push-pop-push-pop pattern

Follow-up Questions

  1. Implement Queue using Stacks: How would you implement a queue using stacks?
  2. Thread Safety: How would you make it thread-safe?
  3. Memory Management: How would you optimize memory usage?
  4. Performance: How would you optimize for high-frequency operations?

Common Mistakes

  1. Transfer Timing: Not transferring elements at the right time
  2. Queue Management: Incorrect queue operations
  3. Empty Check: Not properly checking for empty stack
  4. Order Maintenance: Not maintaining LIFO order correctly

Interview Tips

  1. Clarify Requirements: Ask about time complexity requirements
  2. Discuss Approaches: Mention both amortized and simple approaches
  3. Handle Edge Cases: Discuss empty stack and single element scenarios
  4. Explain Algorithm: Walk through the two-queue approach
  5. Consider Optimizations: Discuss space and time optimizations