UNIT IV

Queues: Introduction to queues: properties and operations, implementing queues using arrays and linked
lists, Applications of queues in breadth-first search, scheduling, etc.
Deques: Introduction to deques (double-ended queues), Operations on deques and their applications.

In data structures, a queue is a linear data structure that follows the First-In-First-Out (FIFO) principle,
meaning that the element added first is the one to be removed first. This structure is similar to a real-world
queue, like a line at a ticket counter.
Properties of a Queue
1. Linear Structure: A queue is a sequential collection of elements, where elements are arranged in a
linear order.
2. FIFO Principle: The first element added to the queue will be the first one to be removed.

3. Two Pointers: Queues typically maintain two pointers:

o Front: Points to the first element of the queue (the element to be removed).
o Rear: Points to the last element of the queue (where new elements are added).
4. Dynamic Size: A queue can be dynamically resized (in case of dynamic data structures like linked
lists) or have a fixed size (in case of array-based queues).
5. Homogeneous Elements: All elements in a queue are of the same data type.

Operations on a Queue
1. Enqueue Operation
 The enqueue operation adds a new element to the rear of the queue. In a queue, elements are always
added at the rear to maintain the FIFO (First-In-First-Out) order.
 This operation helps to insert elements into the queue, and they will be processed in the order they
were added.
 How It Works:
1. Before adding an element, the queue is checked if it is full (in case of a fixed-size queue).
2. If the queue is not full, the element is appended at the end (rear).

1
 3. If the queue is full, an error message is returned, indicating that no more elements can be
added.
 Time Complexity: O(1) (constant time), as adding an element to the rear is done in constant time in
dynamic data structures like a list.

2. Dequeue Operation
 The dequeue operation removes an element from the front of the queue. In a queue, elements are
always removed from the front, following the FIFO principle.
 This operation serves to retrieve and remove elements from the queue in the order they were added.
 How It Works:
1. Before removing an element, the queue is checked if it is empty.
2. If the queue is not empty, the element at the front of the queue is removed and returned.
3. If the queue is empty, an error message is returned, indicating that there are no elements to
remove.
 Time Complexity: O(1) for removing from the front in a linked-list implementation, but O(n) in
Python’s list, because removing the first element requires shifting all other elements by one position.
2
3. Peek Operation (Front)
 The peek operation allows you to view the element at the front of the queue without removing it.
 It’s useful when you need to know which element is next to be processed without actually dequeuing
it.
 How It Works:
1. Before retrieving the element, the queue is checked if it is empty.
2. If the queue is not empty, the element at the front is returned.
3. If the queue is empty, a message is returned, indicating that there is no front element to show.
 Time Complexity: O(1), as simply viewing the first element doesn’t involve any shifting or
movement of data.
4. Display Operation
 The display operation prints all the elements present in the queue in the order they were enqueued.
 This operation is useful for visualizing the current state of the queue.
 How It Works:
1. The queue is checked if it is empty.

3
 2. If the queue is not empty, all elements from front to rear are printed in sequence.
3. If the queue is empty, a message is returned, indicating that the queue is empty.
 Time Complexity: O(n), where n is the number of elements in the queue, as each element must be
printed.
5. isEmpty Operation
 The isEmpty operation checks whether the queue contains any elements.
 This operation is critical before performing operations like dequeue or peek to avoid errors.
 How It Works:
1. It simply checks if the length of the queue is zero.
2. If it is, the queue is considered empty and returns True, otherwise, it returns False.
 Time Complexity: O(1), as it only checks the length of the queue, which is a constant-time
operation.
6. isFull Operation
 The isFull operation checks whether the queue has reached its maximum capacity (for fixed-size
queues).
 This operation is essential before performing enqueue in a fixed-size queue to ensure no overflow
occurs.
 How It Works:
1. It checks if the current size of the queue is equal to its maximum allowed size.
2. If the size is equal, it returns True (queue is full), otherwise False.
 Time Complexity: O(1), as it only checks the current length of the queue, which is constant.

Pseudo Code for Queue Operations

1. Queue Operations Using Arrays

Initialize queue with MAX_SIZE

front = -1, rear = -1 // Indicating empty queue

Enqueue(queue, value):
If rear == MAX_SIZE - 1:
Print "Queue Overflow"
Return
If front == -1:
front = 0 // Set front on first insertion
rear = rear + 1

4
 queue[rear] = value

Dequeue(queue):
If front == -1 OR front > rear:
Print "Queue Underflow"
Return
value = queue[front]
front = front + 1
Return value

Peek(queue):
If front == -1 OR front > rear:
Print "Queue is Empty"
Return
Return queue[front]

IsEmpty(queue):
If front == -1 OR front > rear:
Return True
Else:
Return False

2. Queue Operations Using Linked List

Define Node:
data
next

Initialize queue with front = NULL, rear = NULL

Enqueue(value):
Create newNode
[Link] = value
[Link] = NULL
If rear == NULL:

5
 front = rear = newNode
Else:
[Link] = newNode
rear = newNode

Dequeue():
If front == NULL:
Print "Queue Underflow"
Return
value = [Link]
front = [Link]
If front == NULL:
rear = NULL // Reset rear when queue becomes empty
Return value

Peek():
If front == NULL:
Print "Queue is Empty"
Return
Return [Link]

IsEmpty():
If front == NULL:
Return True
Else:
Return False

Types of Queues:
There are several types of queues, each suited for different purposes depending on the order in which
elements are processed or how elements are accessed. Here are the main types:
1. Simple Queue (Linear Queue):

6
  Description: This is the basic form of a queue where elements are added at the rear (enqueue) and
removed from the front (dequeue).
 Order: First-In-First-Out (FIFO).
 Example: A printer queue where documents are printed in the order they were received.
2. Circular Queue:

 Description: A circular queue is a more efficient version of a simple queue. It uses a circular
structure to prevent the issue of "wasted space" at the front of the queue after elements are dequeued.
 Order: First-In-First-Out (FIFO).
 Example: Buffers in networking devices or memory buffers in real-time systems.
3. Priority Queue:

 Description: In a priority queue, each element is assigned a priority. Elements with higher priority
are dequeued before those with lower priority, regardless of the order they were added.
 Order: Not strictly FIFO; depends on the priority of elements.
 Example: CPU scheduling in operating systems, or medical emergency response systems (where
patients with critical conditions are treated first).
4. Double-Ended Queue (Deque):

 Description: A deque allows insertion and deletion of elements from both ends of the queue — from
the front (enqueue/dequeue) and from the rear (push/pop).
 Order: Can operate as both FIFO and LIFO, depending on the operations performed.

7
  Example: Palindrome checking, or applications that need both ends of the queue for efficient
processing.

Implementation of Queue using arrays

Program:
#include <stdio.h>
#define MAX 5 // Maximum size of the queue
int queue[MAX]; // Array to store queue elements
int front = -1, rear = -1; // Front and rear of the queue

// Check if the queue is empty

int isEmpty()
{
return front == -1;
}

// Check if the queue is full

int isFull()
{
return rear == MAX - 1;
}

// Add an element to the queue (enqueue)

void enqueue(int item)
{
if (isFull())
{
printf("Queue is full. Cannot enqueue %d.\n", item);
}
else
{
if (front == -1) front = 0; // Set front when first element is added
queue[++rear] = item; // Increment rear and add the item
printf("Enqueued: %d\n", item);
}
}

// Remove an element from the queue (dequeue)

void dequeue()
{
if (isEmpty())
{
printf("Queue is empty. Cannot dequeue.\n");
}
else
{
printf("Dequeued: %d\n", queue[front]);
if (front == rear) // If the queue becomes empty after dequeue
front = rear = -1;
else
8
 front++; // Increment front
}
}

// Get the front element of the queue (peek)

void peek()
{
if (isEmpty())
printf("Queue is empty.\n");
else
printf("Front item: %d\n", queue[front]);
}

// Display all elements of the queue

void display()
{
if (isEmpty())
{
printf("Queue is empty.\n");
}
else
{
printf("Queue contents: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
}

// Main function to demonstrate queue operations

int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue is full
display(); // Display queue contents
dequeue();
dequeue();
display(); // Display remaining queue contents
enqueue(60); // Enqueue after dequeue
display(); // Display queue after enqueue
peek(); // Peek at the front element
return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40

9
Enqueued: 50
Queue contents: 10 20 30 40 50
Dequeued: 10
Dequeued: 20
Queue contents: 30 40 50
Queue is full. Cannot enqueue 60.
Queue contents: 30 40 50
Front item: 30
Implementation of Queues using Linked List
Program:
#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node
{
int data;
struct Node* next;
};

// Queue front and rear pointers

struct Node* front = NULL;
struct Node* rear = NULL;

// Check if the queue is empty

int isEmpty()
{
return front == NULL;
}

// Enqueue operation (insert at rear)

void enqueue(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed. Queue is full!\n");
return;
}
newNode->data = value;
newNode->next = NULL;

if (isEmpty())
{
front = rear = newNode;
}
else
{
rear->next = newNode;
rear = newNode;
}

10
 printf("Enqueued: %d\n", value);
}

// Dequeue operation (remove from front)

void dequeue()
{
if (isEmpty())
{
printf("Queue is empty. Cannot dequeue.\n");
return;
}
struct Node* temp = front;
printf("Dequeued: %d\n", temp->data);
front = front->next;
free(temp);

if (front == NULL)
{ // If queue becomes empty, reset rear
rear = NULL;
}
}

// Peek operation (get front element)

void peek()
{
if (isEmpty())
{
printf("Queue is empty.\n");
}
else
{
printf("Front element: %d\n", front->data);
}
}

// Display operation (print queue elements)

void display()
{
if (isEmpty())
{
printf("Queue is empty.\n");
return;
}
struct Node* temp = front;
printf("Queue: ");
while (temp)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

11
// Main function
int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
display(); // Output: Queue: 10 20 30
peek(); // Output: Front element: 10
dequeue();
dequeue();
display(); // Output: Queue: 30
return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue: 10 20 30
Front element: 10
Dequeued: 10
Dequeued: 20
Queue: 30
C Program to implement Circular Queue
Program:
#include <stdio.h>
#define MAX 5 // Maximum size of the queue
int queue[MAX]; // Array to store queue elements
int front = -1, rear = -1; // Front and rear of the queue

// Check if the queue is empty

int isEmpty() {
return front == -1;
}

// Check if the queue is full

int isFull() {
return (rear + 1) % MAX == front;
}

// Add an element to the queue (enqueue)

void enqueue(int item) {
if (isFull()) {
printf("Queue is full. Cannot enqueue %d.\n", item);
} else {
if (front == -1) front = 0; // Set front when first element is added
rear = (rear + 1) % MAX; // Circular increment of rear
queue[rear] = item; // Add the item at the new rear position
printf("\nEnqueued: %d", item);
}
}

12
// Remove an element from the queue (dequeue)
void dequeue() {
if (isEmpty()) {
printf("Queue is empty. Cannot dequeue.\n");
} else {
printf("\n Dequeued: %d", queue[front]);
if (front == rear) { // If the queue becomes empty after dequeue
front = rear = -1;
} else {
front = (front + 1) % MAX; // Circular increment of front
}
}
}

// Get the front element of the queue (peek)

void peek() {
if (isEmpty()) {
printf("Queue is empty.\n");
} else {
printf("\n Front item: %d", queue[front]);
}
}

// Display all elements of the queue using a for loop

void display() {
if (isEmpty()) {
printf("Queue is empty.\n");
} else {
printf("\n Queue contents:");
int i;
// Using a for loop to handle circular queue traversal
for (i = front; i != rear; i = (i + 1) % MAX) {
printf("%d ", queue[i]);
}
//printf("%d\n", queue[rear]); // Print the last element (rear)
}
}

// Main function to demonstrate queue operations

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue is full
display(); // Display queue contents

dequeue();
dequeue();
display(); // Display remaining queue contents

13
 enqueue(60); // Enqueue after dequeue
display(); // Display queue after enqueue

peek(); // Peek at the front element

enqueue(70); // Enqueue another element

display(); // Display queue after another enqueue

return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Enqueued: 50
10 20 30 40 50
Output:Dequeued: 10
Dequeued: 20
30 40 50
Enqueued: 60
30 40 50 60
Front item: 30
Enqueued: 70
30 40 50 60 70

C Program to implement a Simple Printer Queue System using Queue (First Come First Serve Job
Scheduling)
Program:
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#define MAX 20

int jobId[MAX];
char jobName[MAX][50];
int front = -1, rear = -1;

int isFull()
{
return rear == MAX - 1;
}

int isEmpty()
{
return front == -1;
}

void enqueue(int id, char name[])

{
if (isFull())
14
 {
printf("Queue is full! Cannot add job: %s\n", name);
return;
}
if (isEmpty())
{
front = 0;
}
rear++;
jobId[rear] = id;
strcpy(jobName[rear], name);
printf("Enqueued: %d - %s\n", id, name);
}

void dequeue()
{
if (isEmpty())
{
printf("Queue is empty! Nothing to process.\n");
return;
}
printf("Processing: %d - %s\n", jobId[front], jobName[front]);
if (front == rear)
{
front = rear = -1;
}
else
{
front++;
}
}
void displayQueue()
{
if (isEmpty())
{
printf("Queue is empty.\n");
return;
}
printf("Current Printer Queue:\n");
for (int i = front; i <= rear; i++)
{
printf("Job %d: %s\n", jobId[i], jobName[i]);
}
}
int main()
{
enqueue(1, "[Link]");
enqueue(2, "[Link]");
enqueue(3, "[Link]");
enqueue(4, "[Link]");
enqueue(5, "[Link]");
displayQueue();

15
 dequeue();
dequeue();
enqueue(6, "[Link]"); // Will show "Queue is full"
displayQueue();
return 0;
}
Output:
Enqueued: 1 - [Link]
Enqueued: 2 - [Link]
Enqueued: 3 - [Link]
Enqueued: 4 - [Link]
Enqueued: 5 - [Link]
Current Printer Queue:
Job 1: [Link]
Job 2: [Link]
Job 3: [Link]
Job 4: [Link]
Job 5: [Link]
Processing: 1 - [Link]
Processing: 2 - [Link]
Enqueued: 6 - [Link]
Current Printer Queue:
Job 3: [Link]
Job 4: [Link]
Job 5: [Link]
Job 6: [Link]
C Program to perform comparison and check for symmetry using Stack
Program:
#include <stdio.h>
#include <stdbool.h>

#define MAX 100 // Maximum stack size

// Stack
int stack[MAX];
int top = -1;

// Push function
void push(int value)
{
if (top == MAX - 1)
{
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}

// Pop function
int pop() {
if (top == -1)

16
 {
return -1; // Return an invalid value for error
}
return stack[top--];
}

// Function to check symmetry

bool isSymmetric(int arr[], int size)
{
int mid = size / 2;

// Push first half onto stack

for (int i = 0; i < mid; i++)
{
push(arr[i]);
}

// If odd size, skip the middle element

int start = (size % 2 == 0) ? mid : mid + 1;

// Compare second half with stack

for (int i = start; i < size; i++)
{
if (arr[i] != pop())
{
return false;
}
}

return true;
}

int main()
{
int arr[MAX], size;

// Get array size from the user

printf("Enter the number of elements: ");
scanf("%d", &size);

// Get array elements from the user

printf("Enter %d elements:\n", size);
for (int i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}

// Check for symmetry

if (isSymmetric(arr, size))
printf("The array is symmetric.\n");
else
printf("The array is not symmetric.\n");

17
 return 0;
}
Output 1:
Enter the number of elements: 6
Enter 6 elements:
1
2
3
4
5
6
The array is not symmetric.

Output 2:
Enter the number of elements: 6
Enter 6 elements:
1
2
3
3
2
1
The array is symmetric.

C Program to perform comparison and check for symmetry using queue

Program:
#include <stdio.h>
#include <stdbool.h>

#define MAX 100

int deque[MAX];
int front = -1, rear = -1;

bool isEmpty()
{
return front == -1;
}

void insertRear(int value)

{
if (isEmpty())
{
front = rear = 0;
}
else
{
rear++;
}
deque[rear] = value;
18
}

int deleteRear()
{
int val = deque[rear];
if (front == rear)
{
front = rear = -1;
} else {
rear--;
}
return val;
}

bool isSymmetric(int arr[], int size)

{
front = rear = -1; // reset deque
int mid = size / 2;

for (int i = 0; i < mid; i++)

{
insertRear(arr[i]);
}

int start = (size % 2 == 0) ? mid : mid + 1;

for (int i = start; i < size; i++)

{
if (arr[i] != deleteRear())
{
return false;
}
}
return true;
}

int main()
{
int arr[MAX], size;

printf("Enter the number of elements: ");

scanf("%d", &size);

printf("Enter the %d elements:\n", size);

for (int i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}

if (isSymmetric(arr, size))
printf("The array is symmetric.\n");
else

19
 printf("The array is not symmetric.\n");

return 0;
}

Output 1:
Enter the number of elements: 5
Enter the 5 elements:
1
2
3
4
5
The array is not symmetric.

Output 2:
Enter the number of elements: 6
Enter the 6 elements:
1
2
3
3
2
1
The array is symmetric.

C Program to implement simple printer queue system using Circular Queues

Program:
#include <stdio.h>
#include <string.h>

#define MAX 5 // Max size of the circular queue

int jobId[MAX];
char jobName[MAX][50];
int front = -1, rear = -1;

// Function to check if the queue is full

int isFull()
{
return (front == (rear + 1) % MAX);
}

// Function to check if the queue is empty

int isEmpty()
{
return front == -1;
}

// Function to add a job to the queue

void enqueue(int id, char name[])
20
{
if (isFull())
{
printf("Queue is full! Cannot add job: %s\n", name);
return;
}
if (isEmpty())
{
front = rear = 0;
}
else
{
rear = (rear + 1) % MAX;
}
jobId[rear] = id;
strcpy(jobName[rear], name);
printf("Enqueued: %d - %s\n", id, name);
}

// Function to remove a job from the queue

void dequeue()
{
if (isEmpty())
{
printf("Queue is empty! Nothing to process.\n");
return;
}
printf("Processing: %d - %s\n", jobId[front], jobName[front]);
if (front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % MAX;
}
}

// Modified display function using for loop

void displayQueue()
{
if (isEmpty())
{
printf("Queue is empty.\n");
return;
}

printf("Current Printer Queue:\n");

for (int i = front; ; i = (i + 1) % MAX)

{
printf("Job %d: %s\n", jobId[i], jobName[i]);

21
 if (i == rear)
break;
}
}

// Main function to test the circular queue

int main()

{
enqueue(1, "[Link]");
enqueue(2, "[Link]");
enqueue(3, "[Link]");
enqueue(4, "[Link]");
enqueue(5, "[Link]");

dequeue(); // Remove one ([Link])

dequeue(); // Remove another ([Link])

enqueue(6, "[Link]"); // Wrap around to index 0

enqueue(7, "[Link]"); // Wrap to index 1 → Now front = 2, rear = 1

displayQueue(); // Works perfectly with modified for loop!

return 0;
}
Output:
Enqueued: 1 - [Link]
Enqueued: 2 - [Link]
Enqueued: 3 - [Link]
Enqueued: 4 - [Link]
Enqueued: 5 - [Link]
Processing: 1 - [Link]
Processing: 2 - [Link]
Enqueued: 6 - [Link]
Enqueued: 7 - [Link]
Current Printer Queue:
Job 3: [Link]
Job 4: [Link]
Job 5: [Link]
Job 6: [Link]
Job 7: [Link]

Applications of queues in breadth-first search, scheduling

Queues play a critical role in various applications, including Breadth-First Search (BFS) and Scheduling
Algorithms.
1. Applications of Queues in Breadth-First Search (BFS)

22
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph (or nodes
of a tree) level by level, ensuring the shortest path is found when applicable. The core principle of BFS relies
on FIFO (First-In-First-Out) ordering, making a queue the ideal data structure to facilitate this traversal.
How BFS Uses a Queue:
 Initialization: BFS begins by enqueuing the starting node into the queue and marking it as visited.
 Exploration: The node at the front of the queue is dequeued, and its neighbors are explored.
 Queue Update: The unvisited neighbors are enqueued and marked as visited.
 Repeat: This continues until the queue is empty, meaning all reachable nodes have been explored.
Key Points:
 Shortest Path: BFS guarantees the shortest path in unweighted graphs because it explores all nodes
at the current depth (distance) before moving on to the next depth.
 Queue’s Role: The queue ensures that nodes are processed in the order they were discovered,
respecting the level-by-level exploration.
Example Use Cases:
 Shortest Path Finding: BFS can be used to find the shortest path in an unweighted graph, such as
finding the shortest number of moves in a chess game or the shortest route in a city grid.
 Social Networks: Finding the degree of separation between users, or determining the closest friends.
 Web Crawling: Crawlers use BFS to explore websites level by level to gather information.
2. Applications of Queues in Scheduling
Queues are heavily used in Scheduling algorithms, especially in operating systems and task management
systems. Scheduling refers to determining the order in which tasks (or processes) are executed, and queues
ensure that tasks are processed in a fair and efficient manner, often using FIFO or priority-based policies.
Common Scheduling Techniques that Use Queues:
1. First-Come, First-Served (FCFS):
o Description: This is the simplest form of scheduling, where processes are scheduled in the
order they arrive. The first process to arrive is the first to be executed.
o Queue Role: A simple queue (FIFO) is used to maintain the order of processes.
o Example: A printer queue where documents are printed in the order they are received.
2. Round Robin (RR):
o Description: In Round Robin scheduling, each process is assigned a fixed time slice
(quantum). The process is executed for that time slice, and if it doesn’t finish, it is placed at
the end of the queue to wait for the next turn.
o Queue Role: A circular queue is often used to manage the processes. When a process is
executed for its time slice, it either completes or is moved to the back of the queue.
o Example: Time-sharing operating systems, where multiple users share the same CPU.
23
 3. Priority Scheduling:
o Description: In this scheme, each process is assigned a priority, and the process with the
highest priority is executed first. If two processes have the same priority, they are scheduled
in FIFO order.
o Queue Role: A priority queue (which is usually implemented as a heap) is used to store and
retrieve processes based on their priority.
o Example: Real-time systems where higher priority tasks (e.g., medical or flight control
systems) must be completed first.
4. Shortest Job Next (SJN) or Shortest Job First (SJF):
o Description: This algorithm prioritizes processes with the shortest execution time, ensuring
that they are completed before longer ones.
o Queue Role: A priority queue or a sorted queue can be used to manage processes based on
their burst time (time to complete).
o Example: Job schedulers in batch processing systems.

Job Scheduling Algorithms

 Burst Time (BT)
 Waiting Time (WT)
 Turnaround Time (TAT = BT + WT)
 Completion Time (CT = TAT)
All based on the same processes:
Process Table
Process Burst Time (BT)
P1 6
P2 8
P3 7
P4 3

1. FCFS (First Come First Serve)

🔸 Gantt Chart:
| P1 | P2 | P3 | P4 |
0 6 14 21 24
Process BT WT TAT = BT + WT CT (TAT)
P1 6 0 6 6
P2 8 6 14 14
P3 7 14 21 21
P4 3 21 24 24
24
2. SJF (Shortest Job First – Non-Preemptive)
🔸 Sorted order (BT): P4, P1, P3, P2
🔸 Gantt Chart:
| P4 | P1 | P3 | P2 |
0 3 9 16 24
Process BT WT TAT = BT + WT CT (TAT)
P4 3 0 3 3
P1 6 3 9 9
P3 7 9 16 16
P2 8 16 24 24

3. Round Robin (Time Quantum = 4)

🔸 Execution Order:
| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P2 |
0 4 8 12 15 17 21 23 24
Process BT CT TAT = CT WT = TAT - BT
P1 6 17 17 11
P2 8 24 24 16
P3 7 23 23 16
P4 3 15 15 12

[Link] Scheduling (Non-Preemptive)

🔸 Priority:
Process Priority
P4 1 (highest)
P1 2
P3 3
P2 4 (lowest)
🔸 Execution Order: P4 → P1 → P3 → P2
🔸 Gantt Chart:
| P4 | P1 | P3 | P2 |
0 3 9 16 24
Process BT WT TAT = BT + WT CT (TAT)
P4 3 0 3 3
P1 6 3 9 9
P3 7 9 16 16
P2 8 16 24 24

25
 Breadth First Search
Breadth-first search (BFS) is an algorithm that is used to graph data or searching tree or traversing
structures. The full form of BFS is the Breadth-first search.

The algorithm efficiently visits and marks all the key nodes in a graph in an accurate breadthwise fashion.
This algorithm selects a single node (initial or source point) in a graph and then visits all the nodes adjacent
to the selected node. Remember, BFS accesses these nodes one by one.

Once the algorithm visits and marks the starting node, then it moves towards the nearest unvisited nodes and
analyses them. Once visited, all nodes are marked. These iterations continue until all the nodes of the graph
have been successfully visited and marked.

What is Graph traversals?

A graph traversal is a commonly used methodology for locating the vertex position in the graph. It is an
advanced search algorithm that can analyze the graph with speed and precision along with marking the
sequence of the visited vertices. This process enables you to quickly visit each node in a graph without being
locked in an infinite loop.

The architecture of BFS algorithm

1. In the various levels of the data, you can mark any node as the starting or initial node to begin
traversing. The BFS will visit the node and mark it as visited and places it in the queue.
2. Now the BFS will visit the nearest and un-visited nodes and marks them. These values are also added
to the queue. The queue works on the FIFO model.
3. In a similar manner, the remaining nearest and un-visited nodes on the graph are analyzed marked
and added to the queue. These items are deleted from the queue as receive and printed as the result.

26
Why do we need BFS Algorithm?

There are numerous reasons to utilize the BFS Algorithm to use as searching for your dataset. Some of the
most vital aspects that make this algorithm your first choice are:

 BFS is useful for analyzing the nodes in a graph and constructing the shortest path of traversing
through these.
 BFS can traverse through a graph in the smallest number of iterations.
 The architecture of the BFS algorithm is simple and robust.
 The result of the BFS algorithm holds a high level of accuracy in comparison to other algorithms.
 BFS iterations are seamless, and there is no possibility of this algorithm getting caught up in an
infinite loop problem.

How does BFS Algorithm Work?

Graph traversal requires the algorithm to visit, check, and/or update every single un-visited node in a tree-
like structure. Graph traversals are categorized by the order in which they visit the nodes on the graph.

BFS algorithm starts the operation from the first or starting node in a graph and traverses it thoroughly. Once
it successfully traverses the initial node, then the next non-traversed vertex in the graph is visited and
marked.

Hence, you can say that all the nodes adjacent to the current vertex are visited and traversed in the first
iteration. A simple queue methodology is utilized to implement the working of a BFS algorithm, and it
consists of the following steps:

Step 1)

Each vertex or node in the graph is known. For instance, you can mark the node as V.

Step 2)

27
In case the vertex V is not accessed then add the vertex V into the BFS Queue

Step 3)

Start the BFS search, and after completion, Mark vertex V as visited.

Step 4)

The BFS queue is still not empty, hence remove the vertex V of the graph from the queue.

Step 5)

Retrieve all the remaining vertices on the graph that are adjacent to the vertex V

Step 6)

28
For each adjacent vertex let’s say V1, in case it is not visited yet then add V1 to the BFS queue

Step 7)

BFS will visit V1 and mark it as visited and delete it from the queue.

Example BFS Algorithm

Step 1)

You have a graph of seven numbers ranging from 0 – 6.

Step 2)

29
0 or zero has been marked as a root node.

Step 3)

0 is visited, marked, and inserted into the queue data structure.

Step 4)

Remaining 0 adjacent and unvisited nodes are visited, marked, and inserted into the queue.

Step 5)

30
Traversing iterations are repeated until all nodes are visited.

Rules of BFS Algorithm

Here, are important rules for using BFS algorithm:

 A queue (FIFO-First in First Out) data structure is used by BFS.

 You mark any node in the graph as root and start traversing the data from it.
 BFS traverses all the nodes in the graph and keeps dropping them as completed.
 BFS visits an adjacent unvisited node, marks it as done, and inserts it into a queue.
 Removes the previous vertex from the queue in case no adjacent vertex is found.
 BFS algorithm iterates until all the vertices in the graph are successfully traversed and marked as
completed.
 There are no loops caused by BFS during the traversing of data from any node.

Applications of BFS Algorithm

Let’s take a look at some of the real-life applications where a BFS algorithm implementation can be highly
effective.

 Un-weighted Graphs: BFS algorithm can easily create the shortest path and a minimum spanning
tree to visit all the vertices of the graph in the shortest time possible with high accuracy.
 P2P Networks: BFS can be implemented to locate all the nearest or neighboring nodes in a peer to
peer network. This will find the required data faster.
 Web Crawlers: Search engines or web crawlers can easily build multiple levels of indexes by
employing BFS. BFS implementation starts from the source, which is the web page, and then it visits
all the links from that source.
 Navigation Systems: BFS can help find all the neighboring locations from the main or source
location.

31
  Network Broadcasting: A broadcasted packet is guided by the BFS algorithm to find and reach all
the nodes it has the address for.

C Program to implement Breadth First Search (BFS) using array based queue
BFS is commonly used for:
 Shortest path finding in unweighted graphs.
 Level-order traversal in trees.
 Finding connected components in a graph.
 Solving puzzles like the 8-puzzle.
Steps of BFS:
1. Start at a specific node (called the root or starting node).
2. Mark it as visited.
3. Enqueue the starting node into a queue.
4. While the queue is not empty:
o Dequeue a node.
o Visit all its unvisited neighbors (nodes connected to it), mark them as visited, and enqueue
them into the queue.
5. Repeat this process until all reachable nodes have been visited.
Properties of BFS:
 Level-Order Traversal: BFS explores the graph level by level.
 Shortest Path: In an unweighted graph, BFS guarantees the shortest path from the start node to any
other node.
 Queue Data Structure: BFS uses a queue to manage the order of node exploration.
BFS Example:
Consider the following unweighted graph:
0
/\
1 2
/ \
3 4
 Starting node: 0
 BFS Traversal:
Start from 0, visit 0, enqueue its neighbors 1 and 2.
Then visit 1 and 2, enqueue their neighbors 3 and 4 (if not visited).
Continue until all nodes are visited.

32
Order of visiting:
BFS(0) → 0 → 1 → 2 → 3 → 4

Program:
#include <stdio.h>

#define SIZE 10 // Maximum number of vertices allowed in the graph

int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value)

{
if (rear == SIZE - 1)
{
return;
}
if (front == -1) front = 0;
rear++;
queue[rear] = value;
}

int dequeue()
{
if (front == -1)
{
return -1;
}
return queue[front++];
}

void bfs(int graph[SIZE][SIZE], int visited[], int start, int n)

{
enqueue(start); // Start BFS from the given start vertex
visited[start] = 1; // Mark the start vertex as visited

while (front <= rear)

{
// Continue while the queue is not empty
int current = dequeue(); // Get the current vertex from the queue
printf("%d ", current); // Print the current vertex

// Visit all adjacent vertices of the current vertex

for (int i = 0; i < n; i++)
{
if (graph[current][i] == 1 && visited[i] == 0)
{
// If there's an edge and the vertex is not visited
enqueue(i); // Add vertex to the queue
visited[i] = 1; // Mark it as visited

33
 }
}
}
}

int main()
{
int graph[SIZE][SIZE]; // Adjacency matrix representation of graph
int visited[SIZE] = {0}; // Array to keep track of visited vertices
int n, start;

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter the adjacency matrix (0 or 1):\n");

for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &graph[i][j]); // Input 1 if edge exists, else 0
}
}

// Input starting vertex for BFS traversal

printf("Enter the starting vertex (0 to %d): ", n - 1);
scanf("%d", &start);

// Perform BFS traversal and print the result

printf("BFS traversal: ");
bfs(graph, visited, start, n);

return 0;
}
Output 1:
Enter number of vertices: 4
Enter the adjacency matrix (0 or 1):
0111
1010
1101
1010
Enter the starting vertex (0 to 3): 1
BFS traversal: 1 0 2 3

Output 2:
Enter number of vertices: 5
Enter the adjacency matrix (0 or 1):
01100
10110
11001
01001
00110
Enter the starting vertex (0 to 4): 3

34
BFS traversal: 3 1 4 0 2

Scheduling
Scheduling using queues is a common approach in operating systems, networking, and task management
systems. Here’s a breakdown of how it works:
1. Types of Scheduling Using Queues
 CPU Scheduling: Queues manage processes waiting for CPU time.
 Job Scheduling: Jobs are placed in queues before being assigned resources.
 Disk Scheduling: Requests to read/write from a disk are managed in a queue.
 Network Scheduling: Packets waiting to be transmitted are queued.
2. Types of Queues in Scheduling
 Ready Queue: Holds processes that are ready to execute.
 Job Queue: Contains all processes waiting for execution.
 Device Queue: Holds processes waiting for I/O operations.
3. Scheduling Algorithms Using Queues
 First-Come, First-Served (FCFS): The first process in the queue is executed first.
 Round Robin (RR): Each process gets a fixed time slice in a cyclic order.
 Priority Scheduling: Processes are scheduled based on priority values.
 Shortest Job Next (SJN): The shortest task in the queue gets executed first.
 Multilevel Queue Scheduling: Processes are divided into multiple queues based on priority or type.
4. Example: Round Robin Scheduling Using a Queue
 Each process gets executed for the given time quantum.
 If a process isn't finished, it's placed back in the queue.
 The process completes when its remaining time reaches zero.

Implementation of Round Robin Scheduling using Queues

Program:
#include <stdio.h>

void round_robin(int processes[], int n, int burst_time[], int quantum) {

int remaining_time[n];
for (int i = 0; i < n; i++)
remaining_time[i] = burst_time[i];

int time = 0, done;

do {
done = 1;
for (int i = 0; i < n; i++) {
if (remaining_time[i] > 0) {

35
 done = 0;
if (remaining_time[i] > quantum) {
printf("Process %d executed for %d units\n", processes[i], quantum);
remaining_time[i] -= quantum;
time += quantum;
} else {
printf("Process %d completed\n", processes[i]);
time += remaining_time[i];
remaining_time[i] = 0;
}
}
}
} while (!done);
}

int main() {
int n = 3, quantum = 4;
int processes[] = {1, 2, 3};
int burst_time[] = {10, 5, 8};

round_robin(processes, n, burst_time, quantum);

return 0;
}
Output:
Process 1 executed for 4 units
Process 2 executed for 4 units
Process 3 executed for 4 units
Process 1 executed for 4 units
Process 2 completed
Process 3 completed
Process 1 completed

Time Complexity of Queues:

C program to implement double ended queue (DEQUE)

Program:
#include <stdio.h>
#define MAX 5

36
int deque[MAX];
int front = -1, rear = -1;

void insertRear(int value)

{
if (rear == MAX - 1)
{
printf("Queue is full at rear.\n");
return;
}
else
{
rear++;
deque[rear] = value;
printf("Inserted %d at rear.\n", value);
if (front == -1)
front = 0;
}
}

void insertFront(int value)

{
if (front == 0 )
{
printf("Queue is Full.\n");
return;
}
else if (front == -1 )
{
front++;
rear++;
deque[front] = value;
}
else
{
front--;
deque[front]=value;
printf("Inserted %d at front.\n", value);
}
}

void deleteFront()
{
if (front == -1)
{
printf("Queue is empty.\n");
return;
}
else if(front==rear)
front=rear=-1;
else
printf("Deleted from front: %d\n", deque[front]);

37
 front++;
}

void deleteRear()
{
if (rear == -1 && front ==-1)
{
printf("Queue is empty.\n");
return;
}
else if(front==rear)
{
printf("Deleted from rear: %d\n", deque[rear]);
front=rear=-1;
}
else
{
printf("Deleted from rear: %d\n", deque[rear]);
rear=rear-1;
}
}

void display()
{
if (front == -1)
{
printf("Queue is empty.\n");
return;
}
printf("Deque elements: ");
for (int i = front; i <= rear; i++)
{
printf("%d ", deque[i]);
}
printf("\n");
}

int main()
{
int choice, value;
while (1)
{
printf("\n--- Deque Menu ---\n");
printf("1. Insert at Rear\n");
printf("2. Insert at Front\n");
printf("3. Delete from Front\n");
printf("4. Delete from Rear\n");
printf("5. Display\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

38
 switch (choice)
{
case 1:
printf("Enter value to insert at rear: ");
scanf("%d", &value);
insertRear(value);
break;
case 2:
printf("Enter value to insert at front: ");
scanf("%d", &value);
insertFront(value);
break;
case 3:
deleteFront();
break;
case 4:
deleteRear();
break;
case 5:
display();
break;
case 6:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}
Applications of Deques

1. Palindrome Checking

 Check characters from both ends of a string.

 If characters match from front and rear until the middle — it’s a palindrome!

2. Sliding Window Maximum / Minimum (in Arrays)

 Used in problems where you need to find the max/min in every window of size k.
 Deque helps maintain candidates efficiently in O(n) time.

3. Job / Task Scheduling

 High priority tasks can be inserted at front.

 Normal tasks at rear.
 Deque allows flexibility in task ordering.
39
4. Undo and Redo Operations

 In editors, you can undo (pop from one end) or redo (push to other end).
 Deques are perfect for this two-way movement.

5. Input and Output Restricted Queues

 Deques can simulate:

o Input-Restricted Queue (insert at rear, delete at both ends)
o Output-Restricted Queue (insert at both ends, delete at front)

6. Browser History Navigation

 Back and Forward operations work like deque ends.

 You can push/pop URLs depending on user navigation.

7. Train Coaches Simulation

 Coaches can be added/removed from front or rear of a train simulation.

8. Memory Management

 In systems like memory caches or CPU task management, deques help manage entries from both
ends (like LRU cache).

9. Implement Stack and Queue

 A deque can simulate both a stack (LIFO) and a queue (FIFO) depending on which ends you use.

40