Step 3 of 5

60% Complete

Dequeue Operation

Learn how to remove elements from a queue

The Dequeue Operation

The dequeue operation removes and returns the element at the front of the queue. It's like serving the next person in line.

When implementing a queue, the dequeue operation is responsible for:

Removing the element from the front of the queue
Updating the front pointer (if applicable)
Decreasing the size of the queue
Returning the removed element

Array-based Implementation

In a simple array-based implementation, we use the shift() method to remove the first element from the array. However, this is inefficient as it requires shifting all remaining elements.

Dequeue Operation (Simple Array-based)

dequeue() {
  // Check if queue is empty
  if (this.isEmpty()) {
    return null; // Or throw an error
  }
  
  // Remove and return the front element
  return this.items.shift();
}

Before dequeuing:

After dequeuing (10 removed):

Key Points:

Time Complexity: O(n) - linear time
The shift() operation requires shifting all remaining elements
Simple to implement but inefficient for large queues
Always check if the queue is empty before dequeuing

Optimized Array Implementation

To improve the efficiency of the dequeue operation, we can use a more sophisticated approach with front and rear pointers.

Dequeue Operation (Optimized Array-based)

class OptimizedQueue {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(element) {
    this.items[this.rear] = element;
    this.rear++;
    return this;
  }
  
  dequeue() {
    // Check if queue is empty
    if (this.isEmpty()) {
      return null;
    }
    
    // Get the front element
    const item = this.items[this.front];
    
    // Delete the front element
    delete this.items[this.front];
    
    // Move front pointer
    this.front++;
    
    return item;
  }
  
  isEmpty() {
    return this.rear - this.front === 0;
  }
  
  size() {
    return this.rear - this.front;
  }
}

Key Points:

Time Complexity: O(1) - constant time
Uses an object instead of an array to avoid the shift operation
Front and rear pointers keep track of the queue boundaries
More efficient for large queues with frequent dequeue operations

Linked List-based Implementation

In a linked list-based implementation, we remove the node at the head of the linked list.

Dequeue Operation (Linked List-based)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
 
class LinkedListQueue {
  constructor() {
    this.head = null; // Front of the queue
    this.tail = null; // Rear of the queue
    this.size = 0;
  }
  
  // Enqueue method (for reference)
  enqueue(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
    return this;
  }
  
  dequeue() {
    // Check if queue is empty
    if (this.isEmpty()) {
      return null;
    }
    
    // Get the value of the head node
    const value = this.head.value;
    
    // If there's only one node
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      // Move head pointer to the next node
      this.head = this.head.next;
    }
    
    this.size--;
    return value;
  }
  
  isEmpty() {
    return this.size === 0;
  }
}

Key Points:

Time Complexity: O(1) - constant time
Special handling for the case when there's only one node
Updates the head pointer to the next node
No need to shift elements, making it more efficient

Circular Queue Implementation

In a circular queue, the dequeue operation removes the element at the front position and updates the front pointer.

Dequeue Operation (Circular Queue)

class CircularQueue {
  constructor(capacity = 5) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }
  
  // Enqueue method (for reference)
  enqueue(element) {
    if (this.isFull()) {
      throw new Error("Queue overflow");
    }
    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
    return this;
  }
  
  dequeue() {
    // Check if queue is empty
    if (this.isEmpty()) {
      return null;
    }
    
    // Get the front element
    const item = this.items[this.front];
    
    // Clear the front position
    this.items[this.front] = undefined;
    
    // Update front (wrap around if necessary)
    this.front = (this.front + 1) % this.capacity;
    
    // Decrement size
    this.size--;
    
    return item;
  }
  
  isEmpty() {
    return this.size === 0;
  }
  
  isFull() {
    return this.size === this.capacity;
  }
}

Key Points:

Time Complexity: O(1) - constant time
Uses modulo arithmetic to wrap around the array
Maintains the circular nature of the queue
Efficient for both enqueue and dequeue operations

Edge Cases and Considerations

Queue Underflow

Always check if the queue is empty before attempting to dequeue. Options for handling empty queues include:

Return null or undefined
Throw an error
Return a special value indicating failure

Memory Management

In some implementations, you might need to consider memory management:

In the optimized array implementation, the front and rear pointers keep increasing
Consider resetting the pointers when the queue becomes empty
In linked list implementations, removed nodes should be properly garbage collected

Practical Example

Let's see a complete example of a queue with both enqueue and dequeue operations:

class Queue {
  constructor() {
    this.items = [];
  }
  
  // Add an element to the queue
  enqueue(element) {
    this.items.push(element);
    return this;
  }
  
  // Remove and return the front element
  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.shift();
  }
  
  // Check if the queue is empty
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Get the size of the queue
  size() {
    return this.items.length;
  }
}
 
// Usage example
const queue = new Queue();
 
queue.enqueue(10).enqueue(20).enqueue(30);
console.log("Queue after enqueuing:", queue.items); // [10, 20, 30]
 
const firstItem = queue.dequeue();
console.log("Dequeued item:", firstItem); // 10
console.log("Queue after dequeuing:", queue.items); // [20, 30]
 
queue.enqueue(40);
console.log("Queue after enqueuing 40:", queue.items); // [20, 30, 40]
 
const secondItem = queue.dequeue();
console.log("Dequeued item:", secondItem); // 20
console.log("Queue after dequeuing again:", queue.items); // [30, 40]

Check Your Understanding

Next Steps

Now that you understand how to remove elements from a queue with the dequeue operation, let's move on to learning how to view the front element without removing it using the peek operation.