All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Queues, Deques & Circular Queues

Queues, Deques & Circular Queues

0/14 in this phase0/57 across the roadmap

📖 Concept

A queue is a FIFO (First In, First Out) data structure. Like a line at a coffee shop — first person in line gets served first.

Operations — ALL O(1) with proper implementation:

  • enqueue(item) — Add to back
  • dequeue() — Remove from front
  • peek()/front() — View front element
  • isEmpty() — Check if empty

Types of queues:

  1. Queue — Standard FIFO
  2. Deque — Double-ended queue, add/remove from both ends
  3. Circular Queue — Fixed-size, wraps around to reuse space
  4. Priority Queue — Elements dequeued by priority (covered in Phase 4 with heaps)

⚠️ Array-based queue in JavaScript is O(n) for dequeue!

  • arr.shift() is O(n) — it shifts all elements left
  • For O(1) dequeue, use a linked list or circular buffer
  • Or use the "pointer offset" trick (track front index)

Where queues appear:

  • BFS traversal — level-order tree/graph traversal
  • Task scheduling — print queue, process queue
  • Rate limiting — sliding window of requests
  • Buffering — data streams, message queues

🏠 Real-world analogy: A queue is a line at the bank. A deque is a hospital ER — high-priority patients can go to the front. A circular queue is a round table where everyone takes turns.

💻 Code Example

codeTap to expand ⛶
1// QUEUE — Linked list-based O(1) operations
2class QueueNode {
3  constructor(val) { this.val = val; this.next = null; }
4}
5

6class Queue {
7  constructor() { this.front = null; this.back = null; this.size = 0; }
8

9  enqueue(val) {
10    const node = new QueueNode(val);
11    if (this.back) this.back.next = node;
12    this.back = node;
13    if (!this.front) this.front = node;
14    this.size++;
15  }
16

17  dequeue() {
18    if (!this.front) return null;
19    const val = this.front.val;
20    this.front = this.front.next;
21    if (!this.front) this.back = null;
22    this.size--;
23    return val;
24  }
25

26  peek() { return this.front?.val ?? null; }
27  isEmpty() { return this.size === 0; }
28}
29

30// CIRCULAR QUEUE — Fixed size, O(1) all operations
31class CircularQueue<T> {
32  private data: (T | undefined)[];
33  private front: number = 0;
34  private rear: number = -1;
35  private count: number = 0;
36  private capacity: number;
37

38  constructor(k: number) {
39    this.capacity = k;
40    this.data = new Array(k);
41  }
42

43  enqueue(val: T): boolean {
44    if (this.isFull()) return false;
45    this.rear = (this.rear + 1) % this.capacity;
46    this.data[this.rear] = val;
47    this.count++;
48    return true;
49  }
50

51  dequeue(): T | undefined {
52    if (this.isEmpty()) return undefined;
53    const val = this.data[this.front];
54    this.front = (this.front + 1) % this.capacity;
55    this.count--;
56    return val;
57  }
58

59  peek(): T | undefined { return this.isEmpty() ? undefined : this.data[this.front]; }
60  isEmpty(): boolean { return this.count === 0; }
61  isFull(): boolean { return this.count === this.capacity; }
62}
63

64// BFS using a queue — Level order traversal
65function bfs(root) {
66  if (!root) return [];
67  const result = [];
68  const queue = [root];
69  while (queue.length) {
70    const levelSize = queue.length;
71    const level = [];
72    for (let i = 0; i < levelSize; i++) {
73      const node = queue.shift();
74      level.push(node.val);
75      if (node.left) queue.push(node.left);
76      if (node.right) queue.push(node.right);
77    }
78    result.push(level);
79  }
80  return result;
81}
82

83// DEQUE — Double-ended queue
84class Deque {
85  constructor() { this.items = []; }
86  addFront(val) { this.items.unshift(val); }  // O(n) with array
87  addBack(val)  { this.items.push(val); }     // O(1)
88  removeFront() { return this.items.shift(); } // O(n) with array
89  removeBack()  { return this.items.pop(); }   // O(1)
90  peekFront()   { return this.items[0]; }
91  peekBack()    { return this.items[this.items.length - 1]; }
92  isEmpty()     { return this.items.length === 0; }
93}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Implement a queue using a linked list (O(1) enqueue/dequeue)
  2. Implement a queue using two stacks
  3. Implement a circular queue with fixed capacity
  4. Generate binary numbers from 1 to n using a queue
  5. Implement a recent counter (count requests in last 3000ms)
  6. Design a hit counter using a circular buffer
  7. Sliding window maximum using a deque (O(n) solution)
  8. Implement a task scheduler with cooldown
  9. BFS to find shortest path in a grid
  10. Design a snake game using a deque

⚠️ Common Mistakes

  • Using Array.shift() for queue dequeue — it's O(n) because it shifts all elements

  • Not handling empty queue for dequeue/peek — always check isEmpty first

  • Forgetting that circular queue uses modulo to wrap around: (index + 1) % capacity

  • Confusing stack (LIFO) with queue (FIFO) — stack uses push/pop, queue uses push/shift or enqueue/dequeue

  • Not realizing that BFS = queue, DFS = stack — this is fundamental

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Queues, Deques & Circular Queues

← PreviousStacks — Implementation & ApplicationsNext →Hash Tables & Hash Maps — Internal Working