Implementing an Array-Based Queue with Amortized O(1) Dequeue

In our last session, we mastered the stack, a data structure built on the Last-In, First-Out (LIFO) principle, and applied it to validate nested parentheses. We saw how a simple array with push() and pop() elegantly solves problems involving ordered, nested states.

Today, we'll turn our attention to the stack's counterpart: the queue. A queue operates on a First-In, First-Out (FIFO) principle, just like a real-world checkout line. Your objective for this lesson is to design an efficient array-backed queue in TypeScript. Specifically, you will learn how to achieve constant-time amortized removal by maintaining a head index, a crucial optimization that avoids a common performance trap. This concept is fundamental for building performant data-processing pipelines, task schedulers, and is a cornerstone of breadth-first search, which we will cover later.

The FIFO Principle and a Naive Implementation

A queue has two primary operations:

• enqueue(item): Adds an item to the back (or tail) of the queue.
• dequeue(): Removes and returns the item from the front (or head) of the queue.

Given your extensive experience with JavaScript, your first instinct for implementing a queue might be to use a standard array: push() to add to the end and shift() to remove from the beginning.

class NaiveQueue<T> {
  private storage: T[] = [];

  enqueue(item: T): void {
    this.storage.push(item); // O(1)
  }

  dequeue(): T | undefined {
    return this.storage.shift(); // O(n)!
  }
}

While push() is a constant-time operation, shift() is not. When you remove the first element of an array, every other element must be moved one position to the left. For an array with n elements, this requires n-1 movements, resulting in a time complexity of $O(n)$. In applications involving frequent dequeues, this linear-time operation becomes a significant performance bottleneck.

The Optimization: Using a Head Index

How can we achieve a constant-time dequeue? The key insight is to avoid the costly shift() operation altogether. Instead of physically removing the element from the array, we can simply keep track of the logical front of the queue using a pointer or index. Let's call it head.

The logic now becomes:

• enqueue(item): Remains the same. We push the item to the end of the array. O(1).
• dequeue():
  1. Read the item at the head index.
  2. Increment the head index. This logically "removes" the item.
  3. This is now an O(1) operation, as it only involves reading an array element and incrementing a number.

This approach introduces a new problem: the array will grow indefinitely, and the space before the head index becomes wasted. The dequeued elements are still held in memory, though they are logically inaccessible.

The image below illustrates the state of such a queue. indexFront is our head pointer, and indexBack points to the position for the next enqueue. Notice the empty slots at the beginning of the array, which represent the wasted space from previous dequeue operations.

Amortized Constant Time: Periodic Cleanup

We have a classic trade-off: we achieved $O(1)$ time for dequeue at the cost of $O(n)$ wasted space. To manage this, we can perform a cleanup operation, but only periodically. If we clean up too often, we lose our performance gain. If we never clean up, we risk excessive memory consumption.

A common strategy is to clean up when the wasted space reaches a certain threshold, for example, when the number of "dead" elements equals the number of "live" elements (i.e., head >= length / 2). The cleanup operation involves slicing the array to discard the wasted portion and resetting the head index.

if (this.head * 2 >= this.queue.length) {
    this.queue = this.queue.slice(this.head);
    this.head = 0;
}

This slice() operation is $O(k)$, where k is the number of live elements in the queue. In the worst case, this is $O(n)$. However, because this expensive operation happens only after many cheap $O(1)$ dequeues, the average cost per operation remains constant. This is known as amortized constant time.

The following graph visualizes this concept. The orange line shows the time taken per operation. It's almost always constant and low, with occasional spikes. These spikes represent our expensive cleanup operations. The blue line, representing cumulative time, still grows linearly, confirming that the average cost per operation is constant.

A Production-Ready TypeScript Implementation

Let's now look at a complete implementation that brings these ideas together. The following Stack Overflow answer provides a well-structured TypeScript Queue class that uses a head offset and includes the periodic cleanup logic we just discussed.

Alternative Implementations

While the dynamic array with slicing is a common and effective approach, it's worth knowing about two other popular strategies.

1. Using a Plain JavaScript Object

Another clever way to achieve $O(1)$ enqueue and dequeue is to use a plain JavaScript object instead of an array. By maintaining head and tail pointers as keys, you can add and remove properties in constant time, sidestepping the array shift() problem entirely.

This video from Codevolution walks through this exact implementation.

This method avoids the need for amortization and slicing but relies on the performance characteristics of JavaScript object property access and deletion.

2. The Circular Queue

For queues with a fixed maximum capacity, a circular queue (or circular buffer) is an extremely efficient solution. It uses a fixed-size array and two pointers, head and tail. When a pointer reaches the end of the array, it "wraps around" to the beginning, using the modulo (%) operator. This reuses memory slots immediately, eliminating wasted space without needing to resize or slice the array.

This article provides a fantastic explanation and implementation.

The circular queue is a powerful pattern, especially in systems programming, device drivers, and streaming applications where you're dealing with fixed-size buffers.

Conclusion

You've now learned how to design and implement an efficient array-backed queue, moving from a naive but flawed approach to an optimized one using a head index and amortization. This journey from identifying a performance bottleneck to devising a clever solution is at the heart of algorithmic thinking.

Here are your key takeaways:

• FIFO vs. LIFO: Queues follow a First-In, First-Out principle, unlike the Last-In, First-Out principle of stacks.
• The shift() Trap: Using Array.prototype.shift() for dequeue is an $O(n)$ operation and should be avoided in performance-critical code.
• The Head Index Optimization: Maintaining a head index allows for an $O(1)$ dequeue operation by logically, rather than physically, removing elements.
• Amortized Analysis: The memory cost of the head index approach can be managed by periodic cleanup. This makes the dequeue operation have an amortized constant-time complexity.
• Alternatives: For fixed-size buffers, the circular queue offers a highly efficient $O(1)$ implementation without the need for amortization.

In our next lesson, we'll return to the stack data structure to explore a more advanced and powerful pattern: the monotonic stack. You'll learn how to use it to efficiently solve problems like finding the next greater or smaller element for every item in an array.