Queue

Using Array

Queue Implementation Using Array

The simplest way to build a queue is to back it with an array and track a front index and a rear index. As long as those two indices are updated correctly on every enqueue and dequeue, the array behaves like a proper FIFO queue.

How Does It Work?

The array never moves — only the two indices do. front marks the element that leaves next, rear marks the last one that arrived, and every operation is just an index update:

  1. An empty queue of capacity 5. Both pointers start at -1, which is how the code tells empty apart from holding one element at index 0.
    01234front = -1, rear = -1, size 0
  2. enqueue(10), enqueue(20), enqueue(30): front is set to 0 on the first insert, and rear steps forward with each one.
    frontrear10020130234front = 0, rear = 2, size 3
  3. dequeue() twice: 10 and 20 are returned and front moves to index 2. Nothing is shifted — which is what keeps dequeue O(1) — but slots 0 and 1 are now stranded.
    frontdead0dead130234front = 2, rear = 2, size 1
  4. enqueue(40), enqueue(50): rear reaches index 4, the last slot. The check rear == capacity - 1 now reports the queue as full even though it only holds 3 of 5 elements.
    frontreardead0dead1302403504front = 2, rear = 4, size 3FULL — 2 wasted
Holds a live elementDequeued — stranded behind frontNever used yet

Step 4 is the flaw in the plain array approach. Two perfectly good slots sit empty at the start, but front only ever moves right, so nothing can reach them again. You can reclaim them by shifting every element down on each dequeue — at which point dequeue costs O(n) instead of O(1) — or you can let rear wrap around to index 0 with modulo arithmetic, which is exactly what a circular queue does and why it is the version normally used in practice.

Implementation Steps

  1. Initialize an array of fixed size (for static implementation) or dynamic array
  2. Initialize two pointers: front (for dequeue) and rear (for enqueue), both set to -1 initially
  3. Implement boundary checks for overflow (full queue) and underflow (empty queue) conditions
  4. For circular queue implementation, use modulo arithmetic for pointer updates

Enqueue Algorithm

  1. Check if queue is full (if (rear == capacity - 1) for linear array)
  2. For empty queue, set both front and rear to 0
  3. For circular queue: rear = (rear + 1) % capacity
  4. Insert new element at items[rear]
  5. Increment size counter

Dequeue Algorithm

  1. Check if queue is empty (front == -1)
  2. Store the front element to return later
  3. If only one element (front == rear), reset pointers to -1
  4. For circular queue: front = (front + 1) % capacity
  5. Decrement size counter
  6. Return the stored element

Time & Space Complexity

  • Enqueue Operation: O(1) - Amortized constant time for dynamic arrays
  • Dequeue Operation: O(1) - No shifting needed with pointer approach
  • Peek Operation: O(1) - Direct access via front pointer
  • Space Usage: O(n) - Linear space for storing elements

Because both enqueue and dequeue only touch an index and a single slot, none of them get slower as the queue fills up:

Pros and Cons

  • Pros: Simple implementation, cache-friendly (array elements contiguous in memory)
  • Pros: Efficient O(1) operations with pointer tracking
  • Cons: Fixed size limitation in static array implementation
  • Cons: Wasted space in linear array implementation without circular approach

Practical Considerations

The catch with a plain array is wasted space at the front once you've dequeued a few elements: the circular-array trick fixes that by letting the rear index wrap back around to index 0 once it hits the end.

Queues are widely used in scenarios like printer job scheduling, call center systems, and network packet handling where order preservation is crucial.

Daily DSA Challenge by Scale Engineer

Implementation (Enqueue & Dequeue)

// Queue Implementation in JavaScript (Array)
class Queue {
  constructor(size) {
    this.capacity = size;
    this.arr = new Array(size);
    this.front = this.rear = -1;
  }
  
  // Add element to the rear (enqueue)
  enqueue(item) {
    if ((this.rear + 1) % this.capacity === this.front) {
      console.log("Queue Overflow");
      return;
    }
    if (this.front === -1) {
      this.front = this.rear = 0;
    } else {
      this.rear = (this.rear + 1) % this.capacity;
    }
    this.arr[this.rear] = item;
  }
  
  // Remove element from front (dequeue)
  dequeue() {
    if (this.front === -1) {
      console.log("Queue Underflow");
      return -1;
    }
    const item = this.arr[this.front];
    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.capacity;
    }
    return item;
  }
}

// Usage Example
const queue = new Queue(5);
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20

Done With the Learning

Mark Queue implementation using Array as done and view it on your dashboard

Explore other implementation

Using Linked List