Queue

What is a queue?

A queue is a linear data structure where items are added at one end, the rear, and removed from the other end, the front.

Think of the line at a ticket counter or a canteen. New people join at the back of the line. The person at the front is served and leaves. Nobody cuts in line.

This rule is called FIFO — First In, First Out: whoever arrived first is served first.

A stack removes the newest item (LIFO). A queue removes the oldest item (FIFO). That one difference changes everything about how they are used.

Operations

Operation	What it does	Ticket line analogy
enqueue(x)	Add x at the rear	A new person joins the back
dequeue()	Remove and return the front item	The first person is served and leaves
peek() / front()	Look at the front item without removing it	See who is next
isEmpty(), isFull()	Check the size	Is anyone waiting? Is the hall full?

The simple (shifting) queue

The easiest way to build a queue is with an array, where the front is always index 0:

• Enqueue: write the value at index size, then size = size + 1.
• Dequeue: take queue[0], then shift every other element one place left.

Try Simple queue mode in the model above. Enqueue is instant, but every dequeue makes the whole line shuffle forward. With n elements that is n − 1 moves, so dequeue costs O(n). For a queue with a million items, that’s a million moves for every single dequeue!

The circular queue — the clever fix

Instead of moving the people, we move the counter. Keep two indexes:

• front — where the oldest element is,
• rear — where the newest element is.

Dequeue just does front = front + 1. Enqueue does rear = rear + 1. Nobody else moves.

But then front and rear keep drifting right and would fall off the end of the array. The trick is to wrap around using the modulo operator:

rear  = (rear + 1)  % capacity
front = (front + 1) % capacity

So after index 6 comes index 0 again — as if the array were bent into a ring. That is exactly what the Circular queue mode shows in 3D. Now both enqueue and dequeue are O(1).

To tell “full” from “empty” (in both cases front and rear can sit next to each other), we also keep a size counter.

Code (circular queue)

class CircularQueue:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.rear = -1
        self.size = 0

    def enqueue(self, x):
        if self.size == self.capacity:
            raise OverflowError("Queue is full")
        self.rear = (self.rear + 1) % self.capacity
        self.items[self.rear] = x
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("Queue is empty")
        x = self.items[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return x

q = CircularQueue(7)
q.enqueue(12); q.enqueue(45); q.enqueue(7)
print(q.dequeue())   # 12  (first in, first out)

#include <iostream>
#include <stdexcept>
using namespace std;

class CircularQueue {
    int items[7];
    int capacity = 7, front = 0, rear = -1, size = 0;
public:
    void enqueue(int x) {
        if (size == capacity) throw overflow_error("Queue is full");
        rear = (rear + 1) % capacity;
        items[rear] = x;
        size++;
    }
    int dequeue() {
        if (size == 0) throw underflow_error("Queue is empty");
        int x = items[front];
        front = (front + 1) % capacity;
        size--;
        return x;
    }
};

int main() {
    CircularQueue q;
    q.enqueue(12); q.enqueue(45); q.enqueue(7);
    cout << q.dequeue() << "\n";   // 12
}

In everyday Python, use collections.deque (append and popleft are both O(1)). In C++ use std::queue, and in Java ArrayDeque.

Where are queues used?

• Printer and task queues — jobs are processed in the order they arrive.
• CPU scheduling — the Round-Robin scheduler keeps ready processes in a queue.
• Breadth-first search (BFS) in graphs — explore nodes level by level.
• Networking — routers buffer packets in queues.
• Customer support / ticket systems — first come, first served.

Variations you will meet

• Deque (double-ended queue): add and remove at both ends.
• Priority queue: the item with the highest priority leaves first, not the oldest — usually built with a binary heap.

Common mistakes

• Forgetting the % capacity, so rear runs past the end of the array.
• Using front == rear alone to detect “empty” — it is ambiguous; keep a size counter.
• Using a Python list with pop(0) as a queue: that is the O(n) shifting version.