QUEUE

MODULE-3
● Queue Operations and Applications
● Variants: Circular Queue, Priority Queue, Deque

Queue:
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This
means that the element inserted first will be the one to be removed first — like a line of
people waiting for a service.

Queues can be implemented using:

 Arrays (fixed size, needs shifting in some cases)

 Linked Lists (dynamic size, no shifting needed)

Basic Representation:

 Front: Position of the entry in a queue ready to be served, that is, the first entry that
will be removed from the queue, is called the front of the queue. It is also referred
as the head of the queue.
 Rear: Position of the last entry in the queue, that is, the one most recently added, is
called the rear of the queue. It is also referred as the tail of the queue.

Types of Queue:

1. Simple Queue (Linear Queue) – Basic FIFO structure.

2. Circular Queue – Last position connects back to the first to utilize space efficiently.
3. Priority Queue – Each element has a priority, and removal is based on priority.
4. Double-Ended Queue (Deque) – Insertion and deletion allowed at both ends.
Applications :
 CPU Scheduling: To manage processes waiting to be executed by the CPU.
 Disk Scheduling: Manage the sequence of read/write requests sent to the disk controller.
 Print Queue: Manage multiple documents waiting to be printed.
 Data Buffers / IO Buffers: Temporarily hold data during data transfer between two
devices/systems. For example, when streaming audio/video, data is buffered using a
queue.
 Breadth-First Search (BFS) in Graphs and Trees: To explore nodes level by level.
 Handling Requests in Web Servers: Web servers handle client requests using queues.
 Call Center Systems: Manage incoming customer calls.
 Simulation Systems: Used in event-driven simulations (e.g., traffic lights, checkout
systems).

Linear Queue (Simple Queue)Operations:

Operation Description Time Complexity
Enqueue() Insert element at the rear O(1)
Dequeue() Remove element from the front O(1)
View element at the front without
Peek() / Front() O(1)
removing
isEmpty() Check if queue is empty O(1)
Check if queue is full (in case of fixed
isFull() O(1)
size)

1. Enqueue (Insertion)

Goal: Add an element to the rear of the queue.

Algorithm:

1. Check if the queue is full

o If rear == MAX_SIZE - 1 → Queue Overflow → Stop.
2. If queue is empty (front == -1):
o Set front = 0 (first element position).
3. Increase rear pointer: rear = rear + 1
4. Insert the element at queue[rear]
5. End

2. Dequeue (Deletion)

Goal: Remove an element from the front of the queue.

Algorithm:

1. Check if the queue is empty

o If front == -1 → Queue Underflow → Stop.
2. Display the element at queue[front]
3. Increase front pointer: front = front + 1
4. If front > rear, set both front = -1 and rear = -1 (queue becomes empty).
5. End

3. Peek / Front

Goal: View the element at the front without removing it.

Algorithm:

1. Check if the queue is empty

o If front == -1 → Queue is Empty → Stop.
2. Return the element at queue[front]
3. End

4. isEmpty

Goal: Check whether the queue has no elements.

Algorithm:

1. If front == -1 → Queue is empty → Return True

2. Else → Return False

5. isFull

Goal: Check whether the queue has reached its maximum capacity.

Algorithm:

1. If rear == MAX_SIZE - 1 → Queue is full → Return True

2. Else → Return False

Menu driven C Program for all Queue Operations (Array Implementation)

#include <stdio.h>
#include <stdlib.h>

#define MAX 5 // Maximum size of Queue

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

// Function to check if queue is full

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

// Function to check if queue is empty

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

// Function to insert an element in queue

void enqueue(int value) {
if (isFull()) {
printf("Queue is Full! (Overflow)\n");
} else {
if (front == -1) // First element being inserted
front = 0;
rear++;
queue[rear] = value;
printf("Inserted %d into the queue.\n", value);
}
}

// Function to delete an element from queue

void dequeue() {
if (isEmpty()) {
printf("Queue is Empty! (Underflow)\n");
} else {
printf("Deleted %d from the queue.\n", queue[front]);
front++;
if (front > rear) {
// Reset queue to empty state
front = rear = -1;
}
}
}

// Function to view front element

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

// Function to display the queue

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

// Main function with menu-driven program

int main() {
int choice, value;

while (1) {
printf("\n--- Queue Menu ---\n");
printf("1. Enqueue (Insert)\n");
printf("2. Dequeue (Delete)\n");
printf("3. Peek (Front Element)\n");
printf("4. Display Queue\n");
printf("5. Exit\n");
printf("Enter your 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:
peek();
break;
case 4:
 display();
break;
case 5:
exit(0);
default:
printf("Invalid choice! Please try again.\n");
}
}
return 0;
}

Drawback of Simple Queue: After several dequeues, empty slots before front can’t be reused
without shifting elements → wasted space.

Circular Queue:
Its is a type of queue where the last position is connected to the first to form a circle, allowing
unused spaces to be reused.

It overcomes the limitation of a linear queue where space can’t be reused once elements
are dequeued.

Front and Rear pointers are used to track the queue's start and end.
Usually it is represented as an array with modulus (%) for index wrapping.
Operations:
0. Initialization

1. Set front = -1.

2. Set rear = -1.
3. (Optional) Allocate queue array of length size.

1. isEmpty()

1. If front == -1 then return TRUE.

2. Else return FALSE.

2. isFull()

1. If (rear + 1) % size == front then return TRUE.

2. Else return FALSE.

3. Enqueue(x) — Insert element x

1. Check isFull():
a. If TRUE → report Overflow and stop.
2. If front == -1 (queue is empty):
a. Set front = 0.
b. Set rear = 0.
3. Else:
a. Set rear = (rear + 1) % size.
4. Store queue[rear] = x.
5. End (optionally return success).

4. Dequeue() — Remove and return front element

1. Check isEmpty():
a. If TRUE → report Underflow and stop (or return error).
2. Let temp = queue[front] (value to return).
3. If front == rear (only one element):
a. Set front = -1.
b. Set rear = -1. // queue becomes empty
4. Else:
a. Set front = (front + 1) % size.
5. Return temp.

5. Peek() / Front()

1. Check isEmpty():
a. If TRUE → report Queue is empty and stop (or return error).
2. Return queue[front].
Complexity

 Time for enqueue, dequeue, peek, isEmpty, isFull: O(1).

 Display: O(n) in worst case.
 Space: O(size).

C code for all operations on Circular Queue

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5 // Maximum size of queue

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

// Function to check if queue is empty

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

// Function to check if queue is full

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

// Enqueue operation
void enqueue(int x) {
if (isFull()) {
printf("Overflow: Queue is Full\n");
return;
}
if (front == -1) { // Queue is empty
front = 0;
rear = 0;
} else {
rear = (rear + 1) % SIZE;
}
queue[rear] = x;
printf("%d inserted into the queue\n", x);
}

// Dequeue operation
int dequeue() {
if (isEmpty()) {
printf("Underflow: Queue is Empty\n");
return -1; // Error value
}
int temp = queue[front];
if (front == rear) { // Only one element
front = -1;
rear = -1;
} else {
front = (front + 1) % SIZE;
}
printf("%d removed from the queue\n", temp);
return temp;
}

// Peek operation
int peek() {
if (isEmpty()) {
printf("Queue is Empty\n");
return -1;
}
return queue[front];
}

// Display all elements

void display() {
if (isEmpty()) {
printf("Queue is Empty\n");
return;
}
printf("Queue elements: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear)
break;
i = (i + 1) % SIZE;
}
printf("\n");
}

// Main function
int main() {
 int choice, value;
while (1) {
printf("\n--- Circular Queue Menu ---\n");
printf("1. Enqueue\n2. Dequeue\n3. Peek\n4. Display\n5. Exit\n");
printf("Enter 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:
value = peek();
if (value != -1)
printf("Front element: %d\n", value);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}

Double Ended Queue (Deque):

A Deque (Double Ended Queue) is a linear data structure where insertion and deletion can be done
from both ends — front and rear.

Types of Deque:

1. Input-Restricted Deque – Insertion at only one end, deletion from both ends.
2. Output-Restricted Deque – Deletion at only one end, insertion from both ends.
Operations on Deque (Circular array implementation):
1. isEmpty()

1. If front == -1 then return TRUE.

2. Else return FALSE.

2. isFull()

1. If ( (rear + 1) % size == front ) then return TRUE.

2. Else return FALSE.

3. insertFront(x) — Insert element x at the front

1. Check isFull():
1. If TRUE → report Overflow and stop.
2. If front == -1 (deque is empty):
1. Set front = 0.
2. Set rear = 0.
3. Else if front == 0:
1. Set front = size - 1 (wrap around).
4. Else:
1. Set front = front - 1.
5. Store deque[front] = x.
6. End (optionally return success).

4. insertRear(x) — Insert element x at the rear

1. Check isFull():
1. If TRUE → report Overflow and stop.
2. If front == -1 (deque is empty):
1. Set front = 0.
2. Set rear = 0.
3. Else if rear == size - 1:
1. Set rear = 0 (wrap around).
 4. Else:
1. Set rear = rear + 1.
5. Store deque[rear] = x.
6. End (optionally return success).

5. deleteFront() — Remove and return element from front

1. Check isEmpty():
1. If TRUE → report Underflow and stop.
2. Let temp = deque[front] (value to return).
3. If front == rear (only one element in deque):
1. Set front = -1.
2. Set rear = -1. // deque becomes empty
4. Else if front == size - 1:
1. Set front = 0.
5. Else:
1. Set front = front + 1.
6. Return temp.

6. deleteRear() — Remove and return element from rear

1. Check isEmpty():
1. If TRUE → report Underflow and stop.
2. Let temp = deque[rear] (value to return).
3. If front == rear (only one element in deque):
1. Set front = -1.
2. Set rear = -1.
4. Else if rear == 0:
1. Set rear = size - 1.
5. Else:
1. Set rear = rear - 1.
6. Return temp.

7. peekFront() — View the front element without removing it

1. Check isEmpty():
1. If TRUE → report Deque is empty and stop.
2. Return deque[front].

8. peekRear() — View the rear element without removing it

1. Check isEmpty():
1. If TRUE → report Deque is empty and stop.
2. Return deque[rear].
Complexity

 Time Complexity:
o insertFront, insertRear, deleteFront, deleteRear, peekFront, peekRear, isEmpty, isFull →
O(1)
o display → O(n) worst case.
 Space Complexity: O(size).

Priority Queue :
A Priority Queue is a special type of queue where each element is associated with a priority and the
element with the highest priority is served before elements with lower priority.
If two elements have the same priority, they are served according to their order of arrival (FIFO).

Here priority can be Ascending Priority (smallest value = highest priority) or Descending Priority
(largest value = highest priority).

Operations on Priority Queue

We’ll assume Ascending Priority Queue (smaller value = higher priority) using an unsorted
array for simple algorithms.

Operation 1: isEmpty()

Purpose: Checks if the priority queue is empty.

Algorithm:

1. If n == 0 (no elements), return TRUE. (n= number of elements currently present in the
priority queue.)
2. Else, return FALSE.

Operation 2: isFull()

Purpose: Checks if the priority queue is full.

Algorithm:
 1. If n == size (maximum capacity reached), return TRUE.
2. Else, return FALSE.

Operation 3: enqueue(x, priority) — Insert element with priority

Algorithm (Unsorted Array):

1. If isFull() is TRUE, report Overflow and stop.

2. Store (x, priority) at queue[n]. (x = value/data, priority = priority number)
3. Increment n = n + 1.
4. End.

Operation 4: dequeue() — Remove element with highest priority

Algorithm (Unsorted Array, Ascending Priority):

1. If isEmpty() is TRUE, report Underflow and stop.

2. Set pos = 0 (assume first position is the highest priority element).
3. For i = 1 to n - 1:
o If queue[i].priority < queue[pos].priority:
 Set pos = i.
4. Store (element, priority) from queue[pos] in a temporary variable temp.
5. Shift all elements from pos + 1 to n - 1 one position left.
6. Decrement n = n - 1.
7. Return temp.

Operation 5: peek() — View element with highest priority without removing it

Algorithm:

1. If isEmpty() is TRUE, report Queue is empty and stop.

2. Set pos = 0.
3. For i = 1 to n - 1:
o If queue[i].priority < queue[pos].priority:
 Set pos = i.
4. Return queue[pos].

Complexity (Unsorted Array Implementation)

Operation Time Complexity

enqueue O(1)

dequeue O(n)

peek O(n)

isEmpty O(1)

isFull O(1)
Operation Time Complexity

Example (Ascending Priority)

Let size = 5 and elements (value, priority):

 enqueue(10, 3) → [(10,3)]
 enqueue(5, 1) → [(10,3), (5,1)]
 enqueue(8, 2) → [(10,3), (5,1), (8,2)]
 dequeue() → Removes (5,1) (lowest priority number = highest priority)
 Queue now → [(10,3), (8,2)]

Implementation of Priority queue in Sorted Array

(We’ll assume Ascending Priority Queue (smaller value = higher priority))
1. isEmpty()

Purpose: Check if queue has no elements.

Algorithm:

1. If n == 0 → return TRUE.
2. Else → return FALSE.

2. isFull()

Purpose: Check if queue is full.

Algorithm:

1. If n == size → return TRUE.

2. Else → return FALSE.

3. enqueue(x, priority) — Insert while keeping sorted order

Purpose: Insert (x, priority) into correct position so that array remains sorted in ascending
priority order.

Algorithm:

1. If isFull() is TRUE → print Overflow and stop.

2. Set i = n - 1 (last index).
3. (checks priority only with the last element that was inserted)
 While i >= 0 and queue[i].priority > priority:

o Move queue[i] to
Operation Unsorted Array Sorted Array queue[i + 1].
o Decrement i = i - 1.
4. enqueue O(1) O(n) Place (x, priority) at queue[i +
1].
5. dequeue O(n) O(1) Increment n = n + 1.
6. End.
peek O(n) O(1)
Example:
Queue: [(B, 1), (C, 3), (E, 5)], n = 3
Insert (D, 4) → shifts (E, 5) right → New queue: [(B, 1), (C, 3), (D, 4), (E, 5)].

4. dequeue() — Remove highest priority element

Purpose: Remove element at the front (index 0) because it's already the smallest priority.

Algorithm:

1. If isEmpty() is TRUE → print Underflow and stop.

2. Store (element, priority) = queue[0] in temp.
3. Shift all elements from index 1 to n - 1 one step left.
4. Decrement n = n - 1.
5. Return temp.
6. End.

Example:
Queue: [(B, 1), (C, 3), (D, 4)] → remove (B, 1) → New queue: [(C, 3), (D, 4)].

5. peek() — View highest priority element

Purpose: Just return the element at the front without removing it.

Algorithm:

1. If isEmpty() is TRUE → print Queue is empty and stop.

2. Return queue[0].

Example:
Queue: [(B, 1), (C, 3), (D, 4)] → Peek returns (B, 1).

Comparison: Unsorted vs Sorted Array Priority Queue