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.

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
Advertisement

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