Queue: Linear, Circular, Priority Queue and Deque

Queue as an ADT

A queue is an ordered list where elements are inserted at one end, the rear, and deleted from the other end, the front. The first element in is the first one out: FIFO (First In, First Out), like a line at a ticket counter.

Operations: enqueue(x) (insert at rear), dequeue() (delete from front), peek()/front(), isEmpty(), isFull().

Linear queue (array)

#define MAX 5
int q[MAX], front = -1, rear = -1;

void enqueue(int x) {
    if (rear == MAX - 1) { printf("Queue full\n"); return; }
    if (front == -1) front = 0;
    q[++rear] = x;
}

int dequeue(void) {
    if (front == -1 || front > rear) { printf("Queue empty\n"); return -1; }
    return q[front++];
}

Limitation of the linear queue

Suppose MAX = 5. Enqueue 10, 20, 30, 40, 50: rear = 4 (full). Dequeue three times: front = 3. Positions 0, 1 and 2 are now free, but rear == MAX − 1, so another enqueue says "Queue full". The freed space at the front can never be reused. This wastes memory.

Circular queue

A circular queue treats the array as a circle: after the last position comes the first. Indexes advance with modulo arithmetic:

• rear = (rear + 1) % MAX
• front = (front + 1) % MAX

Conditions (using front = rear = -1 for empty):

• Empty: front == −1
• Full: (rear + 1) % MAX == front

void enqueue(int x) {
    if ((rear + 1) % MAX == front) { printf("Queue full\n"); return; }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    q[rear] = x;
}

int dequeue(void) {
    if (front == -1) { printf("Queue empty\n"); return -1; }
    int x = q[front];
    if (front == rear) front = rear = -1;       /* it was the last element */
    else front = (front + 1) % MAX;
    return x;
}

In the example above, after three dequeues, the next enqueue goes into position 0, so no space is wasted.

Priority queue

A priority queue stores elements with a priority, and dequeue always removes the element with the highest priority (or lowest, in a min-priority queue). Elements with equal priority are served in FIFO order.

• Ascending priority queue: the smallest element is removed first.
• Descending priority queue: the largest element is removed first.

Implementations: an unordered array (insert O(1), delete O(n)), a sorted list (insert O(n), delete O(1)), or a heap (both O(log n), the best choice).

Uses: CPU scheduling, Dijkstra's shortest path algorithm, Huffman coding, hospital emergency queues.

Deque (double-ended queue)

A deque allows insertion and deletion at both ends: insertFront, insertRear, deleteFront, deleteRear.

• Input-restricted deque: insertion at one end only, deletion at both.
• Output-restricted deque: deletion at one end only, insertion at both.

A deque can act as both a stack and a queue.

Applications of queue

• CPU and disk scheduling
• Printer spooling
• Breadth-first search of a graph
• Buffers in keyboards and network routers
• Call centre systems

Exam tip

The question "What is the limitation of a linear queue, and how does a circular queue solve it?" repeats often. Draw both arrays: show the wasted slots in the linear queue, then show rear wrapping to index 0 in the circular queue.