Queue Using Stacks

Overview

Queue using stacks is a classic interview problem that asks you to implement a queue (FIFO) data structure using only stacks (LIFO). This demonstrates understanding of both data structures and how to achieve FIFO behavior using LIFO operations.

There are two main approaches:

1. Two stacks approach - Use two stacks, one for enqueue and one for dequeue
2. Amortized approach - Transfer elements between stacks only when needed

The challenge is that stacks are LIFO (Last-In, First-Out) while queues are FIFO (First-In, First-Out), so you need to reverse the order using a second stack.

Key characteristics:

• Two stacks - Use two stacks to reverse order
• FIFO from LIFO - Achieve FIFO behavior using LIFO operations
• Amortized O(1) - Amortized constant time operations
• Design problem - Classic system design interview question
• Stack operations only - Can only use push, pop, peek, isEmpty

How Queue Using Stacks Works

The key insight is using two stacks:

1. Stack 1 (input stack) - Used for enqueue operations
2. Stack 2 (output stack) - Used for dequeue operations
3. Enqueue - Push element to input stack
4. Dequeue - If output stack is empty, transfer all elements from input to output, then pop from output
5. Reverse order - Transferring reverses order, making first element accessible

The transfer operation reverses the order, converting LIFO to FIFO.

Approach 1: Two Stacks (Amortized O(1))

Efficient approach with amortized O(1) operations:

class QueueUsingStacks<T> {
  private inputStack: T[] = [];
  private outputStack: T[] = [];
  
  enqueue(item: T): void {
    this.inputStack.push(item);
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    // Transfer from input to output if output is empty
    if (this.outputStack.length === 0) {
      while (this.inputStack.length > 0) {
        this.outputStack.push(this.inputStack.pop()!);
      }
    }
    
    return this.outputStack.pop();
  }
  
  peek(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    // Transfer if needed
    if (this.outputStack.length === 0) {
      while (this.inputStack.length > 0) {
        this.outputStack.push(this.inputStack.pop()!);
      }
    }
    
    return this.outputStack[this.outputStack.length - 1];
  }
  
  isEmpty(): boolean {
    return this.inputStack.length === 0 && this.outputStack.length === 0;
  }
  
  size(): number {
    return this.inputStack.length + this.outputStack.length;
  }
}

Time complexity:

• enqueue: O(1)
• dequeue: O(1) amortized (O(n) worst case when transfer needed)
• peek: O(1) amortized
• isEmpty: O(1)

Key insight: Transfer only when output stack is empty, amortizing the cost.

Approach 2: Always Transfer (O(n) Operations)

Simpler but less efficient approach:

class QueueUsingStacksSimple<T> {
  private stack1: T[] = [];
  private stack2: T[] = [];
  
  enqueue(item: T): void {
    // Transfer all from stack1 to stack2
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop()!);
    }
    
    // Push new item to stack1
    this.stack1.push(item);
    
    // Transfer back from stack2 to stack1
    while (this.stack2.length > 0) {
      this.stack1.push(this.stack2.pop()!);
    }
  }
  
  dequeue(): T | undefined {
    return this.stack1.pop();
  }
  
  peek(): T | undefined {
    return this.stack1.length > 0 ? this.stack1[this.stack1.length - 1] : undefined;
  }
  
  isEmpty(): boolean {
    return this.stack1.length === 0;
  }
}

Time complexity:

• enqueue: O(n) - transfers all elements twice
• dequeue: O(1)
• peek: O(1)

Note: This approach is O(n) for enqueue, making it inefficient.

Pattern 1: LeetCode - Implement Queue using Stacks

LeetCode problem implementation:

class MyQueue {
  private inputStack: number[] = [];
  private outputStack: number[] = [];
  
  push(x: number): void {
    this.inputStack.push(x);
  }
  
  pop(): number {
    this.peek(); // Ensure output stack has elements
    return this.outputStack.pop()!;
  }
  
  peek(): number {
    if (this.outputStack.length === 0) {
      while (this.inputStack.length > 0) {
        this.outputStack.push(this.inputStack.pop()!);
      }
    }
    return this.outputStack[this.outputStack.length - 1];
  }
  
  empty(): boolean {
    return this.inputStack.length === 0 && this.outputStack.length === 0;
  }
}

Time: O(1) amortized for all operations

Pattern 2: Queue Using Single Stack (Recursive)

Using recursion to simulate second stack:

class QueueUsingSingleStack<T> {
  private stack: T[] = [];
  
  enqueue(item: T): void {
    this.stack.push(item);
  }
  
  dequeue(): T | undefined {
    if (this.stack.length === 0) return undefined;
    
    if (this.stack.length === 1) {
      return this.stack.pop();
    }
    
    // Recursively pop and push to get bottom element
    const top = this.stack.pop()!;
    const result = this.dequeue();
    this.stack.push(top);
    
    return result;
  }
  
  peek(): T | undefined {
    if (this.stack.length === 0) return undefined;
    
    if (this.stack.length === 1) {
      return this.stack[this.stack.length - 1];
    }
    
    const top = this.stack.pop()!;
    const result = this.peek();
    this.stack.push(top);
    
    return result;
  }
  
  isEmpty(): boolean {
    return this.stack.length === 0;
  }
}

Time: O(n) for dequeue/peek (uses recursion)

Note: This is less efficient but demonstrates recursion.

Pattern 3: Queue Using Stacks with Front Tracking

Track front element separately:

class QueueWithFrontTracking<T> {
  private inputStack: T[] = [];
  private outputStack: T[] = [];
  private front: T | undefined;
  
  enqueue(item: T): void {
    if (this.inputStack.length === 0) {
      this.front = item;
    }
    this.inputStack.push(item);
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    if (this.outputStack.length === 0) {
      while (this.inputStack.length > 0) {
        this.outputStack.push(this.inputStack.pop()!);
      }
    }
    
    const result = this.outputStack.pop();
    
    // Update front if output stack not empty
    if (this.outputStack.length > 0) {
      this.front = this.outputStack[this.outputStack.length - 1];
    } else if (this.inputStack.length > 0) {
      // Front is bottom of input stack (will be transferred)
      this.front = this.inputStack[0];
    } else {
      this.front = undefined;
    }
    
    return result;
  }
  
  peek(): T | undefined {
    if (this.outputStack.length > 0) {
      return this.outputStack[this.outputStack.length - 1];
    }
    return this.front;
  }
  
  isEmpty(): boolean {
    return this.inputStack.length === 0 && this.outputStack.length === 0;
  }
}

Time: O(1) amortized

Key insight: Track front element to avoid unnecessary transfers.

Pattern 4: Deque Using Stacks

Implement deque (double-ended queue) using stacks:

class DequeUsingStacks<T> {
  private leftStack: T[] = [];
  private rightStack: T[] = [];
  
  pushFront(item: T): void {
    this.leftStack.push(item);
  }
  
  pushRear(item: T): void {
    this.rightStack.push(item);
  }
  
  popFront(): T | undefined {
    if (this.leftStack.length === 0) {
      // Transfer half from right to left
      this.balanceStacks();
    }
    return this.leftStack.pop();
  }
  
  popRear(): T | undefined {
    if (this.rightStack.length === 0) {
      // Transfer half from left to right
      this.balanceStacks();
    }
    return this.rightStack.pop();
  }
  
  private balanceStacks(): void {
    const total = this.leftStack.length + this.rightStack.length;
    const mid = Math.floor(total / 2);
    
    // Transfer elements to balance
    const temp: T[] = [];
    while (this.leftStack.length > mid) {
      temp.push(this.leftStack.pop()!);
    }
    while (this.rightStack.length < mid) {
      this.rightStack.push(temp.pop()!);
    }
  }
  
  isEmpty(): boolean {
    return this.leftStack.length === 0 && this.rightStack.length === 0;
  }
}

Time: O(n) for balance operations

Note: More complex than simple queue.

When to Use Queue Using Stacks

This is primarily a design/interview problem, but understanding it helps with:

• System design - Understanding data structure trade-offs
• Interview questions - Common coding interview problem
• Algorithm understanding - Demonstrates LIFO vs FIFO concepts
• Amortized analysis - Understanding amortized complexity
• Problem solving - Converting one data structure to another

Key distinction:

• Queue using stacks - Design problem, demonstrates understanding
• Regular queue - Use linked list or array for production
• Stack using queues - Reverse problem (also common interview question)

Queue Using Stacks vs Regular Queue

| Aspect | Queue Using Stacks | Regular Queue |

|--------|-------------------|---------------|

| Operations | O(1) amortized | O(1) |

| Implementation | Two stacks | Linked list/array |

| Use case | Interview/design | Production |

| Complexity | Amortized O(1) | True O(1) |

| Space | O(n) | O(n) |

Remember:

• Queue using stacks for interviews, understanding concepts
• Regular queue for production code

Template (Two Stacks Approach)

class QueueUsingStacksTemplate<T> {
  private inputStack: T[] = [];
  private outputStack: T[] = [];
  
  enqueue(item: T): void {
    this.inputStack.push(item);
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    // Transfer if output stack is empty
    if (this.outputStack.length === 0) {
      while (this.inputStack.length > 0) {
        this.outputStack.push(this.inputStack.pop()!);
      }
    }
    
    return this.outputStack.pop();
  }
  
  peek(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    // Transfer if needed
    if (this.outputStack.length === 0) {
      while (this.inputStack.length > 0) {
        this.outputStack.push(this.inputStack.pop()!);
      }
    }
    
    return this.outputStack[this.outputStack.length - 1];
  }
  
  isEmpty(): boolean {
    return this.inputStack.length === 0 && this.outputStack.length === 0;
  }
}

Time and Space Complexity

Two Stacks Approach (Amortized)

• enqueue: O(1)
• dequeue: O(1) amortized, O(n) worst case
• peek: O(1) amortized, O(n) worst case
• isEmpty: O(1)
• Space: O(n)

Always Transfer Approach

• enqueue: O(n)
• dequeue: O(1)
• peek: O(1)
• Space: O(n)

Single Stack (Recursive)

• enqueue: O(1)
• dequeue: O(n)
• peek: O(n)
• Space: O(n) + O(n) recursion stack = O(n)

Amortized analysis:

• Each element is pushed to input stack once (O(1))
• Each element is popped from input and pushed to output once (O(1))
• Each element is popped from output once (O(1))
• Total: O(1) per operation amortized

Practice Tips

1. Two stacks - Use input stack for enqueue, output stack for dequeue
2. Lazy transfer - Only transfer when output stack is empty
3. Amortized analysis - Understand why it's O(1) amortized
4. Edge cases - Handle empty queue, single element
5. Peek optimization - Reuse transfer logic in peek
6. Test thoroughly - Test interleaved enqueue/dequeue operations
7. Explain approach - Be able to explain the two-stack approach

Common Mistakes

1. Transferring every time - Transferring on every dequeue (inefficient)
2. Wrong transfer direction - Transferring in wrong direction
3. Not checking empty - Not checking if queue is empty before dequeue
4. Peek implementation - Not reusing transfer logic in peek
5. State inconsistency - Elements in wrong stack
6. Amortized misunderstanding - Thinking it's always O(1)
7. Single stack only - Trying to use only one stack (requires recursion)

Real-World Applications

While not used in production (regular queues are better), understanding this helps with:

• System Design Interviews - Demonstrates data structure knowledge
• Algorithm Understanding - Understanding LIFO vs FIFO
• Problem Solving - Converting between data structures
• Amortized Analysis - Understanding amortized complexity
• Interview Preparation - Common coding interview problem
• Educational - Teaching data structure concepts

Related Concepts

• Stack - LIFO data structure used to implement queue
• Queue - FIFO data structure being implemented
• Amortized Analysis - Analyzing average case complexity
• Stack Using Queues - Reverse problem (also common)
• Data Structure Design - Designing one structure using another

Summary

Queue using stacks is a classic design problem:

• Two stacks - Use input and output stacks
• Lazy transfer - Transfer only when output stack is empty
• Amortized O(1) - Average case O(1) per operation
• Design problem - Demonstrates understanding of data structures
• Interview favorite - Common coding interview question

Key takeaways:

• Use two stacks: input for enqueue, output for dequeue
• Transfer elements only when output stack is empty
• Amortized O(1) complexity per operation
• Essential for understanding LIFO vs FIFO
• Common interview problem for system design

Mastering queue using stacks will help you solve design problems and demonstrate deep understanding of data structures in coding interviews.