Stacks and Queues

Stacks and Queues

Why This Matters

Stacks and queues are fundamental data structures that model real-world processes. A stack is like a stack of plates—you add to the top and remove from the top (Last In, First Out). A queue is like a line at a store—you join at the back and leave from the front (First In, First Out).

This matters because these structures appear everywhere in software. Stacks are used for function call management (call stack), expression evaluation (parentheses matching), undo/redo operations, and backtracking algorithms. Queues are used for task scheduling, message processing, breadth-first search, and handling requests in web servers.

In interviews, stack and queue problems test your understanding of when to use each structure and your ability to implement them efficiently. Many algorithm problems become simpler when you recognize they're really stack or queue problems in disguise.

What Engineers Usually Get Wrong

Most engineers think "stacks and queues are just arrays with restrictions." While that's true for simple implementations, the real power comes from understanding when to use each structure. Engineers often use arrays when a stack or queue would be more appropriate, leading to inefficient code.

Engineers also confuse LIFO (Last In, First Out) with FIFO (First In, First Out). They'll use a stack when they need a queue, or vice versa. This causes bugs—like processing tasks in the wrong order or evaluating expressions incorrectly.

Another common mistake is not considering the implementation choice. Array-based stacks/queues have O(1) operations but fixed size (or expensive resizing). Linked list-based implementations have dynamic size but pointer overhead. Choosing the wrong implementation can hurt performance.

How This Breaks Systems in the Real World

A web server was processing incoming requests using a stack. Requests were added to the stack and processed from the top. This meant the most recent request was always processed first. During a traffic spike, new requests kept arriving, pushing older requests deeper into the stack. Some requests waited for hours before being processed. Users complained about slow responses.

The fix? Use a queue instead. Process requests in the order they arrive (FIFO). This ensures fairness—older requests are processed before newer ones. The lesson? Stacks are for LIFO processing, queues are for FIFO processing. Choose based on your requirements.

Another story: A service was evaluating mathematical expressions. It used a queue to store operators. But expression evaluation requires LIFO behavior (operators are evaluated in reverse order due to precedence). The service evaluated expressions incorrectly, producing wrong results. The fix? Use a stack for operators. This allows proper handling of operator precedence and parentheses.

Stacks (LIFO - Last In, First Out)

A stack is a linear data structure where elements are added and removed from the same end (the top).

Operations

• push(val): Add element to top - O(1)
• pop(): Remove and return top element - O(1)
• peek() or top(): View top element without removing - O(1)
• isEmpty(): Check if stack is empty - O(1)
• size(): Get number of elements - O(1)

Array-Based Implementation

1 

Linked List-Based Implementation

1 

Queues (FIFO - First In, First Out)

A queue is a linear data structure where elements are added at the rear and removed from the front.

Operations

• enqueue(val): Add element to rear - O(1)
• dequeue(): Remove and return front element - O(1)
• front() or peek(): View front element without removing - O(1)
• isEmpty(): Check if queue is empty - O(1)
• size(): Get number of elements - O(1)

Array-Based Implementation (Circular Buffer)

1 

Linked List-Based Implementation

1 

Special Queue Variants

Priority Queue

Elements are dequeued based on priority (not insertion order).

1 

Deque (Double-Ended Queue)

Allows insertion and deletion from both ends.

1 

Examples

Example 1: Valid Parentheses (Stack)

1 

Example 2: Implement Queue using Stacks

1 

Example 3: Sliding Window Maximum (Deque)

1 

Common Pitfalls

• Using wrong structure: Using stack when you need queue (or vice versa) causes incorrect processing order
• Not handling empty structure: Always check isEmpty() before pop() or dequeue()
• Array-based queue inefficiency: Naive array queue has O(n) dequeue (shifting). Use circular buffer or linked list
• Memory leaks: In linked implementations, ensure nodes are properly deallocated
• Stack overflow: Array-based stack can overflow if capacity exceeded
• Circular buffer index errors: Use modulo correctly: (index + 1) % capacity
• Not updating rear in queue: When dequeuing last element, set rear to null

Failure Stories You'll Recognize

The Wrong Order Bug: A service was processing tasks using a stack. Tasks were added and processed from the top. This meant urgent tasks that arrived later were processed before older, less urgent tasks. Critical tasks were delayed, causing SLA violations. The fix? Use a queue. Process tasks in the order they arrive (FIFO), or use a priority queue if tasks have different priorities.

The Expression Evaluation Bug: A service was evaluating mathematical expressions. It used a queue to store operators. But expression evaluation requires LIFO behavior due to operator precedence. The expression 2 + 3 * 4 was evaluated as (2 + 3) * 4 = 20 instead of 2 + (3 * 4) = 14. The fix? Use a stack for operators. This allows proper handling of precedence and parentheses.

The Memory Leak: A service was using a linked list-based queue. When dequeuing, it removed the front node but didn't properly free memory (in C/C++). Over time, memory usage grew. The fix? Explicitly free memory when dequeuing, or use a language with garbage collection.

What Interviewers Are Really Testing

They want to see you choose the right structure for the problem. Junior engineers use arrays for everything. Senior engineers recognize when a stack or queue is the right tool.

When they ask "implement a queue using stacks," they're testing:

• Do you understand LIFO vs FIFO?
• Can you use one structure to simulate another?
• Do you understand amortized complexity?

Interview Questions

Beginner

Q: What is the difference between a stack and a queue?

A:

Stack (LIFO - Last In, First Out):

• Elements added and removed from same end (top)
• Like a stack of plates
• Operations: push (add to top), pop (remove from top)
• Use cases: Function calls, expression evaluation, undo/redo, backtracking

Queue (FIFO - First In, First Out):

• Elements added at rear, removed from front
• Like a line at a store
• Operations: enqueue (add to rear), dequeue (remove from front)
• Use cases: Task scheduling, BFS, message processing, request handling

Key Difference:

• Stack: Last element added is first removed
• Queue: First element added is first removed

Intermediate

Q: How would you implement a queue using two stacks? What's the time complexity?

A:

class QueueUsingStacks {
  private stack1: number[] = []; // For enqueue
  private stack2: number[] = []; // For dequeue

  enqueue(x: number): void {
    this.stack1.push(x); // O(1)
  }

  dequeue(): number {
    if (this.stack2.length === 0) {
      // Transfer all elements from stack1 to stack2
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop()!);
      }
    }
    return this.stack2.pop()!;
  }

  peek(): number {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop()!);
      }
    }
    return this.stack2[this.stack2.length - 1];
  }

  empty(): boolean {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }
}

// Time Complexity:
// - enqueue: O(1)
// - dequeue: O(1) amortized (occasional O(n) when transferring)
// - peek: O(1) amortized
// - empty: O(1)

// Space: O(n) for n elements

How it works:

• Enqueue adds to stack1
• Dequeue transfers from stack1 to stack2 (reversing order), then pops from stack2
• This gives FIFO behavior using LIFO structures

Amortized analysis: Each element is pushed/popped at most twice (once in each stack), so average cost per operation is O(1).

Senior

Q: Design a data structure that supports push, pop, top, and getMin all in O(1) time. How would you implement it?

A:

Challenge: Regular stack supports push, pop, top in O(1), but getMin requires O(n) to search.

Solution: Use two stacks—one for values, one for minimums.

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = []; // Tracks minimum at each level

  push(val: number): void {
    this.stack.push(val);
    // Push current minimum (either new val or previous min)
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    } else {
      this.minStack.push(this.minStack[this.minStack.length - 1]);
    }
  }

  pop(): void {
    this.stack.pop();
    this.minStack.pop();
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

// Time: All operations O(1)
// Space: O(n) - two stacks
// Edge cases: empty stack, duplicate minimums

Alternative (Space Optimized): Only push to minStack when new minimum found.

class MinStackOptimized {
  private stack: number[] = [];
  private minStack: number[] = [];

  push(val: number): void {
    this.stack.push(val);
    // Only push if new minimum or equal to current minimum
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }

  pop(): void {
    const val = this.stack.pop()!;
    // Only pop from minStack if we're removing the minimum
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

// Time: All operations O(1)
// Space: O(n) worst case, but often better (only stores minimums)