Queue Implementation Using Array

Queue Implementation Using Array

Implementing a Queue using an array is a fundamental approach where we use a fixed-size or dynamic array to store elements while maintaining FIFO order. The array implementation requires careful handling of front and rear pointers to efficiently enqueue and dequeue elements.

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

Basic Class Structure

class Queue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = -1;
    this.rear = -1;
    this.size = 0;
  }
  // Check if queue is full
  isFull() {
    return this.size === this.capacity;
  }
  // Check if queue is empty
  isEmpty() {
    return this.size === 0;
  }

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

Circular Array Note: The modulo operation (% capacity) enables the circular behavior by wrapping the pointer to the start when it reaches the end.

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

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

In a circular array implementation, we treat the array as circular to maximize space utilization. When either pointer reaches the end of the array, it wraps around to the beginning.

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

Queue 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

Explore other implementation

Using Linked List