QueuesLesson 3

Circular Queues and Deques

Circular queues wrap around to reuse space. Deques allow insertion and removal from both ends. Learn both implementations.

What Is It?

In the last lesson, we saw that a simple array queue wastes space. As elements are dequeued, the front index moves right, leaving empty slots at the start of the array that can never be reused.

A circular queue fixes this by treating the array like a ring. When the rear index reaches the end of the array, it wraps back around to the beginning and reuses those empty slots.

A deque (short for double-ended queue, pronounced "deck") goes one step further. It lets you add and remove from both ends — front and back. A deque can act as a stack, a queue, or both.

Analogy

Circular queue: Picture a circular conveyor belt at a sushi restaurant with 8 spots. The chef places sushi at one position (the rear) and customers take sushi from another position (the front). When the chef fills spot 8, they loop back to spot 1 and keep placing sushi in empty spots. The belt just goes around and around — no spot is ever permanently wasted.

Deque: Imagine a hallway with doors at both ends. A regular queue only lets people enter from the back door and leave from the front door. A deque opens both doors for entering and leaving — you can come in or leave from either end.

How It Works

CIRCULAR QUEUE

#### The Core Idea: Wrap Around Using Modulo

Instead of just adding 1 to the rear index, we wrap it around:

pseudocode
1
2
rear = (rear + 1) mod CAPACITY
front = (front + 1) mod CAPACITY

The modulo operator (mod) gives you the remainder after division. When rear is at the last index and you do (last_index + 1) mod CAPACITY, you get 0 — it wraps back to the start.

Example with capacity 5: (4 + 1) mod 5 = 0. The index jumps from 4 back to 0.

#### Visualizing the Wraparound

Imagine capacity 5. We enqueue 10, 20, 30, 40, 50 (filling it), dequeue 10 and 20, then enqueue 60 and 70:

pseudocode
1
2
3
4
5
6
7
8
After filling and dequeuing 10, 20:
  [  ][  ][30][40][50]   front=2, rear=0, count=3
​
After enqueue(60) - rear wraps to 0:
  [60][  ][30][40][50]   front=2, rear=1, count=4
​
After enqueue(70) - rear moves to 1:
  [60][70][30][40][50]   front=2, rear=2, count=5  FULL

Slots 0 and 1 that were freed up are now being reused. No space wasted.

The array in linear form:

Circular Queue — Linear View— Data wraps around: index 0 holds a value enqueued after indices 4-5
idx 0
idx 1
idx 2
idx 3
idx 4
idx 5
70
30
40
50
60
rear
front

Logical order (front to rear): 30, 40, 50, 60, 70. The modulo arithmetic makes wraparound seamless.

See how 60 and 70 filled in at the beginning of the array — after the values at indices 2, 3, 4.

#### Full Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
structure CircularQueue:
    array = new array of size CAPACITY
    front = 0
    rear = 0
    count = 0
​
function enqueue(queue, value):
    if isFull(queue):
        error("Queue is full")
    queue.array[queue.rear] = value
    queue.rear = (queue.rear + 1) mod CAPACITY
    queue.count = queue.count + 1
​
function dequeue(queue):
    if isEmpty(queue):
        error("Queue is empty")
    value = queue.array[queue.front]
    queue.front = (queue.front + 1) mod CAPACITY
    queue.count = queue.count - 1
    return value
​
function isEmpty(queue):
    return queue.count equals 0
​
function isFull(queue):
    return queue.count equals CAPACITY

#### Tracing the Wraparound Step by Step

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Capacity = 5
​
Operation        front  rear  count  Array [0][1][2][3][4]
---------        -----  ----  -----  --------------------
(initial)          0     0     0     [ ][ ][ ][ ][ ]
enqueue(10)        0     1     1     [10][ ][ ][ ][ ]
enqueue(20)        0     2     2     [10][20][ ][ ][ ]
enqueue(30)        0     3     3     [10][20][30][ ][ ]
dequeue()->10      1     3     2     [  ][20][30][ ][ ]
dequeue()->20      2     3     1     [  ][  ][30][ ][ ]
enqueue(40)        2     4     2     [  ][  ][30][40][ ]
enqueue(50)        2     0     3     [50][  ][30][40][ ]   rear wraps: (4+1)%5=0
enqueue(60)        2     1     4     [50][60][30][40][ ]
dequeue()->30      3     1     3     [50][60][  ][40][ ]
enqueue(70)        3     2     4     [50][60][70][40][ ]
enqueue(80)        3     3     5     [50][60][70][40][80]  FULL

At enqueue(50), rear was at index 4. (4+1) % 5 = 0 — it wrapped to 0. That is the circular queue doing its job.

DEQUE (Double-Ended Queue)

A deque supports four operations instead of two:

  1. pushFront(value) — Add to the front.
  2. pushBack(value) — Add to the back (same as enqueue).
  3. popFront() — Remove from the front (same as dequeue).
  4. popBack() — Remove from the back.
pseudocode
1
2
3
4
5
6
7
8
9
  pushFront            pushBack
      |                    |
      v                    v
 +------+------+------+------+
 |  10  |  20  |  30  |  40  |
 +------+------+------+------+
      ^                    ^
      |                    |
  popFront              popBack

#### Deque as Stack and Queue

  • pushBack + popBack = a stack (last in, first out)
  • pushBack + popFront = a queue (first in, first out)

A deque can do the job of both. That is why it is called the most flexible linear data structure.

#### Implementation Using a Circular Array

We extend the circular queue idea. The difference: front can now move backward (for pushFront) and rear can move backward (for popBack).

To move an index backward without going negative, use this formula:

pseudocode
1
(index - 1 + CAPACITY) mod CAPACITY

Example with capacity 8: (0 - 1 + 8) mod 8 = 7. Moving backward from index 0 lands on index 7.

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function pushFront(deque, value):
    if isFull(deque):
        error("Deque is full")
    deque.front = (deque.front - 1 + CAPACITY) mod CAPACITY
    deque.array[deque.front] = value
    deque.count = deque.count + 1
​
function pushBack(deque, value):
    if isFull(deque):
        error("Deque is full")
    deque.array[deque.rear] = value
    deque.rear = (deque.rear + 1) mod CAPACITY
    deque.count = deque.count + 1
​
function popFront(deque):
    if isEmpty(deque):
        error("Deque is empty")
    value = deque.array[deque.front]
    deque.front = (deque.front + 1) mod CAPACITY
    deque.count = deque.count - 1
    return value
​
function popBack(deque):
    if isEmpty(deque):
        error("Deque is empty")
    deque.rear = (deque.rear - 1 + CAPACITY) mod CAPACITY
    value = deque.array[deque.rear]
    deque.count = deque.count - 1
    return value

#### Tracing Deque Operations

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Capacity = 5
​
Operation          front  rear  count  Array [0][1][2][3][4]
---------          -----  ----  -----  --------------------
(initial)            0     0     0     [ ][ ][ ][ ][ ]
pushBack(20)         0     1     1     [20][ ][ ][ ][ ]
pushBack(30)         0     2     2     [20][30][ ][ ][ ]
pushFront(10)        4     2     3     [20][30][ ][ ][10]
                                        front wraps: (0-1+5)%5=4
pushBack(40)         4     3     4     [20][30][40][ ][10]
pushFront(5)         3     3     5     [20][30][40][5][10]
                                        front: (4-1+5)%5=3
​
Logical order front->rear: 5, 10, 20, 30, 40
​
popFront()->5        4     3     4     [20][30][40][ ][10]
popBack()->40        4     2     3     [20][30][ ][ ][10]
popFront()->10       0     2     2     [20][30][ ][ ][ ]
popFront()->20       1     2     1     [ ][30][ ][ ][ ]
popFront()->30       2     2     0     EMPTY

#### Deque with a Doubly Linked List

You can also build a deque using a doubly linked list — a chain where each node has a pointer to both the next and previous nodes. This gives you fast operations at both ends without any capacity limit.

pushFront
O(1)
pushBack
O(1)
popFront
O(1)
popBack
O(1)

All four operations are fast with a doubly linked list. The trade-off is a little extra memory per node (two pointers instead of one).

Examples

Example 1: Circular Queue Wrapping Around

pseudocode
1
2
3
4
5
6
7
8
9
ticketQueue = new CircularQueue(capacity=4)
​
enqueue(ticketQueue, "Ticket #1")  // front=0, rear=1
enqueue(ticketQueue, "Ticket #2")  // front=0, rear=2
dequeue(ticketQueue)               // returns "Ticket #1", front=1
enqueue(ticketQueue, "Ticket #3")  // front=1, rear=3
enqueue(ticketQueue, "Ticket #4")  // front=1, rear=0  (wraps!)
// Array: [#4][#2][#3][ ]  with front=1, rear=0
// No wasted space!

Example 2: Deque as Both Stack and Queue

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
dq = new CircularDeque(capacity=10)
​
// Use as queue (FIFO)
pushBack(dq, 1)
pushBack(dq, 2)
pushBack(dq, 3)
popFront(dq)  // returns 1
​
// Use as stack (LIFO)
pushBack(dq, 4)
pushBack(dq, 5)
popBack(dq)   // returns 5

Example 3: Sliding Window Maximum

Deques are the key tool for the sliding window maximum problem. You keep a deque of indices where values are in decreasing order. For each new element, remove smaller values from the back. The front always holds the index of the maximum for the current window.

Common Mistakes

1. Forgetting to add CAPACITY before taking the modulo when moving backward. (front - 1) mod CAPACITY can give a negative result in many languages. Always use (front - 1 + CAPACITY) mod CAPACITY.

2. Mixing up full and empty states. If you do not track count, then front == rear looks the same whether the deque is empty or full. Always use a count variable.

3. Wrong index for peekBack. The rear index points to the NEXT empty slot, not the last filled one. The last element is at (rear - 1 + CAPACITY) mod CAPACITY.

4. Forgetting to wrap every single index update. Every time you change front or rear, you must apply the modulo. Missing even one causes an out-of-bounds error.

Best Practices

Use a circular queue instead of a naive array queue. It uses the same array with just one extra formula and eliminates the wasted-space problem.

Use a count variable for full and empty checks. It is the clearest approach and uses every array slot.

Learn the two modulo formulas by heart. Forward: (index + 1) mod CAPACITY. Backward: (index - 1 + CAPACITY) mod CAPACITY. These two handle all circular indexing.

Pick circular array for fixed-size deques, doubly linked list for unlimited size. If you know the max size, the array is simpler and faster. If not, the linked list avoids running out of space.

Implementing a QueueHow Hashing Works