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

1class Stack<T> {
2  private items: T[] = [];
3  private capacity: number;
4
5  constructor(capacity: number = Infinity) {
6    this.capacity = capacity;
7  }
8
9  push(item: T): void {
10    if (this.items.length >= this.capacity) {
11      throw new Error("Stack overflow");

Linked List-Based Implementation

1class StackNode<T> {
2  val: T;
3  next: StackNode<T> | null = null;
4
5  constructor(val: T) {
6    this.val = val;
7  }
8}
9
10class LinkedStack<T> {
11  private head: StackNode<T> | null = null;
12  private size: number = 0;
13
14  push(item: T

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)

1class Queue<T> {
2  private items: (T | undefined)[];
3  private front: number = 0;
4  private rear: number = 0;
5  private count: number = 0;
6  private capacity: number;
7
8  constructor(capacity: number) {
9    this.capacity = capacity;
10    this.items = new Array(capacity);

Linked List-Based Implementation

1class QueueNode<T> {
2  val: T;
3  next: QueueNode<T> | null = null;
4
5  constructor(val: T) {
6    this.val = val;
7  }
8}
9
10class LinkedQueue<T> {
11  private front: QueueNode<T> | null = null;
12  private rear: QueueNode<T> | null = null;
13  private size

Special Queue Variants

Priority Queue

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

1class PriorityQueue<T> {
2  private heap: T[] = [];
3  private compare: (a: T, b: T) => number;
4
5  constructor(compare: (a: T, b: T) => number) {
6    this.compare = compare; // Returns negative if a < b
7  }
8
9  enqueue(item: T): void {
10    heapitem

Deque (Double-Ended Queue)

Allows insertion and deletion from both ends.

1class Deque<T> {
2  private items: T[] = [];
3
4  addFront(item: T): void {
5    this.items.unshift(item); // O(n) - inefficient
6  }
7
8  addRear(item: T): void {
9    this.items.push(item); // O(1)
10  }
11
12  removeFront(): T | undefined {

Examples

Example 1: Valid Parentheses (Stack)

1function isValid(s: string): boolean {
2  const stack: string[] = [];
3  const pairs: Record<string, string> = {
4    ')': '(',
5    '}': '{',
6    ']': '['
7  };
8
9  for (const char of s) {
10    if (char in pairs) {
11      // Closing bracket
12      if (stack.length ===   stack  pairschar

Example 2: Implement Queue using Stacks

1class MyQueue {
2  private stack1: number[] = [];
3  private stack2: number[] = [];
4
5  push(x: number): void {
6    this.stack1.push(x);
7  }
8
9  pop(): number {
10    if (this.stack2.length === 0) {
11      // Transfer all elements from stack1 to stack2
12      while (thisstack1length

Example 3: Sliding Window Maximum (Deque)

1function maxSlidingWindow(nums: number[], k: number): number[] {
2  const result: number[] = [];
3  const deque: number[] = []; // Store indices
4
5  for (let i = 0; i < nums.length; i++) {
6    // Remove indices outside window
7    while (deque.length > 0 && deque[0] <= i - k)

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)

• Stack (LIFO): Last element added is first removed. Use for function calls, expression evaluation, undo/redo, backtracking
• Queue (FIFO): First element added is first removed. Use for task scheduling, BFS, message processing
• Array implementation: O(1) operations, but fixed size (or expensive resizing). Use circular buffer for queue
• Linked list implementation: Dynamic size, O(1) operations, but pointer overhead
• Priority queue: Elements dequeued by priority. Implement with heap for O(log n) operations
• Deque: Double-ended queue, allows O(1) operations on both ends (use doubly linked list)
• Common operations: All basic operations (push/pop, enqueue/dequeue) are O(1)
• Real-world applications: Stacks for call stack, expression evaluation. Queues for task scheduling, BFS
• Implementation choice: Array for fixed size/frequency, linked list for dynamic size
• Edge cases: Empty structure, full structure (array-based), single element

How InterviewCrafted Will Teach This

We'll teach stacks and queues through real problems, not abstract definitions. Instead of memorizing "a stack is LIFO," you'll learn through scenarios like "how do you match parentheses?" or "how do you process tasks in order?"

You'll see how stacks and queues are used in real systems (call stacks, task schedulers) and understand when to choose each structure. When an interviewer asks "implement a queue using stacks," you'll think about LIFO vs FIFO and how to simulate one with the other—not just "use two stacks."

• Arrays - Stacks and queues can be implemented using arrays (with fixed size or dynamic resizing). Understanding arrays helps with implementation.
• Linked Lists - Stacks and queues can be implemented using linked lists for dynamic size. Understanding linked lists helps with pointer-based implementations.
• Trees - Tree traversals use stacks (iterative DFS) and queues (BFS). Understanding stacks/queues helps with tree algorithms.
• Graphs - Graph traversals use stacks (DFS) and queues (BFS). Understanding stacks/queues is essential for graph algorithms.
• Recursion & Backtracking - Recursion uses the call stack. Understanding stacks helps understand how recursion works internally.