C++UCS301
Linear Data StructuresC++17

Queues & Deques

Queues process data FIFO. Circular arrays prevent wasted capacity, while deques permit operations at both ends.

Open this in the visual lab

What to understand

  • enqueue and dequeue
  • Circular indexing
  • Linked queues
  • Deque variants

Remember this

  1. 1First in, first out
  2. 2Use modulo for circular wraparound
  3. 3BFS relies on a queue
  4. 4Deque supports both ends

Detailed notes

A queue separates insertion at the rear from removal at the front. FIFO ordering is essential when work must be processed in arrival order or by increasing graph distance.

A naive array queue wastes space after removals. Circular indexing reuses freed slots; a count or deliberately empty slot distinguishes full from empty when front and rear coincide.

How it works

  1. 1Choose and document the meaning of front and rear indices.
  2. 2Advance indices modulo capacity.
  3. 3Update count atomically with insertion or removal.
  4. 4Use a deque when both ends need public operations.

Worked trace

Circular wraparound

Capacity 5, front=3, count=3
  1. 1The occupied indices are 3, 4, and 0.
  2. 2Rear index is (front+count)%capacity = 1.
  3. 3Enqueue writes the new value at index 1.
  4. 4A dequeue advances front to index 4 without shifting data.
Result: Freed slots are reused; both operations remain O(1)

Where it is used

  • Task scheduling and buffering
  • Breadth-first search
  • Producer-consumer pipelines

Common mistakes

  • Treating front == rear as both full and empty without another rule
  • Shifting every element on dequeue
  • Calling front on an empty queue

Complexity analysis

OperationBestAverageWorstExtra space
enqueueO(1)O(1)O(1)O(1)
dequeueO(1)O(1)O(1)O(1)
frontO(1)O(1)O(1)O(1)
searchO(n)O(n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Circular array queue

Modulo arithmetic reuses array positions released by dequeue operations.

#include <stdexcept>
using namespace std;

template <typename T, int Capacity>
class CircularQueue {
    T data[Capacity];
    int frontIndex = 0, count = 0;
public:
    bool empty() const { return count == 0; }
    void enqueue(const T& value) {
        if (count == Capacity) throw overflow_error("queue full");
        int rear = (frontIndex + count) % Capacity;
        data[rear] = value;
        ++count;
    }
    void dequeue() {
        if (empty()) throw underflow_error("queue empty");
        frontIndex = (frontIndex + 1) % Capacity;
        --count;
    }
    T& front() {
        if (empty()) throw underflow_error("queue empty");
        return data[frontIndex];
    }
};
25 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.