Module 16: Queue

Learning Objectives

By the end of this module, you will be able to:

• Understand the Queue data structure and the FIFO principle.
• Learn queue operations such as Enqueue, Dequeue, Front, and Rear.
• Implement queues using arrays and linked lists.
• Understand Circular Queue, Priority Queue, and Deque.
• Analyze the time complexity of queue operations.
• Build real-world applications such as printer queues and CPU scheduling.

Introduction

A Queue is one of the most important linear data structures in Computer Science.

Unlike a Stack, which follows LIFO (Last In, First Out), a Queue follows the FIFO (First In, First Out) principle.

This means the first element inserted into the queue is the first element removed.

Queues are widely used in:

• CPU Scheduling
• Printer Management
• Network Packet Routing
• Call Centers
• Ticket Booking Systems
• Breadth First Search (BFS)
• Message Queues
• Operating Systems

What is a Queue?

A Queue is a linear data structure where:

• Insertion happens at the Rear
• Deletion happens at the Front

Visualization

genui{"computing_fundamentals_algorithms_learning_block":{"type_id":"ARRAY_QUEUE_FRONT_REAR"}}

Example

textCopy
1Front                          Rear
2  │                              │
3  ▼                              ▼
4+----+----+----+----+----+
5| 10 | 20 | 30 | 40 | 50 |
6+----+----+----+----+----+

If we insert 60, it is added at the Rear.

If we delete an element, 10 is removed from the Front.

Queue Operations

Queue Using Array

The simplest queue implementation uses an array and two variables:

• front
• rear

Initially

textCopy
1front = -1
2rear = -1

Queue Implementation Using Array

cCopy
1#include <stdio.h>
2
3#define SIZE 5
4
5int queue[SIZE];
6int front = -1;
7int rear = -1;
8
9void enqueue(int value)
10{
11    if(rear == SIZE - 1)
12    {
13        printf("Queue Overflow\n");
14        return;
15    }
16
17    if(front == -1)
18        front = 0;
19
20    queue[++rear] = value;
21}
22
23int dequeue()
24{
25    if(front == -1 || front > rear)
26    {
27        printf("Queue Underflow\n");
28        return -1;
29    }
30
31    return queue[front++];
32}
33
34void display()
35{
36    if(front == -1 || front > rear)
37    {
38        printf("Queue Empty\n");
39        return;
40    }
41
42    for(int i = front; i <= rear; i++)
43    {
44        printf("%d ", queue[i]);
45    }
46
47    printf("\n");
48}
49
50int main()
51{
52    enqueue(10);
53    enqueue(20);
54    enqueue(30);
55
56    display();
57
58    printf("Removed = %d\n", dequeue());
59
60    display();
61
62    return 0;
63}

Output

textCopy
110 20 30
2
3Removed = 10
4
520 30

Time Complexity

Queue Overflow

Overflow occurs when we try to insert into a full queue.

Example

textCopy
1Queue Size = 5
2
310
420
530
640
750
8
9Enqueue 60
10
11↓
12
13Queue Overflow

Queue Underflow

Underflow occurs when we remove an element from an empty queue.

Example

textCopy
1Queue Empty
2
3Dequeue()
4
5↓
6
7Queue Underflow

Limitation of Linear Queue

Consider the following:

textCopy
1Initial Queue
2
310 20 30 40 50
4
5Front = 0
6
7Rear = 4

Remove three elements

textCopy
1_ _ _ 40 50
2
3Front = 3
4
5Rear = 4

Although there is free space at the beginning, the queue is considered full because rear has reached the last index.

This problem is solved using a Circular Queue.

Circular Queue

A Circular Queue connects the last position back to the first position, allowing efficient reuse of empty spaces.

Example

textCopy
1      +-----------+
2      |           |
3Front ↓           ↑ Rear
4+----+----+----+----+----+
5| 10 | 20 |    |    | 50 |
6+----+----+----+----+----+

When rear reaches the last index, it wraps around to the beginning if space is available.

Formula

textCopy
1rear = (rear + 1) % SIZE
2front = (front + 1) % SIZE

Advantages

• Efficient memory usage
• Eliminates wasted space
• Ideal for buffers and scheduling

Time Complexity

textCopy
1Enqueue : O(1)
2
3Dequeue : O(1)

Queue Using Linked List

Using a linked list removes the fixed-size limitation.

Node Structure

cCopy
1struct Node
2{
3    int data;
4    struct Node *next;
5};

Maintain two pointers:

• Front
• Rear

Enqueue

cCopy
1void enqueue(int value)
2{
3    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
4
5    newNode->data = value;
6    newNode->next = NULL;
7
8    if(rear == NULL)
9    {
10        front = rear = newNode;
11        return;
12    }
13
14    rear->next = newNode;
15    rear = newNode;
16}

Dequeue

cCopy
1void dequeue()
2{
3    if(front == NULL)
4        return;
5
6    struct Node *temp = front;
7
8    front = front->next;
9
10    free(temp);
11
12    if(front == NULL)
13        rear = NULL;
14}

Advantages

• Dynamic size
• No overflow unless memory is exhausted

Priority Queue

A Priority Queue removes elements based on priority rather than insertion order.

Example

textCopy
1Priority
2
31 = Highest
4
55 = Lowest

Queue

textCopy
1Task A (3)
2
3Task B (1)
4
5Task C (2)

Removal Order

textCopy
1Task B
2
3Task C
4
5Task A

Applications

• CPU Scheduling
• Dijkstra's Algorithm
• Operating Systems
• Network Routing
• Hospital Emergency Systems

Deque (Double Ended Queue)

A Deque allows insertion and deletion from both ends.

Operations

• Insert Front
• Insert Rear
• Delete Front
• Delete Rear

Example

textCopy
1Front                 Rear
2
310 20 30 40

Insert at Front

textCopy
15 10 20 30 40

Insert at Rear

textCopy
15 10 20 30 40 50

Applications

• Sliding Window Problems
• Browser History
• Undo/Redo
• Job Scheduling

Types of Deque

Input Restricted Deque

• Insertion from one side only
• Deletion from both sides

Output Restricted Deque

• Deletion from one side only
• Insertion from both sides

Queue vs Stack

Real-World Applications

Printer Queue

Printers process print jobs in the order they are received.

Example

textCopy
1Document A
2
3↓
4
5Document B
6
7↓
8
9Document C

Printing Order

textCopy
1A
2
3↓
4
5B
6
7↓
8
9C

Each new document is Enqueued.

The printer Dequeues one document at a time.

CPU Scheduling

Operating systems use queues to manage processes waiting for CPU time.

Example

textCopy
1Process P1
2
3↓
4
5Process P2
6
7↓
8
9Process P3

CPU Execution

textCopy
1P1
2
3↓
4
5P2
6
7↓
8
9P3

Different scheduling algorithms may use:

• Simple Queue
• Priority Queue
• Circular Queue

Practice Project 1: Printer Queue

Design a queue that stores print jobs.

Features

• Add a document
• Print the next document
• Display pending documents
• Check whether the queue is empty

Practice Project 2: CPU Scheduling Simulator

Create a simple scheduler using a queue.

Features

• Add a process
• Execute the next process
• Display waiting processes
• Remove completed processes

Common Interview Questions

1. Implement Queue using Array.
2. Implement Queue using Linked List.
3. Implement Circular Queue.
4. Implement Deque.
5. Reverse a Queue.
6. Generate Binary Numbers using Queue.
7. Implement Queue using Two Stacks.
8. Implement Stack using Two Queues.
9. Design a Priority Queue.
10. First Non-Repeating Character in a Stream.

Common Mistakes to Avoid

• Confusing FIFO with LIFO.
• Forgetting to update front and rear correctly after enqueue or dequeue operations.
• Not checking for queue overflow or underflow.
• Failing to reset front and rear when the queue becomes empty.
• Mismanaging wrap-around logic in a circular queue.
• Forgetting to free dynamically allocated memory in linked-list implementations.

Best Practices

• Choose an array implementation when the maximum queue size is known.
• Use a linked-list implementation when the queue size is dynamic.
• Prefer a circular queue over a linear queue to avoid wasted space.
• Use priority queues when tasks must be processed based on importance rather than arrival time.
• Implement queue operations (enqueue, dequeue, front, rear, isEmpty) as separate reusable functions.
• Analyze the time and space complexity of each queue implementation before selecting it for a problem.

Module Summary

In this module, you learned:

• What a Queue is and how it follows the FIFO (First In, First Out) principle.
• How to implement queues using arrays and linked lists.
• The core queue operations: Enqueue, Dequeue, Front, Rear, and Display.
• The limitations of a linear queue and how a Circular Queue solves them.
• How Priority Queues process elements based on priority.
• How a Deque (Double Ended Queue) supports insertion and deletion from both ends.
• Real-world applications such as printer management and CPU scheduling.

After completing this module, you'll be ready to learn Trees, where you'll explore binary trees, binary search trees (BST), tree traversals, heap structures, AVL trees, and tree-based searching and optimization algorithms.