Week 6

6. a) Implementing Queue Operations using Array

Aim: To implement queue operations using array.

Description: Implementing a queue using an array in C involves maintaining a fixed-size
buffer and two pointers, typically named front and rear, to track the positions for deletion and
insertion respectively.

FIFO Principle: Queues operate on a First-In-First-Out basis, where the first element
added is the first one removed.
Pointers:
front: Tracks the index of the first element to be removed.
rear: Tracks the index where the next element will be inserted.
Initialization: Both front and rear are typically initialized to -1 to indicate an empty
queue.

Source Code:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
int queue[SIZE];
int front = -1;
int rear = -1;
// Check if the queue is full
int isFull()
{
if (rear == SIZE - 1)
return 1;
return 0;
}
// Check if the queue is empty
int isEmpty()
{
if (front == -1 || front > rear)
return 1;
return 0;
}
// Add an element to the rear of the queue
void enqueue(int value)
{
if (isFull())
 {
printf("Queue Overflow! Cannot add %d\n", value);
}
else
{
if (front == -1) front = 0;
rear++;
queue[rear] = value;
printf("Inserted %d\n", value);
}
}
// Remove an element from the front of the queue
void dequeue()
{
if (isEmpty())
{
printf("Queue Underflow! Nothing to delete\n");
}
else
{
printf("Deleted element: %d\n", queue[front]);
front++;
if (front > rear)
{
// Reset pointers if queue becomes empty
front = rear = -1;
}
}
}
// Display all elements in the queue
void display()
{
int i;
if (isEmpty())
{
printf("Queue is empty\n");
}
else
{
printf("Queue elements: ");
for (i = front; i <= rear; i++)
{
printf("%d ", queue[i]);
}
printf("\n");
}
 }
int main()
{
int choice, value;
printf("Queue implementation using Arrays\n");
while (1)
{
printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\nEnter choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}

Test Data:
Queue implementation using Arrays
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 10
Inserted 10
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 20
Inserted 20
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 30
Inserted 30
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 40
Inserted 40
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 50
Inserted 50
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Queue elements: 10 20 30 40
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2
Deleted element: 10
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Queue elements: 20 30 40 50
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2
Deleted element: 20
 1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Queue elements: 30 40 50
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 4

Result: The queue was implemented successfully using array.

6. b) Implementing Queue Operations using Linked List

Aim: To implement queue operations using linked list.

Description:
Implementing a queue using a linked list involves creating a dynamic data structure
where nodes are added to the rear and removed from the front, following
the FIFO (First-In-First-Out) principle.
This dynamic approach allows the queue to grow or shrink as needed without a fixed size
limit.

Source Code:
#include <stdio.h>
#include <stdlib.h>
// Define the node structure
struct Node
{
int data;
struct Node* next;
};
// Pointers to the front and rear of the queue
struct Node* front = NULL;
struct Node* rear = NULL;
// Add an element to the rear of the queue
void enqueue(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = NULL;
if (rear == NULL)
{
// If queue is empty, both front and rear point to the new node
front = rear = newNode;
}
else
{
// Link the new node at the end and update rear
rear->next = newNode;
rear = newNode;
}
printf("Enqueued: %d\n", value);
}
// Remove an element from the front of the queue
void dequeue() {
if (front == NULL)
{
printf("Queue Underflow: Queue is empty\n");
return;
}
struct Node* temp = front;
printf("Dequeued: %d\n", temp->data);

front = front->next;
// If front becomes NULL, the queue is now empty, so set rear to NULL
if (front == NULL)
{
rear = NULL;
}
free(temp);
}
// Display all elements in the queue
void display()
{
if (front == NULL)
{
printf("Queue is empty\n");
return;
}
struct Node* temp = front;
printf("Queue elements: ");
while (temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main()
{
int choice, value;
printf("Queue implementation using Linked List\n");
while (1)
{
printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\nEnter choice: ");
scanf("%d", &choice);
switch (choice)
{
 case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}

Test Data:

Queue implementation using Linked List

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 10
Enqueued: 10
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 20
Enqueued: 20
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 30
Enqueued: 30
1. Enqueue
2. Dequeue
 3. Display
4. Exit
Enter choice: 3
Queue elements: 10 -> 20 -> 30 -> NULL
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2
Dequeued: 10
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Queue elements: 20 -> 30 -> NULL
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2
Dequeued: 20
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Queue elements: 30 -> NULL
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2
Dequeued: 30
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Queue is empty
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 4
Result: The queue was implemented successfully using linked list.
6. c ) Simulating A Simple Printer Queue System

Aim: To develop a program to simulate a simple printer queue system using queue data
structure.

Description: A simple printer queue system can be implemented using a queue data structure
based on the First-In, First-Out (FIFO) principle.
Steps:
Enqueue: Adds a new print job to the end of the queue.
Dequeue: Removes and processes the job at the front of the queue.
Display: Lists all current pending print jobs.

Source Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 5
typedef struct
{
char jobName[50];
int pages;
} PrintJob;
PrintJob queue[MAX];
int front = -1, rear = -1;
void addJob(char name[], int p)
{
if (rear == MAX - 1)
{
printf("Queue Full! Cannot add job: %s\n", name);
}
else
{
if (front == -1) front = 0;
rear++;
strcpy(queue[rear].jobName, name);
queue[rear].pages = p;
printf("Added job: %s (%d pages)\n", name, p);
}
}
void processJob()
{
if (front == -1 || front > rear)
{
printf("No jobs to process.\n");
 }
else
{
printf("Processing: %s (%d pages)...\n", queue[front].jobName, queue[front].pages);
front++;
}
}
void displayQueue()
{
int i;
if (front == -1 || front > rear)
{
printf("Queue is empty.\n");
}
else
{
printf("Current Queue:\n");
for (i = front; i <= rear; i++)
{
printf("- %s (%d pages)\n", queue[i].jobName, queue[i].pages);
}
}
}
int main()
{
addJob("DS_Assignment [Link]", 5);
addJob("Employee [Link]", 2);
displayQueue();
processJob();
displayQueue();
return 0;
}
Test Data:
Added job: DS_Assignment [Link] (5 pages)
Added job: Employee [Link] (2 pages)
Current Queue:
- DS_Assignment [Link] (5 pages)
- Employee [Link] (2 pages)
Processing: DS_Assignment [Link] (5 pages)...
Current Queue:
- Employee [Link] (2 pages)

Result: The simple printer queue system was implemented successfully using queue data
structure.
6.d) Solving Memory Problem using Circular Queue

Aim: To implement C program to solve memory problem using circular queue.

Description: In a standard linear queue using an array, memory wastage occurs because once
elements are dequeued, the vacated slots at the beginning of the array cannot be
reused. The Circular Queue is the standard programmatic solution to this problem, as it allows
the rear pointer to wrap around to the first available index when it reaches the end of the array.
Steps
• Modulo Arithmetic: Use the modulo operator (%) to wrap pointers back to the
beginning of the array: (index + 1) % SIZE.
• Pointers: Maintain two variables, front and rear, both initially set to -1.
• Full Condition: The queue is full when (rear + 1) % SIZE == front.
• Empty Condition: The queue is empty when front == -1.
Source Code:
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if queue is full or empty
int isFull()
{
return (front == (rear + 1) % SIZE);
}
int isEmpty()
{
return (front == -1);
}
// Enqueue with wrap-around capability
void enqueue(int element)
{
if (isFull())
printf("Queue Full\n");
else
{
if (front == -1)
 front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("Inserted -> %d\n", element);
}
}
// Dequeue with wrap-around capability
int dequeue()
{
if (isEmpty())
return -1;
int element = items[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
return element;
}
// Display queue elements
void display()
{
int i;
if (isEmpty())
printf("Empty Queue\n");
else
{
printf("Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE)
printf("%d ", items[i]);
printf("%d\n", items[rear]);
}
}
int main()
{
printf("Circular Queue Implementation\n");
int choice, value;
while (1)
{
printf("Queue implementation using Arrays\n");
printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\nEnter choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
Test Data:
Circular Queue implementation using Arrays
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 10
Inserted -> 10

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 20
Inserted -> 20

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 30
Inserted -> 30

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 40
Inserted -> 40

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 50
Inserted -> 50

1. Enqueue
2. Dequeue
3. Display
4. Exit
 Enter choice: 3
Items -> 10 20 30 40 50

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 2

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Items -> 30 40 50

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 60
Inserted -> 60

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 3
Items -> 30 40 50 60

1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter choice: 4

Result: The C program was implemented to solve memory problem using circular queue.