Queues, Circular Queues and Deques: short notes (Data Structures)

Revision mode

Introduction

A queue is a collection in which elements are inserted at one end, the rear, and removed from the other end, the front. The element removed is the one that has waited longest: first in, first out (FIFO). A ticket counter line is the usual picture.

Queues model anything served in arrival order: processes waiting for the CPU, packets waiting at a router, the frontier of breadth-first search, print jobs. This note covers the queue operations, the array implementation and why it is made circular, the exact empty and full conditions under the common index conventions, the linked implementation, the deque, and the relation to priority queues.

Conventions: C11; arrays are 0-based; $N$ is the array size.

Prerequisites

Arrays and Their Relation to Pointers: indexing.
Structures, Unions and Enumerations: nodes for the linked version.

Core concepts

The queue abstract data type

Operation	Effect	Error case
`enqueue(Q, x)`	insert `x` at the rear	overflow if a fixed-size queue is full
`dequeue(Q)`	remove and return the front element	underflow if empty
`front(Q)` (`peek`)	return the front element	underflow if empty
`isEmpty(Q)`, `isFull(Q)`	tests	none

The fixed array reserves $\Theta(N)$ storage; the linked representation stores $\Theta(n)$ nodes. Each ordinary operation uses $O(1)$ workspace (allocation cost assumed constant). All are $O(1)$ in the implementations below.

Why a linear array queue fails

If front and rear only ever increase, a queue in an array of size $N$ can accept at most $N$ enqueues in its lifetime: after a few enqueue and dequeue pairs, rear reaches the end of the array while the slots before front are empty but unusable. Shifting all elements down on every dequeue fixes this at $O(n)$ per dequeue. The standard fix is to wrap around: treat index $N-1$ as followed by index 0, so every index update is taken modulo $N$ .

Circular queue, convention A: one slot left empty

front is the index of the first element; rear is the index one past the last element.

#define N 5
int q[N], front = 0, rear = 0;

int isEmpty(void) { return front == rear; }
int isFull(void)  { return (rear + 1) % N == front; }
int enq(int x)  { if (isFull()) return 0; q[rear] = x; rear = (rear + 1) % N; return 1; }
int deq(int *x) { if (isEmpty()) return 0; *x = q[front]; front = (front + 1) % N; return 1; }
int count(void) { return (rear - front + N) % N; }

Empty: front == rear. Full: (rear + 1) % N == front.
The queue holds at most $N - 1$ elements. One slot is sacrificed because with all $N$ slots used, front == rear would also hold when full, and empty and full could not be told apart.
Number of elements: $(\text{rear} - \text{front} + N) \bmod N$ . The + N keeps the left operand of % non-negative; in C, % with a negative left operand gives a negative or zero result (Operators and Expressions).

Circular queue full and empty conditions — Figure 1. A circular queue of size 5 drawn as a ring. Empty: front equals rear. After enqueuing 10, 20, 30, 40 the queue is full with one free slot (rear + 1 equals front modulo 5). After two dequeues and two more enqueues the elements wrap past index 4.

Convention B: keep an explicit count

Store front and a counter n. The rear position is (front + n) % N; empty is n == 0 and full is n == N. All $N$ slots are usable, using the same number of variables as front-plus-rear by computing rear. A counter is an extra variable only if both front and rear are retained too.

Convention C: front and rear both start at $-1$

Many textbooks use front = rear = -1 for an empty queue, with rear the index of the last element. Enqueue sets front = 0 if the queue was empty, then rear = (rear + 1) % N. Dequeue reads q[front]; if front == rear the queue becomes empty and both are reset to $-1$ , otherwise front = (front + 1) % N. Full is (rear + 1) % N == front, and all $N$ slots are usable because emptiness is signalled by $-1$ , not by an index equality. Always identify the convention from the code given in a question before applying any formula.

Linked queue

Keep pointers to both ends of a singly linked list: dequeue at the head, enqueue at the tail.

struct node { int val; struct node *next; };
struct node *head = NULL, *tail = NULL;

void enq(int x) {                              /* allocation check omitted for brevity */
    struct node *n = malloc(sizeof *n);
    n->val = x; n->next = NULL;
    if (tail) tail->next = n; else head = n;   /* empty queue: new node is also the head */
    tail = n;
}
int deq(int *x) {
    struct node *n = head;
    if (!n) return 0;
    *x = n->val; head = n->next;
    if (!head) tail = NULL;                    /* queue became empty: reset tail too */
    free(n);
    return 1;
}

Both operations are $O(1)$ . Enqueueing at the head and dequeueing at the tail would make dequeue $O(n)$ in a singly linked list, because the node before the tail must be found. Forgetting to reset tail when the last node is removed leaves a dangling pointer (Dynamic Memory Allocation). A circular singly linked list with only a tail pointer also works: the head is tail->next.

How it works: deques and priority queues

Deque (double-ended queue)

A deque allows insertion and deletion at both ends: insertFront, insertRear, deleteFront, deleteRear, all $O(1)$ with a circular array or a doubly linked list. A stack and a queue are both restricted deques:

Restriction	Behaviour
insert and delete at the same end	stack
insert at one end, delete at the other	queue
input-restricted deque	insert at one end only, delete at both
output-restricted deque	insert at both ends, delete at one only

Priority queue

A priority queue removes the element of highest (or lowest) priority rather than the oldest one. It is not FIFO. An unsorted array gives $O(1)$ insert and $O(n)$ delete; a sorted array gives the reverse; a binary heap gives $O(\lg n)$ for both and is the standard choice.

Queue from two stacks, stack from two queues

Queue from two stacks: enqueue pushes onto stack IN; dequeue pops OUT, first moving all of IN into OUT if OUT is empty. Each element is moved once, so a sequence of $m$ operations costs $O(m)$ : amortised $O(1)$ . The two stacks together store $O(n)$ elements; this storage bound is separate from amortised time (Stacks).
Stack from two queues: to push, enqueue into an empty queue and then move every element of the other queue behind it, making push $O(n)$ and pop $O(1)$ ; or make pop the expensive operation instead. The two queues together use $O(n)$ storage.

Worked examples

C outputs below are for C11 with gcc on x86-64 Linux (LP64), $N = 5$ , convention A.

Example 1 (capacity $N - 1$ ). Enqueue 10, 20, 30, 40, 50 into an empty queue: four succeed, the fifth fails. Now count() = 4, front = 0, rear = 4.

Example 2 (wrap-around). Dequeue twice (returns 10, 20; front = 2), then enqueue 60 and 70. 60 goes to index 4 and 70 to index 0, so rear = 1. Then count() = (1 - 2 + 5) % 5 = 4 and the queue is full because (1 + 1) % 5 = 2 = front. Dequeuing everything returns 30 40 60 70 and leaves front = rear = 1: empty, but not at index 0.

Example 3 (convention B). With an explicit count, six enqueues into the same size-5 array accept five.

Example 4 (convention C, $N = 4$ ). Enqueue 1 to 5: the fifth is rejected as full (all 4 slots used). Dequeue (1), enqueue 6 (goes to index 0), then dequeue repeatedly: 2, 3, 4, 6, then underflow, and front = rear = -1.

Example 5 (linked queue). enq 1, enq 2, deq, enq 3, then dequeue until empty: outputs 2 3, and both head and tail end as NULL.

Important properties and observations

FIFO: elements leave in the order they arrived.
Circular arrays make every operation $O(1)$ and reuse freed slots.
Convention A wastes one slot; conventions B and C use all $N$ .
In a linked queue, enqueue at the tail and dequeue at the head.
Breadth-first search uses a queue; depth-first search uses a stack (Breadth-First Search).
Level-order traversal of a tree is breadth-first search with a queue (Binary Tree Traversals).
Round-robin CPU scheduling keeps the ready processes in a FIFO queue (CPU Scheduling).

GATE examination perspective

Full and empty conditions for a circular queue under the convention in the given code.
Number of elements from front and rear: $(\text{rear} - \text{front} + N) \bmod N$ for convention A.
Trace enqueue and dequeue with wrap-around; track both indices.
Which pointers change in a linked queue when the queue becomes empty or stops being empty.
Simulating one structure with another (queue from stacks) and the cost per operation.
Deque restrictions: which output orders an input- or output-restricted deque can produce.

Summary

Sources

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009: Section 10.1 (queues in a circular array; deques in Exercise 10.1-5), Section 6.5 (priority queues).
D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., Addison-Wesley, 1997: Section 2.2.1 (stacks, queues and deques; input- and output-restricted deques).