Queue

A queue is a linear data structure that follows FIFO: First In, First Out. The first item added is the first item removed.

A line at a grocery store works the same way. New customers join at the back, or rear, while the customer who has waited the longest leaves from the front after being served.

How FIFO Works

Start with an empty queue and follow three operations:

The insertion order is 10, then 20. The removal order stays the same: 10, then 20.

Core Operations

Enqueue and dequeue define FIFO behavior. Peek and empty checks let code inspect the queue safely.

Implementing a Queue

The queue stores its items in an array or list and uses a front index to track the next item to remove. Enqueue adds at the end. Dequeue reads the current front item and moves the index forward.

Queue Class

class Queue {
  constructor() {
    this.items = [];
    this.front = 0;
  }

  isEmpty() {
    return this.front >= this.items.length;
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }

    const item = this.items[this.front];
    this.front++;

    if (this.isEmpty()) {
      this.items = [];
      this.front = 0;
    }

    return item;
  }

  peek() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }

    return this.items[this.front];
  }
}

Using the Queue

const queue = new Queue();

queue.enqueue("first");
queue.enqueue("second");
queue.enqueue("third");

console.log(queue.peek());    // "first"
console.log(queue.dequeue()); // "first"
console.log(queue.dequeue()); // "second"
console.log(queue.isEmpty()); // false

The first value enqueued is also the first value dequeued, so the implementation preserves FIFO order.

Performance and Big O

Big O notation describes how an operation's running time changes as the input grows.

• Constant time — $O(1)$: The work does not increase with the number of items.
• Linear time — $O(n)$: The work grows with the number of items.

The queue does not need to scan its existing items for any core operation.

Applications of Queues

Print Spooling

When several devices send jobs to one printer, the queue preserves the order in which those jobs arrived. The printer handles one job at a time, preventing jobs from overlapping.

Background Processing

Applications can place work in a queue so it can be processed outside the main application flow. This keeps the main application responsive while tasks wait for a worker.

For example, confirmation emails can be queued as users trigger them. A worker then processes the emails sequentially instead of making each user wait for sending to finish.

Task Scheduling and Shared Resources

Queues help manage work that must be handled fairly and in arrival order. This makes them useful when multiple tasks are waiting for the same resource.

Stack vs. Queue

Key Takeaways

• A queue follows First In, First Out order.
• New items enter at the rear, and existing items leave from the front.
• enqueue adds, dequeue removes, peek reads, and the empty check reports whether items remain.
• A well-implemented queue performs its core operations in $O(1)$ time.
• Print spooling, background jobs, and task scheduling use queues to preserve arrival order.