A Queue is a linear data structure that follows the FIFO principle: the first element added is the first one to be removed. It's the standard model for handling requests and scheduling.

Think of a Line at a Coffee Shop:

1. The first person to join the line is the first person to get their coffee (Dequeue).
2. Any newcomer must join the very back of the line (Enqueue).
3. "Cutting" the line is not allowed in a standard queue!

---

Core Operations

• Enqueue: Adds an item to the back (rear) of the queue. ($O(1)$)
• Dequeue: Removes an item from the front (head) of the queue. ($O(1)$)
• Front: Returns the front item without removing it. ($O(1)$)
• Rear: Returns the last item. ($O(1)$)

Performance Note (JavaScript)

Using array.shift() to dequeue from a JavaScript array is $O(n)$ because every other element must be moved forward. For a proper $O(1)$ queue in JS, you should use a Linked List or track the head index manually.

---

javascript Standard
/**
 * Efficient Queue using a Linked List or Pointer
 * This ensures O(1) Dequeue.
 */
class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  // Add to back - O(1)
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  // Remove from front - O(1)
  dequeue() {
    if (this.isEmpty()) return undefined;
    
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  isEmpty() {
    return this.tailIndex - this.headIndex === 0;
  }
}

---

Use Cases

• BFS (Breadth-First Search): Queues are the core of level-order traversal in trees and graphs.
• Task Scheduling: Handling incoming web requests or print jobs.
• Rate Limiting: Sliding window logs often use a queue.

Must-Practice Problems

• Implement Stack using Queues: (And vice-versa).
• Recent Calls: Count requests in the last 3000ms.
• Circular Queue Design: Handling fixed-size memory efficiently.
• Sliding Window Maximum: (Requires a specialized queue called a Deque).