Queue Basics

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line at a store - the first person in line is the first to be served.

Core Operations

• Enqueue: Add an element to the back of the queue - O(1)
• Dequeue: Remove and return the front element - O(1)
• Peek/Front: View the front element without removing it - O(1)
• isEmpty: Check if the queue is empty - O(1)

When to Use Queues

Queues are ideal when you need to:

• Process items in order of arrival
• Implement breadth-first search (BFS)
• Handle tasks in a scheduling system
• Buffer data streams
• Implement caching systems (FIFO eviction)

Implementation with Array

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

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

  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift(); // O(n) - not ideal!
  }

  front() {
    if (this.isEmpty()) return null;
    return this.items[0];
  }

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

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

Better Implementation with Two Pointers

class Queue:
    def __init__(self):
        self.items = []
        self.front_index = 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return None

        item = self.items[self.front_index]
        self.front_index += 1

        # Reset when queue is empty
        if self.front_index == len(self.items):
            self.items = []
            self.front_index = 0

        return item

    def front(self):
        if self.is_empty():
            return None
        return self.items[self.front_index]

    def is_empty(self):
        return self.front_index >= len(self.items)

    def size(self):
        return len(self.items) - self.front_index

Using Python's deque

Python's collections.deque is optimized for queue operations:

from collections import deque

queue = deque()
queue.append(1)      # Enqueue
queue.append(2)
item = queue.popleft()  # Dequeue - O(1)
front = queue[0]     # Peek

JavaScript Queue Pattern

// Using array methods (not optimal)
const queue = [];
queue.push(1); // Enqueue
const item = queue.shift(); // Dequeue

// Better: Use two arrays
class OptimizedQueue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
  }

  enqueue(item) {
    this.inbox.push(item);
  }

  dequeue() {
    if (this.outbox.length === 0) {
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
    return this.outbox.pop();
  }
}

Key Insight

Queues preserve order - the first item enqueued is the first item dequeued. This makes them perfect for problems requiring level-by-level or breadth-first processing.