Queues
Open in the Padhaiko app3.1 Definition of queue and its operations
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.
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:
| Operation | Formal Specification | Exceptional / Boundary State | Time Complexity |
|---|---|---|---|
enqueue(Q, item) | Appends item at the rear of queue Q | Queue Overflow if fixed storage is full | |
dequeue(Q) | Removes and returns the element at the front of Q | Queue Underflow if Q is empty | |
front(Q) / peek(Q) | Returns the value at the front without removing it | Error if Q is empty | |
rear(Q) | Returns the value at the rear without removing it | Error 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 Q | None |
Applications of Queues in Computer Systems
| Application Area | Operating Mechanism | System Examples |
|---|---|---|
| CPU Scheduling | Ready processes wait in a queue to be assigned CPU time slices | Round-Robin (RR) scheduling, Multilevel Feedback Queues |
| I/O & Print Buffering | Harmonizes speed mismatch between fast CPUs and slow peripheral devices | Printer spoolers (CUPS/Windows Spooler), disk write buffers |
| Graph Traversal | Tracks frontier vertices discovered during level-by-level exploration | Breadth-First Search (BFS), shortest path in unweighted graphs |
| Network Packet Handling | Routers buffer incoming packets in packet queues during network congestion | FIFO router queues, Fair Queueing algorithms |
| Asynchronous Messaging | Producer-consumer architectures decouple sending and receiving threads | Message 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.
- Initialization convention: Initialize
front = 0andrear = -1. - Empty state:
front > rear(orrear < front). - Full condition:
rear == MAX - 1. - Enqueue operation: Increment
rearby 1 (rear = rear + 1) and assignitems[rear] = item. - Dequeue operation: Retrieve
item = items[front]and advancefrontby 1 (front = front + 1).
#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):
- As items are inserted,
rearincreases until it reachesMAX - 1. - As items are dequeued,
frontadvances to the right, leaving vacant memory locations atitems[0],items[1], etc. - Once
rear == MAX - 1, any subsequent call toenqueue()reports Queue Overflow, even if the first several slots are completely empty. - 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:
- Characteristics: Straightforward array or linked list indexing; operations until
rearreaches array capacity. - Drawback: Memory wastage through unrecoverable dead space at the front of the array once elements are dequeued.
3.3.2 Circular Queue
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:
- Initialization: Set
front = MAX - 1andrear = MAX - 1. - Empty condition:
front == rear. - Full condition:
(rear + 1) % MAX == front. - Enqueue: Advance
rear = (rear + 1) % MAX, then writeitems[rear] = item. - Dequeue: Advance
front = (front + 1) % MAX, then readitem = items[front]. - Capacity: A circular queue of array size stores a maximum of elements.
#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];
}| Aspect | Linear Queue | Circular Queue |
|---|---|---|
| Memory Reuse | Freed slots before front cannot be reused | Freed slots are reused immediately via modular wrap-around |
| Full Detection | rear == MAX - 1 (susceptible to false overflow) | (rear + 1) % MAX == front |
| Max Capacity | Stores up to MAX items once | Stores up to MAX - 1 items indefinitely under cycling |
| Index Advancement | rear = rear + 1 | rear = (rear + 1) % MAX |
| Efficiency | Space-inefficient over extended runtime | Space-optimal; continuously operates in fixed memory |
3.3.3 Double-Ended Queue (Deque)
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.
| Operation | Behavior | Index Update (Circular Array Size MAX) |
|---|---|---|
insertRear(x) | Adds x to the back | rear = (rear + 1) % MAX; items[rear] = x; |
deleteFront() | Removes item from the front | front = (front + 1) % MAX; return items[front]; |
insertFront(x) | Adds x to the front | items[front] = x; front = (front - 1 + MAX) % MAX; |
deleteRear() | Removes item from the back | item = 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:
- Input-Restricted Deque:
- Insertion is permitted at one end only (usually the rear).
- Deletion is permitted from both ends (front and rear).
- Output-Restricted Deque:
- Deletion is permitted from one end only (usually the front).
- Insertion is permitted at both ends (front and rear).
- Applications of Deque: Work-stealing task schedulers (e.g. AWE, Go runtime), sliding window maximum algorithms, maintaining browser navigation history with forward/backward buffers, and undo/redo operation stacks with maximum memory limits.
3.3.4 Priority Queue
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
- Ascending Priority Queue: Items are removed in order of increasing priority key (the smallest numeric value has the highest priority, e.g. min-priority).
- Descending Priority Queue: Items are removed in order of decreasing priority key (the largest numeric value has the highest priority, e.g. max-priority).
| Underlying Data Structure | Insertion Complexity | Deletion / Extract-Max | Peek (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) |
- Key Applications: Dijkstra's shortest path algorithm, Prim's minimum spanning tree algorithm, Huffman data compression tree construction, and OS preemptive process scheduling.
Worked Examples
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:
| Operation | front | rear | items[0..3] | Status / Output |
|---|---|---|---|---|
| Initial | 0 | -1 | [-, -, -, -] | Queue is empty |
enqueue(10) | 0 | 0 | [10, -, -, -] | Inserted 10 at index 0 |
enqueue(20) | 0 | 1 | [10, 20, -, -] | Inserted 20 at index 1 |
enqueue(30) | 0 | 2 | [10, 20, 30, -] | Inserted 30 at index 2 |
dequeue() | 1 | 2 | [-, 20, 30, -] | Removed 10 from index 0 |
dequeue() | 2 | 2 | [-, -, 30, -] | Removed 20 from index 1 |
enqueue(40) | 2 | 3 | [-, -, 30, 40] | Inserted 40 at index 3 |
enqueue(50) | 2 | 3 | [-, -, 30, 40] | Queue Overflow! (rear == 3 == MAX - 1) |
enqueue(60) | 2 | 3 | [-, -, 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.
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.
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 .
| Operation | Calculation | front | rear | Array items[0..4] | Condition / State |
|---|---|---|---|---|---|
| Initial | — | 4 | 4 | [-, -, -, -, -] | Empty (front == rear) |
enqueue(11) | rear = (4+1)%5 = 0 | 4 | 0 | [11, -, -, -, -] | Enqueued 11 at index 0 |
enqueue(22) | rear = (0+1)%5 = 1 | 4 | 1 | [11, 22, -, -, -] | Enqueued 22 at index 1 |
enqueue(33) | rear = (1+1)%5 = 2 | 4 | 2 | [11, 22, 33, -, -] | Enqueued 33 at index 2 |
dequeue() | front = (4+1)%5 = 0 | 0 | 2 | [-, 22, 33, -, -] | Dequeued 11 from index 0 |
enqueue(44) | rear = (2+1)%5 = 3 | 0 | 3 | [-, 22, 33, 44, -] | Enqueued 44 at index 3 |
enqueue(55) | rear = (3+1)%5 = 4 | 0 | 4 | [-, 22, 33, 44, 55] | Enqueued 55 at index 4 |
enqueue(66) | (4+1)%5 == 0 == front | 0 | 4 | [-, 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.
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 .
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:
insertRear(1)Deque:[1]insertRear(2)Deque:[1, 2]insertRear(3)Deque:[1, 2, 3](Front is 1, Rear is 3)- To output 3 first: call
deleteRear()outputs3, Deque remains[1, 2] - To output 1 next: call
deleteFront()outputs1, Deque remains[2] - To output 2 last: call
deleteFront()(ordeleteRear()) outputs2, Deque empty.
Yes, the permutation is achievable with an input-restricted deque by inserting all items at the rear, followed by deleteRear(), deleteFront(), and deleteFront().
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:
| Arrival Step | Job Inserted | Stored Priority Order (Front -> Rear) | Action Taken |
|---|---|---|---|
| 1 | Inserted 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:
- Dequeue
- Dequeue
- Dequeue
- Dequeue
Final stored queue state before deletion: . The sequence of serviced jobs is .
Exercises
Exercise Questions: Queues
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.
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 .
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:
#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];
}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.
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:
- Insert 15, 25, 35
- Delete two elements
- 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. Sincefront == 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 .
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.
Differentiate between an Input-Restricted Deque and an Output-Restricted Deque. Provide diagrams and list two real-world use cases.
Definition and Comparison:
| Aspect | Input-Restricted Deque | Output-Restricted Deque |
|---|---|---|
| Insertion Access | Restricted to one end (typically Rear) | Permitted at both ends (Front and Rear) |
| Deletion Access | Permitted at both ends (Front and Rear) | Restricted to one end (typically Front) |
| Supported Operations | insertRear(), deleteFront(), deleteRear() | insertFront(), insertRear(), deleteFront() |
| Use Case Scenario | Undo operations where latest inputs can be revoked from the tail | Multi-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 -----> | |
+-----------------------------+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.
In a circular queue implemented using an array of size , the current indices are front = 2 and rear = 6.
- Calculate the current number of elements in the queue using modular formula.
- 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.
- Initially, there are elements in the queue.
- After 3 deletions and 4 insertions,
front = 5,rear = 2, and the queue contains elements.
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:
| Data Structure | insert(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.
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.