Implement Queue Using an Array

Implementing a Queue with an Array

A queue can be implemented using an array by maintaining the order of elements and controlling where new elements are inserted and where existing elements are removed. The queue follows the FIFO (First In, First Out) principle, so elements are added at the rear and removed from the front.

Arrays are convenient for demonstrating queue implementation because they provide indexed storage and are available in almost every programming language. However, the way the front of the queue is managed has an important effect on performance.

Front                         Rear
  ↓                             ↓
[ 10 ] [ 20 ] [ 30 ] [ 40 ]
  ↑                             ↑
Remove                        Add

Basic Array-Based Queue

The simplest approach is to store all queue elements in an array. A new element can be added with an array append operation, while the first element can be removed using an operation such as shift() in JavaScript.

const queue = [];

queue.push(10);
queue.push(20);
queue.push(30);

console.log(queue);
// [10, 20, 30]

const removed = queue.shift();

console.log(removed);
// 10

console.log(queue);
// [20, 30]

This implementation is easy to understand and works correctly for small queues. However, repeatedly removing the first element from a regular array can become inefficient because the remaining elements may need to be shifted or reindexed.

Why Front Indexing Matters

A more efficient array-based queue keeps track of the position of the front element instead of physically removing the first array element after every dequeue operation.

Consider the following queue:

queue = [10, 20, 30, 40]
front = 0

Front points to:
queue[0] → 10

After removing 10, the implementation can simply increment front.

queue = [10, 20, 30, 40]
front = 1

Front now points to:
queue[1] → 20

The value 10 remains physically stored in the array, but it is no longer considered part of the active queue. The active queue is represented by the elements from the front index onward.

Array Queue Structure

An efficient array-based queue commonly maintains two pieces of information:

• Queue array: Stores the elements.
• Front index: Identifies the next element that should be removed.

The rear can be represented by the current array length when elements are always appended using push().

Array:  [10] [20] [30] [40] [50]
          ↑               ↑
        front            rear

front = 0

After dequeue:

Array:  [10] [20] [30] [40] [50]
               ↑           ↑
             front        rear

front = 1

Enqueue in an Array Queue

The enqueue operation adds a new value to the rear of the queue. With a JavaScript array, push() can be used for this purpose.

const queue = [];
let front = 0;

queue.push(10);
queue.push(20);
queue.push(30);

console.log(queue);
// [10, 20, 30]

Appending an element does not affect the front index. The newly inserted value simply becomes the newest element at the rear.

Dequeue Using a Front Index

Instead of calling shift(), dequeue can read the element at the current front index and then increment that index.

const queue = [10, 20, 30];
let front = 0;

const removed = queue[front];
front++;

console.log(removed); // 10
console.log(queue[front]); // 20

The active queue is now represented by the values starting at front. No elements need to be shifted toward the beginning of the array.

Complete Array Queue Implementation

The following implementation provides the common queue operations using an array and a front index.

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

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

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

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

  peek() {
    if (this.isEmpty()) {
      return null;
    }

    return this.items[this.front];
  }

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

  size() {
    return this.items.length - this.front;
  }
}

const queue = new Queue();

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.peek());    // 10
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
console.log(queue.size());    // 1

How the Implementation Works

Suppose three elements are inserted:

enqueue(10)
enqueue(20)
enqueue(30)

items = [10, 20, 30]
front = 0

The first dequeue reads items[0] and advances the front index.

dequeue()

removed = items[0]
front = 1

Active queue:
[20, 30]

A second dequeue reads items[1] and advances the front again.

dequeue()

removed = items[1]
front = 2

Active queue:
[30]

The underlying array still contains the earlier values, but the front index determines which portion is currently active.

Checking Whether the Queue Is Empty

With front indexing, the queue is empty when the front index reaches or passes the array length.

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

For example, if the array contains three inserted values and the front index is 3, there are no active elements left in the queue.

items = [10, 20, 30]
front = 3

isEmpty() → true

Calculating Queue Size

The number of active elements can be calculated using the difference between the array length and the front index.

size = items.length - front

If the array contains five values and the front index is 2, the active queue contains three elements.

items.length = 5
front = 2

size = 5 - 2
     = 3

Handling an Empty Queue

Dequeue and peek operations should check whether the queue is empty before accessing an element. Returning null is one possible design, although other applications may prefer an exception or another explicit result.

dequeue() {
  if (this.isEmpty()) {
    return null;
  }

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

This prevents the implementation from returning an invalid queue element when no active values remain.

The Memory Trade-Off

Front indexing improves dequeue performance, but it introduces another consideration: values that have already been removed remain in the underlying array.

After many dequeues:

items = [10, 20, 30, 40, 50, 60, 70]
                         ↑
                       front = 5

Active queue:
[60, 70]

Unused prefix:
[10, 20, 30, 40, 50]

If a queue is long-lived and processes a large number of elements, retaining this unused prefix can consume unnecessary memory. A production implementation can periodically compact the array or use a different queue structure.

Compacting the Array

One approach is to periodically remove the inactive prefix when it becomes large enough. This should not be performed after every dequeue because doing so would reintroduce repeated shifting costs.

compact() {
  if (this.front > 0 && this.front >= this.items.length / 2) {
    this.items = this.items.slice(this.front);
    this.front = 0;
  }
}

This strategy allows the implementation to reclaim unused space occasionally while keeping normal dequeue operations efficient. The exact compaction strategy depends on the workload and memory requirements.

Circular Array Queue

Another important array-based approach is a circular queue. Instead of allowing the front of the queue to move permanently toward the end of the array, the implementation reuses positions that become available after dequeue operations.

Initial:
[10] [20] [30] [40] [50]

After removing 10 and 20:
[  ] [  ] [30] [40] [50]

New elements can wrap around:
[60] [70] [30] [40] [50]
 ↑
rear wraps to beginning

Circular queues are particularly useful when a fixed amount of storage is available and memory positions should be reused. The circular queue is covered in more detail as a separate queue type.

Array Queue Complexity

The complexity of an array-based queue depends on how its operations are implemented. Using a front index avoids the repeated shifting associated with removing the first array element.

The exact enqueue complexity can vary because dynamic arrays may occasionally resize their internal storage. Over a sequence of appends, the usual amortized complexity is O(1).

Array Queue vs Shift-Based Queue

Both approaches are valid for demonstrating queue behavior, but they make different performance trade-offs.

When an Array Is a Good Choice

An array can be a practical choice for implementing a queue when direct indexed storage is convenient and the expected workload is compatible with the implementation.

• The queue needs compact contiguous storage.
• The maximum capacity is known and a circular implementation is suitable.
• The language provides an efficient array-based queue abstraction.
• You want a simple implementation for learning or small workloads.
• Memory locality and predictable storage are useful for the application.

Common Implementation Mistakes

• Using shift() repeatedly without considering its cost for large queues.
• Forgetting to advance the front index after dequeue.
• Reading from the queue without checking whether it is empty.
• Calculating the queue size as items.length when a front index is being used.
• Allowing unused elements at the beginning of a long-lived queue to grow without considering memory usage.
• Resetting the front index incorrectly when the queue becomes empty.

Practical Example: Processing Requests

An array-based queue can represent requests waiting to be processed. New requests are appended to the rear, while the front index identifies the next request that should be handled.

const requests = [];
let front = 0;

function addRequest(request) {
  requests.push(request);
}

function processRequest() {
  if (front >= requests.length) {
    return null;
  }

  return requests[front++];
}

addRequest("Request A");
addRequest("Request B");
addRequest("Request C");

console.log(processRequest()); // Request A
console.log(processRequest()); // Request B
console.log(processRequest()); // Request C
console.log(processRequest()); // null

The example demonstrates the core idea of an array-based queue: new work enters at the end, while processing moves forward through the array.

Key Takeaways

• An array can be used to implement a queue by maintaining FIFO ordering.
• New elements are normally added at the rear using an append operation.
• A front index can identify the next element to dequeue without shifting the remaining elements.
• Using shift() is simple but can be inefficient for large queues.
• Front indexing provides O(1) dequeue behavior while introducing inactive space at the beginning of the array.
• Long-lived queues may need compaction or a circular array to reuse storage.
• Circular queues are useful when fixed array capacity and memory reuse are important.
• The implementation should always handle empty-queue operations safely.