PadhaikoAll subjects

Queues

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

3.1 Definition of queue and its operations

Definition

Queue and FIFO Principle

A queue is a linear, ordered collection of homogeneous elements that operates on the First In, First Out (FIFO) principle. Elements are inserted at one designated end called the rear (or tail) and deleted from the opposite end called the front (or head).

The FIFO discipline mirrors everyday waiting lines: the first person to join the counter line is served and leaves first. In a queue, the relative order of insertion is strictly preserved upon removal.

Conceptual FIFO Queue ModelText
                 Enqueue (Insert)                             Dequeue (Delete)
                 at rear end                                  from front end
                      |                                             |
                      v                                             v
               +--------------+--------------+--------------+--------------+
  Rear Index ->|  Element D   |  Element C   |  Element B   |  Element A   |-> Front Index
               +--------------+--------------+--------------+--------------+
                 (Last in)                                     (First in)

Queue ADT Operations

As an Abstract Data Type (ADT), a queue defines a mathematical model along with a set of operations that manipulate data independently of the storage representation:

Queue ADT Primary Operations
OperationFormal SpecificationExceptional / Boundary StateTime Complexity
enqueue(Q, item)Appends item at the rear of queue QQueue Overflow if fixed storage is full
dequeue(Q)Removes and returns the element at the front of QQueue Underflow if Q is empty
front(Q) / peek(Q)Returns the value at the front without removing itError if Q is empty
rear(Q)Returns the value at the rear without removing itError if Q is empty
isEmpty(Q)Returns boolean true (1) if contains zero items, else false (0)None
isFull(Q)Returns boolean true (1) if has reached capacity, else false (0)Bounded representations only
size(Q)Returns the current count of elements currently stored in QNone

Applications of Queues in Computer Systems

Core Computer Science Applications of Queue Structures
Application AreaOperating MechanismSystem Examples
CPU SchedulingReady processes wait in a queue to be assigned CPU time slicesRound-Robin (RR) scheduling, Multilevel Feedback Queues
I/O & Print BufferingHarmonizes speed mismatch between fast CPUs and slow peripheral devicesPrinter spoolers (CUPS/Windows Spooler), disk write buffers
Graph TraversalTracks frontier vertices discovered during level-by-level explorationBreadth-First Search (BFS), shortest path in unweighted graphs
Network Packet HandlingRouters buffer incoming packets in packet queues during network congestionFIFO router queues, Fair Queueing algorithms
Asynchronous MessagingProducer-consumer architectures decouple sending and receiving threadsMessage brokers (RabbitMQ, Kafka), event-driven microservices

3.2 Array implementation of queue ADT

In a static array-based linear queue, elements are stored inside a one-dimensional array of fixed capacity MAX alongside two integer indices: front and rear.

Linear Queue Implementation in CC
#include <stdio.h>
#include <stdlib.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} LinearQueue;

void initQueue(LinearQueue *q) {
    q->front = 0;
    q->rear = -1;
}

int isEmpty(const LinearQueue *q) {
    return (q->rear < q->front);
}

int isFull(const LinearQueue *q) {
    return (q->rear == MAX - 1);
}

void enqueue(LinearQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
        return;
    }
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(LinearQueue *q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! Queue is empty\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front++;
    return value;
}

int peek(const LinearQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    return q->items[q->front];
}

The False Overflow Problem

A major limitation of the static linear queue is false overflow (also termed unutilized space syndrome):

  1. As items are inserted, rear increases until it reaches MAX - 1.
  2. As items are dequeued, front advances to the right, leaving vacant memory locations at items[0], items[1], etc.
  3. Once rear == MAX - 1, any subsequent call to enqueue() reports Queue Overflow, even if the first several slots are completely empty.
  4. Shifting remaining elements to index 0 on every dequeue requires time per deletion, destroying the desired performance guarantee.

3.3 Types of queue ADT: Linear, circular, double ended and priority queues

Queues are specialized into four primary variants based on entry/exit points, storage geometry, and prioritization rules.

3.3.1 Linear Queue

The simple linear queue maintains strict single-directional traversal where front and rear monotonically march forward:

3.3.2 Circular Queue

Definition

Circular Queue (Ring Buffer)

A circular queue is a linear data structure in which the last position of the underlying storage array is logically connected back to the first position, forming a continuous ring. Circular wrapping is governed by modular arithmetic: .

Circular Queue Design: Sacrificing One Cell Convention

In the standard textbook and university convention (used in lecture notes), we intentionally sacrifice one array slot to distinguish between an entirely empty queue and a completely full queue without requiring an additional counter variable:

Circular Queue with One Sacrificed Cell in CC
#include <stdio.h>
#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} CircularQueue;

void initCQueue(CircularQueue *cq) {
    cq->front = MAX - 1;
    cq->rear = MAX - 1;
}

int isCEmpty(const CircularQueue *cq) {
    return (cq->front == cq->rear);
}

int isCFull(const CircularQueue *cq) {
    return ((cq->rear + 1) % MAX == cq->front);
}

void enqueueC(CircularQueue *cq, int val) {
    if (isCFull(cq)) {
        printf("Circular Queue Overflow! Cannot insert %d\n", val);
        return;
    }
    cq->rear = (cq->rear + 1) % MAX;
    cq->items[cq->rear] = val;
}

int dequeueC(CircularQueue *cq) {
    if (isCEmpty(cq)) {
        printf("Circular Queue Underflow!\n");
        return -1;
    }
    cq->front = (cq->front + 1) % MAX;
    return cq->items[cq->front];
}
AspectLinear QueueCircular Queue
Memory ReuseFreed slots before front cannot be reusedFreed slots are reused immediately via modular wrap-around
Full Detectionrear == MAX - 1 (susceptible to false overflow)(rear + 1) % MAX == front
Max CapacityStores up to MAX items onceStores up to MAX - 1 items indefinitely under cycling
Index Advancementrear = rear + 1rear = (rear + 1) % MAX
EfficiencySpace-inefficient over extended runtimeSpace-optimal; continuously operates in fixed memory

3.3.3 Double-Ended Queue (Deque)

Definition

Double-Ended Queue (Deque)

A double-ended queue (abbreviated as deque, pronounced deck) is a generalized linear data structure wherein elements can be inserted and deleted at both the front and rear ends.

A deque subsumes both stacks and queues: it behaves as a FIFO queue when inserting at rear and deleting at front, and as a LIFO stack when insertions and deletions occur at the same end.

Deque Core Operations and Index Arithmetic
OperationBehaviorIndex Update (Circular Array Size MAX)
insertRear(x)Adds x to the backrear = (rear + 1) % MAX; items[rear] = x;
deleteFront()Removes item from the frontfront = (front + 1) % MAX; return items[front];
insertFront(x)Adds x to the frontitems[front] = x; front = (front - 1 + MAX) % MAX;
deleteRear()Removes item from the backitem = items[rear]; rear = (rear - 1 + MAX) % MAX; return item;

Restricted Deque Variations

Depending on which operations are permitted, deques are classified into two restricted types:

  1. Input-Restricted Deque:
    • Insertion is permitted at one end only (usually the rear).
    • Deletion is permitted from both ends (front and rear).
  2. Output-Restricted Deque:
    • Deletion is permitted from one end only (usually the front).
    • Insertion is permitted at both ends (front and rear).

3.3.4 Priority Queue

Definition

Priority Queue ADT

A priority queue is an abstract data structure in which every element possesses an associated priority key. Elements are dequeued according to priority rather than chronological arrival: an element with higher priority is processed before any element with lower priority.

If two elements share identical priority, they are served according to standard FIFO arrival ordering.

Types of Priority Queues

  1. Ascending Priority Queue: Items are removed in order of increasing priority key (the smallest numeric value has the highest priority, e.g. min-priority).
  2. Descending Priority Queue: Items are removed in order of decreasing priority key (the largest numeric value has the highest priority, e.g. max-priority).
Priority Queue Implementation Trade-offs
Underlying Data StructureInsertion ComplexityDeletion / Extract-MaxPeek (Top Priority)
Unordered Array (Linear scan for max)
Sorted / Ordered Array (Sorted insert with shifts) (Remove from end)
Binary Heap (Min/Max)
Balanced BST (AVL)

Worked Examples

Example 1

1

Trace the contents of a linear queue implemented via a static array of size (initially front = 0, rear = -1) under the following sequence of operations: enqueue(10), enqueue(20), enqueue(30), dequeue(), dequeue(), enqueue(40), enqueue(50), enqueue(60). Identify if and when false overflow occurs.

Executing the operations step by step: Track front, rear, the array slots items[0..3], and status updates:

Linear Queue Execution Trace (MAX = 4)
Operationfrontrearitems[0..3]Status / Output
Initial0-1[-, -, -, -]Queue is empty
enqueue(10)00[10, -, -, -]Inserted 10 at index 0
enqueue(20)01[10, 20, -, -]Inserted 20 at index 1
enqueue(30)02[10, 20, 30, -]Inserted 30 at index 2
dequeue()12[-, 20, 30, -]Removed 10 from index 0
dequeue()22[-, -, 30, -]Removed 20 from index 1
enqueue(40)23[-, -, 30, 40]Inserted 40 at index 3
enqueue(50)23[-, -, 30, 40]Queue Overflow! (rear == 3 == MAX - 1)
enqueue(60)23[-, -, 30, 40]Queue Overflow! (rear == 3 == MAX - 1)

Diagnosing False Overflow: When enqueue(50) is invoked, rear == 3 == MAX - 1. The linear queue algorithm halts and reports overflow even though indices 0 and 1 are completely vacant (holding 2 available slots). This demonstrates the false overflow problem inherent to static linear queues.

Answer:

The queue retains elements [30, 40] with front = 2 and rear = 3. Both enqueue(50) and enqueue(60) fail due to false overflow because rear == MAX - 1, despite the presence of 2 free positions at the head of the array.

Example 2

2

Trace the state of a circular queue of capacity using the sacrificed-cell convention (initial front = 4, rear = 4) over the sequence: enqueue(11), enqueue(22), enqueue(33), dequeue(), enqueue(44), enqueue(55), enqueue(66). Show front, rear, array contents, and wrap-around index calculations.

Applying modular arithmetic : The queue is full when .

Circular Queue Trace (MAX = 5, One Cell Sacrificed)
OperationCalculationfrontrearArray items[0..4]Condition / State
Initial—44[-, -, -, -, -]Empty (front == rear)
enqueue(11)rear = (4+1)%5 = 040[11, -, -, -, -]Enqueued 11 at index 0
enqueue(22)rear = (0+1)%5 = 141[11, 22, -, -, -]Enqueued 22 at index 1
enqueue(33)rear = (1+1)%5 = 242[11, 22, 33, -, -]Enqueued 33 at index 2
dequeue()front = (4+1)%5 = 002[-, 22, 33, -, -]Dequeued 11 from index 0
enqueue(44)rear = (2+1)%5 = 303[-, 22, 33, 44, -]Enqueued 44 at index 3
enqueue(55)rear = (3+1)%5 = 404[-, 22, 33, 44, 55]Enqueued 55 at index 4
enqueue(66)(4+1)%5 == 0 == front04[-, 22, 33, 44, 55]Queue Full! Call rejected

Evaluating Capacity Utilization: The array contains 4 active items (22, 33, 44, 55). Because slot 0 is the designated sacrificed slot (matching front = 0), . The queue correctly prevents overriding unread items without suffering false overflow.

Answer:

At completion, the circular queue contains 4 elements ([22, 33, 44, 55]) with front = 0 and rear = 4. The call enqueue(66) correctly detects Queue Full since .

Example 3

3

Illustrate the operation of an input-restricted deque versus an output-restricted deque by considering a sequence of numbers . Can the permutation be obtained from an input-restricted deque?

Analyzing Input-Restricted Deque Rules: In an input-restricted deque:

  • Insertions are allowed only at one end (say, Rear).
  • Deletions are allowed at both ends (Front and Rear).

Tracing Permutation Generation:

  1. insertRear(1) Deque: [1]
  2. insertRear(2) Deque: [1, 2]
  3. insertRear(3) Deque: [1, 2, 3] (Front is 1, Rear is 3)
  4. To output 3 first: call deleteRear() outputs 3, Deque remains [1, 2]
  5. To output 1 next: call deleteFront() outputs 1, Deque remains [2]
  6. To output 2 last: call deleteFront() (or deleteRear()) outputs 2, Deque empty.
Answer:

Yes, the permutation is achievable with an input-restricted deque by inserting all items at the rear, followed by deleteRear(), deleteFront(), and deleteFront().

Example 4

4

Consider a descending priority queue (where a higher numeric key represents higher priority) implemented using a sorted array. Given jobs arriving in order: , , , . Trace the queue after each insertion and list the exact sequence in which jobs are dequeued.

Step-by-step sorted insertions (highest priority at front/end): Maintaining descending order from front to rear:

Priority Queue Insertion Trace
Arrival StepJob InsertedStored Priority Order (Front -> Rear)Action Taken
1Inserted into empty queue
2, placed before
3, placed at the rear
4 inserted between and

Sequential Deletion based on Priority: Repeatedly removing the highest priority item from the front:

  1. Dequeue
  2. Dequeue
  3. Dequeue
  4. Dequeue
Answer:

Final stored queue state before deletion: . The sequence of serviced jobs is .


Exercises

Exercise Questions: Queues

Question 1

Define the Queue Abstract Data Type. Explain the "false overflow" condition in a linear array implementation of a queue and explain how circular queues resolve it. [2079 Ashwin]

Queue ADT Definition: A Queue ADT is a linear collection of elements accessed in strict First-In, First-Out (FIFO) sequence. It supports two primary operations: enqueue(x) which appends an element at the rear end, and dequeue() which removes and returns an element from the front end, both operating with time complexity.

The False Overflow Problem: In a static array implementation of capacity MAX, items are inserted at incrementing rear indices and deleted at incrementing front indices. When rear reaches MAX - 1, the queue signals an overflow error on the next enqueue(). However, if multiple elements were previously dequeued, the indices are vacant. Thus, the queue erroneously reports it is full despite having available physical memory. This is called false overflow (or boundary overflow).

Resolution via Circular Queue: A circular queue treats the array as a ring by taking array indices modulo MAX:

When rear reaches MAX - 1, the next insertion wraps around to index 0 if front > 0. This fully utilizes vacated memory cells without requiring costly array shifting.

Answer:

A Queue ADT is a FIFO linear structure. False overflow occurs in linear array queues when rear reaches the upper array boundary (MAX - 1) even though earlier slots have been freed by deletions. Circular queues eliminate this by wrapping indices back to index 0 using modular arithmetic .

Question 2

Write complete C algorithms/functions for enqueue and dequeue operations in a circular queue where one memory cell is sacrificed to differentiate full and empty states.

Full and Empty Conditions with One Cell Sacrificed: Given array capacity MAX:

  • Empty: front == rear
  • Full: (rear + 1) % MAX == front
  • Enqueue advances rear = (rear + 1) % MAX
  • Dequeue advances front = (front + 1) % MAX

C Implementation:

Circular Queue Operations in CC
#define MAX 10

typedef struct {
    int items[MAX];
    int front;
    int rear;
} CircularQueue;

void enqueue(CircularQueue *q, int x) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Error: Circular Queue Overflow!\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = x;
}

int dequeue(CircularQueue *q) {
    if (q->front == q->rear) {
        printf("Error: Circular Queue Underflow!\n");
        return -1;
    }
    q->front = (q->front + 1) % MAX;
    return q->items[q->front];
}
Answer:

In the sacrificed cell circular queue model, enqueue checks (rear + 1) % MAX == front before advancing rear = (rear + 1) % MAX and inserting the item. dequeue checks front == rear before advancing front = (front + 1) % MAX and returning the item.

Question 3

A circular queue of capacity (indices ) uses the sacrificed-cell approach with initial front = 5 and rear = 5. Trace front, rear, and the number of stored items after the following sequential operations:

  1. Insert 15, 25, 35
  2. Delete two elements
  3. Insert 45, 55, 65, 75

State whether the final insertion succeeds or causes overflow.

Tracing Phase 1: Insert 15, 25, 35

  • Initial: front = 5, rear = 5 (0 items)
  • Insert 15: rear = (5+1)%6 = 0, items[0] = 15
  • Insert 25: rear = (0+1)%6 = 1, items[1] = 25
  • Insert 35: rear = (1+1)%6 = 2, items[2] = 35

State: front = 5, rear = 2. Stored items: 3.

Tracing Phase 2: Delete two elements

  • First delete: front = (5+1)%6 = 0, returns 15
  • Second delete: front = (0+1)%6 = 1, returns 25

State: front = 1, rear = 2. Stored items: 1 (item 35 at index 2).

Tracing Phase 3: Insert 45, 55, 65, 75

  • Insert 45: rear = (2+1)%6 = 3, items[3] = 45
  • Insert 55: rear = (3+1)%6 = 4, items[4] = 55
  • Insert 65: rear = (4+1)%6 = 5, items[5] = 65
  • Attempt Insert 75: Next rear would be . Check full condition: (rear + 1) % 6 == 0. Since front == 1 != 0, item 75 is successfully inserted: rear = (5+1)%6 = 0, items[0] = 75.

State: front = 1, rear = 0. Number of elements: . Capacity of queue with one cell sacrificed is . The queue is now completely FULL. A subsequent insertion would fail because .

Answer:

After all operations, front = 1, rear = 0, and the queue contains 5 elements ([35, 45, 55, 65, 75]). The final insertion of 75 succeeds, filling the queue to its maximum capacity of items.

Question 4

Differentiate between an Input-Restricted Deque and an Output-Restricted Deque. Provide diagrams and list two real-world use cases.

Definition and Comparison:

AspectInput-Restricted DequeOutput-Restricted Deque
Insertion AccessRestricted to one end (typically Rear)Permitted at both ends (Front and Rear)
Deletion AccessPermitted at both ends (Front and Rear)Restricted to one end (typically Front)
Supported OperationsinsertRear(), deleteFront(), deleteRear()insertFront(), insertRear(), deleteFront()
Use Case ScenarioUndo operations where latest inputs can be revoked from the tailMulti-source event queues processed in single FIFO order

Diagrammatic Representation:

Input-Restricted Deque:
                      +-----------------------------+
  Insert Rear  -----> |    Linear / Circular Array  |
  Delete Rear  <----- |                             | -----> Delete Front
                      +-----------------------------+

Output-Restricted Deque:
  Insert Rear  -----> +-----------------------------+ -----> Delete Front
                      |    Linear / Circular Array  |
  Insert Front -----> |                             |
                      +-----------------------------+
Answer:

An input-restricted deque allows insertion at only one end while allowing deletion at both ends. An output-restricted deque allows deletion from only one end while allowing insertion at both ends.

Question 5

In a circular queue implemented using an array of size , the current indices are front = 2 and rear = 6.

  1. Calculate the current number of elements in the queue using modular formula.
  2. If 3 elements are dequeued and then 4 new elements are enqueued, calculate the new values of front, rear, and the new count of elements.

Formula for Element Count in Circular Queue: The number of elements in a circular queue of size is:

For front = 2, rear = 6, N = 8:

Updating Indices after Operations:

  • Dequeue 3 elements:
  • Enqueue 4 elements:
  • New element count:

Notice that , exactly verifying the count.

Answer:
  1. Initially, there are elements in the queue.
  2. After 3 deletions and 4 insertions, front = 5, rear = 2, and the queue contains elements.
Question 6

Compare the time complexities of implementing a Priority Queue using an Unordered Array, an Ordered Array, and a Binary Min-Heap for insert, deleteMin, and getMin. Explain why the heap is preferred.

Tabulating Operations and Complexities:

Priority Queue Complexity Comparison
Data Structureinsert(x)deleteMin()getMin() (Peek)
Unordered Array
Ordered (Sorted) Array
Binary Min-Heap

Why Binary Heap is Preferred:

  • In an unordered array, insertion is fast () but finding and removing the minimum requires scanning the entire array ().
  • In a sorted array, retrieval is instantaneous () but insertion requires element shifts to maintain order.
  • A Binary Heap provides a balanced compromise: both insertion and deletion take time in the worst case, and finding the minimum takes . For dynamic workloads with repeated mixed insertions and extractions (such as in Dijkstra's algorithm), heap performance substantially outperforms array implementations.
Answer:

An unordered array has insert and deleteMin; an ordered array has insert and deleteMin. A binary min-heap achieves for both insert and deleteMin with getMin, making it optimal for dynamic priority queue workloads.

Past exam questions for Data Structure and Algorithms

← RecursionLinked List →