sko.kr

Algorithms - 9. Queue

algorithmsdata-structuresqueuefifolinked-list
By sko•10/7/2025•7 min read

When to use Queue

Use Queue when you need to process items in First-In-First-Out (FIFO) order - the first item added is the first item removed. While most commonly used for task scheduling, it's essential for:

  • Breadth-First Search (BFS) (classic use case)
  • Task scheduling (processing in order of arrival)
  • Message queuing systems (maintaining order of messages)
  • Print spooler (print jobs processed in submission order)
  • Call center systems (handling calls in order received)
  • Any problem requiring fair ordering where items must be processed in arrival sequence

Example problem

Customer Service System: A coffee shop needs to serve customers in the order they arrive. Customers join the line at different times and must be served fairly.

  • Customer A arrives at 9:00 AM
  • Customer B arrives at 9:02 AM
  • Customer C arrives at 9:05 AM
  • Customer D arrives at 9:07 AM

Answer: Using a queue ensures Customer A is served first, then B, then C, then D - maintaining perfect fairness through FIFO ordering.

Single most important insight

A queue maintains order by separating the addition point (rear) from the removal point (front) - and by using two pointers to track both ends, we achieve O(1) operations while guaranteeing items exit in the exact order they entered.

Mental note: The queue's genius lies in its two-pointer design. We only interact with the front when removing (dequeue/shift) and the rear when adding (enqueue/push). This separation of concerns means we never need to traverse or reorganize - the structure itself maintains the order automatically through its dual-ended access pattern.

Decision Framework

With the dummy node pattern, operations become remarkably consistent:

  • Push: Always add to the rear - no special cases at all!
  • Shift: Always remove from dummyHead.next (if it exists)
  • Edge case simplified: Only one check - is dummyHead.next null? (empty queue)

Code

// Each customer in line is a "node" containing their value and who's next
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// Cleaner implementation with dummy node - no null checks needed!
class Queue {
  constructor() {
    // Create a dummy node that always exists (like a "line starts here" sign)
    this.dummyHead = new ListNode(null);
    this.rear = this.dummyHead; // Initially, rear points to dummy
  }

  // Add a new customer to the back of the line
  push(value) {
    const newCustomer = new ListNode(value);

    // Step 1: Connect the current last person to the new customer
    this.rear.next = newCustomer;

    // Step 2: Update our rear pointer to point to the new last person
    // Think of it like moving a "Last Person" sign to the new customer
    this.rear = newCustomer;
    // Now this.rear points to the new last node, not the old one
  }

  // Serve the customer at the front and remove them from line
  shift() {
    // DECISION FRAMEWORK: Check if line is empty (no one after dummy)
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // The first real customer is always at dummyHead.next
    const firstCustomer = this.dummyHead.next;
    const servedValue = firstCustomer.value;

    // Move the line forward - skip over the first customer
    // This makes dummyHead point directly to the second customer (or null if none)
    this.dummyHead.next = firstCustomer.next;
    // We're essentially "cutting out" firstCustomer from the chain

    // DECISION FRAMEWORK: If we removed the last customer, update rear
    if (this.dummyHead.next === null) {
      this.rear = this.dummyHead; // Reset rear to dummy when empty
    }

    return servedValue;
  }

  // Look at who's next without serving them
  peek() {
    if (this.dummyHead.next === null) {
      return undefined;
    }
    return this.dummyHead.next.value;
  }

  // Check if the line is empty
  isEmpty() {
    return this.dummyHead.next === null;
  }

  // Visualize the queue (helpful for debugging)
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// Example: Coffee shop line
const coffeeLine = new Queue();

// Morning rush - customers join the line
coffeeLine.push("Alice");
coffeeLine.push("Bob");
coffeeLine.push("Charlie");

console.log("Line:", coffeeLine.display()); // 'Alice → Bob → Charlie'
console.log("First in line:", coffeeLine.peek()); // 'Alice'

// Start serving customers (FIFO order)
console.log("Now serving:", coffeeLine.shift()); // 'Alice'
console.log("Line:", coffeeLine.display()); // 'Bob → Charlie'

// New customer arrives while serving
coffeeLine.push("Diana");
console.log("Line:", coffeeLine.display()); // 'Bob → Charlie → Diana'

console.log("Now serving:", coffeeLine.shift()); // 'Bob'
console.log("Now serving:", coffeeLine.shift()); // 'Charlie'
console.log("Now serving:", coffeeLine.shift()); // 'Diana'
console.log("Now serving:", coffeeLine.shift()); // undefined (empty)

Understanding the pointer reassignment

When we do this.rear = newCustomer, we're moving the rear pointer to point to a different node:

Before push('Alice'):
dummyHead → null
rear ↑ (points to dummyHead)

After this.rear.next = newCustomer:
dummyHead → Alice → null
rear ↑ (still points to dummyHead)

After this.rear = newCustomer:
dummyHead → Alice → null
            rear ↑ (NOW points to Alice)

The key insight: this.rear is just a reference/pointer that tells us "which node is currently last". When we write this.rear = newCustomer, we're not changing any nodes - we're just updating our reference to point to the new last node. It's like moving a "Last in Line" sign from one person to another.

Understanding shift's pointer bypass

When we do this.dummyHead.next = firstCustomer.next, we're bypassing the first customer:

Before shift():
dummyHead → Alice → Bob → Charlie → null
            ↑ firstCustomer points here

After const firstCustomer = this.dummyHead.next:
We save a reference to Alice

After this.dummyHead.next = firstCustomer.next:
dummyHead → Bob → Charlie → null
(Alice is bypassed - no longer in the chain!)

The line this.dummyHead.next = firstCustomer.next is saying: "Whatever Alice was pointing to (Bob), make the dummy point directly to that instead." This effectively removes Alice from the chain - she's been "served" and is no longer in line.

Why the dummy node makes it cleaner

The dummy node acts like a "line starts here" sign that never moves. This eliminates special cases:

Without dummy node:

  • Must check if queue is null before adding first element
  • Must handle both front and rear being null
  • Need different logic for first element vs subsequent elements

With dummy node:

  • The dummy always exists, so no null checks for the structure itself
  • Adding is always the same: attach to rear, update rear
  • Removing is always the same: take from dummyHead.next
  • The only check needed is whether the queue is empty (dummyHead.next === null)

Doubt buster

Common doubt: "Why use a linked list for the queue? Can't we just use an array and track indices? Wouldn't that be simpler?"

This is an excellent question that highlights a critical performance consideration. Let's examine both approaches.

Why you might think arrays are simpler

Consider implementing a queue with an array:

  • "Arrays give us indexed access - seems more straightforward"
  • "We could just use push() to add and shift() to remove"
  • "No need to manage node pointers and next references"

Why this thinking misses a crucial problem

Key realization: Array-based queues have a hidden performance trap!

Let's trace what happens with an array implementation:

Initial: [1, 2, 3, 4, 5]

Dequeue (remove from front):
Step 1: Remove element at index 0: [_, 2, 3, 4, 5]
Step 2: Shift all remaining elements left: [2, 3, 4, 5]
        - Element at index 1 moves to index 0
        - Element at index 2 moves to index 1
        - Element at index 3 moves to index 2
        - Element at index 4 moves to index 3

The performance disaster: Every dequeue operation requires shifting ALL remaining elements, making it O(n) instead of O(1)!

Concrete example: Performance comparison

Let's compare operations on a queue with 1000 items:

Array-based queue:

  • Enqueue: O(1) - just append to end
  • Dequeue: O(n) - must shift 999 elements!
  • Processing all 1000 items: O(n²) total operations

Linked list queue:

  • Enqueue: O(1) - update rear pointer
  • Dequeue: O(1) - update front pointer
  • Processing all 1000 items: O(n) total operations

The circular array alternative

"But wait," you might say, "what about using a circular array with front and rear indices?"

class ArrayQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = capacity;
  }
}

This approach has its own problems:

  • Fixed capacity: Must predetermine maximum size
  • Wasted space: Unused array slots consume memory
  • Resize complexity: Growing the queue requires copying all elements
  • Index wraparound logic: More complex mental model with modulo arithmetic

Why linked list is the optimal choice

The linked list implementation elegantly solves all these issues:

  1. Constant time operations: Both enqueue and dequeue are always O(1)
  2. Dynamic size: Grows and shrinks as needed
  3. Memory efficient: Only allocates what's actually used
  4. Simple mental model: Front pointer for removal, rear pointer for addition
  5. No shifting or copying: Nodes stay where they are; only pointers change

The guarantee: Since we only ever touch the ends of the structure (never the middle), and pointer updates are O(1) operations, we maintain constant time complexity for all core operations while using only the memory we need.

The two-pointer linked list design isn't just an implementation detail - it's the fundamental mechanism that makes queues efficient for their intended FIFO purpose!

← Back to Blog