1|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

Unit –VI
Queue
1. Queue

1.1 Basic Concept

A Queue Data Structure is a fundamental concept in computer science used for storing and
managing data in a specific order. It follows the principle of "First in, First out" (FIFO),
where the first element added to the queue is the first one to be removed. Queues are commonly
used in various algorithms and applications for their simplicity and efficiency in managing data
flow.

A Queue is like a line waiting to purchase tickets, where the first person in line is the first
person served. (i.e. First Come First Serve).

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 (sometimes, head of the queue). Similarly, the
position of the last entry in the queue, that is, the one most recently added, is called the rear (or
the tail) of the queue.
2|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

1.2 Queue as Abstract Data Type

 The queue abstract data type (ADT) follows the basic design of the stack abstract data type.

 Each node contains a void pointer to the data and the link pointer to the next element in the
queue. The program’s responsibility is to allocate memory for storing the data.

 enqueue() – Insert an element at the end of the queue.

 dequeue() – Remove and return the first element of the queue, if the queue is not empty.

 peek() – Return the element of the queue without removing it, if the queue is not empty.

 size() – Return the number of elements in the queue.

 isEmpty() – Return true if the queue is empty, otherwise return false.

 isFull() – Return true if the queue is full, otherwise return false.

1.3 Queue Operations

1. enqueue(value): This operation adds an element to the rear (end) of the queue.

Steps:

1. Check for queue overflow:

 If the rear index points to the last position in the array and the queue is full,
insertion is not allowed.

2. If the queue is empty (both front and rear are -1), set front = 0 and rear = 0.

3. If not empty, increment the rear and insert the element at the new position.

2. dequeue(): This operation removes an element from the front of the queue.

Steps:
3|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

1. Check for queue underflow:

 If the queue is empty (front = -1 or front > rear), no deletion is possible.

2. Retrieve the element at the front.

3. Increment the front to the next position.

4. If after deletion, front > rear, reset front and rear to -1 (queue is empty).

3. peek(): This operation retrieves the element at the front of the queue without removing it.

Steps:

1. Check if the queue is empty (front = -1).

2. If not empty, return the element at the front.

4. isEmpty(): This operation checks whether the queue is empty.

Steps:

1. If front = -1, or front > rear, return true (queue is empty).

2. Otherwise, return false.

5. isFull(): This operation checks whether the queue has reached its maximum size (only
for array-based implementation).

Steps:

1. If rear = size - 1, return true (queue is full).

4|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

2. Otherwise, return false.

1.4 Representation of Queue using Sequential Organization

A queue can be efficiently represented using a linear array. Two variables, front and rear, are
used to keep track of the positions where elements are deleted and inserted, respectively.

1. Initial State: When the queue is empty:

 front = -1 (indicates no element is present).

 rear = -1 (no element has been inserted yet).

2. After Inserting the First Element: When the first element is inserted:

 Both front and rear are set to 0 (pointing to the same index, where the first element is
stored).

3. During Normal Operations: After inserting more elements:

 rear increments with each insertion, pointing to the latest added element.
 front remains unchanged until a deletion occurs.

4. After Deleting Elements: After an element is dequeued:

 front increments by 1, pointing to the next element to be removed.

5|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

Example: Pseudo C++ Code for Linear Queue Implementation Using Array

// Define the structure of the Queue

class LinearQueue {
int front; // Index of the front element
int rear; // Index of the rear element
int size; // Maximum size of the queue
int* queue; // Array to store queue elements

public:
// Constructor to initialize the queue
LinearQueue(int capacity) {
size = capacity;
queue = new int[size];
front = -1;
rear = -1;
}

// Function to check if the queue is empty

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

// Function to check if the queue is full

bool isFull() {
return rear == size - 1;
}
6|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Function to enqueue (add) an element

void enqueue(int element) {
if (isFull()) {
print("Queue Overflow! Cannot add element.");
return;
}
if (isEmpty()) {
front = 0; // Initialize front when first element is added
}
rear++;
queue[rear] = element;
}

// Function to dequeue (remove) an element

int dequeue() {
if (isEmpty()) {
print("Queue Underflow! Cannot remove element.");
return -1; // Indicate failure
}
int removedElement = queue[front];
front++;
if (front > rear) {
// Reset queue when all elements are removed
front = -1;
rear = -1;
}
return removedElement;
}

// Function to get the front element

int peek() {
7|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

if (isEmpty()) {
print("Queue is empty! No front element.");
return -1; // Indicate failure
}
return queue[front];
}

// Destructor to free allocated memory

~LinearQueue() {
delete[] queue;
}
};

// Example Usage
void main() {
LinearQueue queue(5); // Create a queue with capacity 5
queue.enqueue(10); // Add elements
queue.enqueue(20);
print(queue.peek()); // Output: 10
print(queue.dequeue()); // Output: 10
print(queue.dequeue()); // Output: 20
print(queue.dequeue()); // Output: Queue Underflow!
}
1.5 Circular Queue and its advantages

A Circular Queue is an extended version of a normal queue where the last element of the queue
is connected to the first element of the queue forming a circle.

The operations are performed based on FIFO (First In First Out) principle. It is also
called ‘Ring Buffer’.
8|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

Operations on Circular Queue:

1. enqueue(value): This operation adds an element to the queue.

If the queue is full (i.e., (rear + 1) % size == front), the operation cannot be performed,
and an overflow condition occurs.

If the queue is not full:

 Insert the element at the rear position.

 Update the rear to the next position. If rear reaches the last index of the array, it
wraps around to the first index (circular behavior).

2. dequeue(): This operation removes the front element from the queue.
9|Page © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

If the queue is empty (i.e., front == rear), the operation cannot be performed, and an
underflow condition occurs.

If the queue is not empty:

 Remove the element at the front position.

 Update the front to the next position. If front reaches the last index, it wraps around to
the first index (circular behavior).

3. peek(): This operation allows you to view the front element without removing it.

 If the queue is empty, there is no element to peek at.

 Otherwise, return the element at the front.

4. isFull(): This operation checks whether the queue has reached its maximum capacity.

 Condition: The queue is full if (rear + 1) % size == front

5. isEmpty(): This operation checks if the queue has any elements.

 Condition: The queue is empty if front == rear

Example: Pseudo C++ code to implement Circular Queue

// Define the maximum size of the queue

#define MAX_SIZE 5

// Define the Circular Queue structure

struct CircularQueue {
int arr[MAX_SIZE]; // Array to store queue elements
int front; // Points to the front element of the queue
10 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

int rear; // Points to the last element of the queue

};

// Initialize the Circular Queue

void initializeQueue(CircularQueue &q) {
q.front = -1; // Indicating empty queue
q.rear = -1; // Indicating empty queue
}

// Check if the Circular Queue is empty

bool isEmpty(CircularQueue &q) {
return (q.front == -1); // Front is -1 when queue is empty
}

// Check if the Circular Queue is full

bool isFull(CircularQueue &q) {
return ((q.rear + 1) % MAX_SIZE == q.front); // Check for overflow
}

// Enqueue (Insert) an element to the Circular Queue

void enqueue(CircularQueue &q, int value) {
// Check if the queue is full
if (isFull(q)) {
print("Queue is full! Cannot enqueue.");
return;
}

// If the queue is empty, initialize front and rear

if (isEmpty(q)) {
q.front = 0;
}
11 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Move the rear to the next position in a circular way

q.rear = (q.rear + 1) % MAX_SIZE;
q.arr[q.rear] = value; // Insert the element at the rear position
print("Element enqueued: " + value);
}

// Dequeue (Remove) an element from the Circular Queue

int dequeue(CircularQueue &q) {
// Check if the queue is empty
if (isEmpty(q)) {
print("Queue is empty! Cannot dequeue.");
return -1; // Indicating failure
}

int dequeuedValue = q.arr[q.front]; // Get the front element

// If there's only one element left in the queue

if (q.front == q.rear) {
q.front = q.rear = -1; // Reset to empty queue
} else {
// Move the front to the next position in a circular way
q.front = (q.front + 1) % MAX_SIZE;
}

print("Element dequeued: " + dequeuedValue);

return dequeuedValue; // Return the removed element
}

// Peek (View) the front element of the Circular Queue

int peek(CircularQueue &q) {
// Check if the queue is empty
if (isEmpty(q)) {
12 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

print("Queue is empty! Cannot peek.");

return -1; // Indicating failure
}

return q.arr[q.front]; // Return the front element

}

// Main function to demonstrate Circular Queue operations

void main() {
CircularQueue q;
initializeQueue(q);

enqueue(q, 10); // Enqueue 10

enqueue(q, 20); // Enqueue 20
enqueue(q, 30); // Enqueue 30

print(peek(q)); // Output: 10 (front element)

dequeue(q); // Dequeue the front element (10)

enqueue(q, 40); // Enqueue 40

print(peek(q)); // Output: 20 (new front element after dequeue)

enqueue(q, 50); // Enqueue 50

enqueue(q, 60); // Enqueue 60 (Queue might be full now)

dequeue(q); // Dequeue the front element (20)

}
Advantages of Circular Queue over Linear Queue
13 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

There was one limitation in the array implementation of Queue. If the rear reaches to the end
position of the queue, then there might be possibility that some vacant spaces are left in the
beginning which cannot be utilized. So, to overcome such limitations, the concept of the
circular queue was introduced.

1. No Space Wastage:

 Circular Queue: The front and rear pointers can wrap around, reusing previously
emptied spaces.

 Linear Queue: Once the front reaches the end, no further enqueuing is possible without
resetting.

2. Reduced Overhead:

 Circular Queue: No need to shift elements; it wraps around efficiently.

 Linear Queue: Shifting elements after dequeuing is required, causing overhead.

3. Better Performance in Queue-based Systems:

 Circular Queue: Ideal for buffer management, round-robin scheduling, and continuous
operations.

 Linear Queue: Less efficient when elements are continuously added or removed.

4. Prevents Overflow:

 Circular Queue: Avoids overflow by reusing available space.

14 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

 Linear Queue: Can overflow even with unused space due to fixed rear position.

1.1 Multi-queues

Multi Queues refer to the concept of using multiple queues to manage different sets of data,
typically when tasks or resources are divided into several categories. Each queue is used to
manage a specific type of data or task, and they work independently of each other.

Key Points:

1. Multiple Queues: A system may implement several queues instead of just one, to
handle different types of operations or resources (e.g., one queue for high-priority tasks,
another for low-priority tasks).

2. Shared Storage: Although the queues are separate, they may share a common memory
space (array or linked list) to manage the queues, often by dividing the space into
segments.

3. Usage: Multi-queues are useful in situations where different kinds of data need to be
processed at different rates or with different priorities. For example, in operating
systems, you could have separate queues for different levels of task priorities or
different processes.

4. Implementation: Multi-queues can be implemented by using an array of queues or a

linked list of queues.

Example:

 Queue 1: High-priority tasks.

 Queue 2: Low-priority tasks.

Tasks are processed based on their priority by dequeuing from the respective queue.

Advantage:

 Better resource management by segregating tasks or data types into specialized

queues, improving overall system efficiency.

1.6 Linked Queue and Operations

A queue is generally implemented using an array, but the limitation of this kind of queue is that
the memory occupied by the array is fixed no matter how many elements are in the queue. In
15 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

the queue implemented using a linked list, the size occupied by the linked list will be equal to
the number of elements in the queue. Moreover, its size is dynamic, meaning that the size will
change automatically according to the elements present.

Basic Operations of Linear Queue using Singly Linked List (with isFull)

A linear queue implemented using a singly linked list follows the FIFO (First-In-First-Out)
principle. The basic operations are:

1. enqueue(value): Adds an element at the rear of the queue.

 If the queue is empty, both front and rear pointers are set to the new node.

 Otherwise, the next pointer of the current rear node is updated to point to the new
node, and the rear pointer is updated to the new node.

2. dequeue(): Removes an element from the front of the queue.

16 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

 The element at the front is removed, and the front pointer is updated to the next
node.

 If the queue becomes empty after the dequeue operation, both

front and rear pointers are set to nullptr.

3. peek(): Returns the data of the front element of the queue without removing it.

 If the queue is empty, return an error or nullptr.

4. isEmpty(): Checks if the queue is empty by checking if the front pointer is nullptr.

5. isFull(): Checks if the queue is full

 In a singly linked list implementation, the queue size is dynamic and does not have a
fixed limit, so it is never full as long as there is available memory.

 However, if there's a predefined limit or if memory constraints exist,

the isFull function can be implemented by comparing the number of nodes with the
predefined size limit.

Advantages of Linked List Implementation:

 Dynamic Size: Unlike arrays, the size of the queue is not fixed.

 No Overflow: As long as there is available memory, elements can be added to the

queue.

 Efficient Memory Usage: The queue grows and shrinks as needed, using memory only
for the elements in the queue.

Example: Pseudo C++ Code to implement queue as a singly linked list

// Define the structure of a node

struct Node {
int data; // Data part of the node
Node* next; // Pointer to the next node
};

// Define the queue

Node* front = nullptr; // Front of the queue
17 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

Node* rear = nullptr; // Rear of the queue

// Function to check if the queue is empty

bool isEmpty() {
return front == nullptr;
}

// Function to enqueue (add element to the queue)

void enqueue(int element) {
Node* newNode = new Node();
newNode->data = element;
newNode->next = nullptr;

if (isEmpty()) {
front = newNode; // If the queue is empty, front points to
the new node
} else {
rear->next = newNode; // Link the current rear to the new
node
}
rear = newNode; // Move the rear pointer to the new node
}

// Function to dequeue (remove element from the queue)

int dequeue() {
if (isEmpty()) {
print("Queue Underflow! Cannot dequeue.");
return -1; // Indicate failure
}

int dequeuedValue = front->data;

Node* temp = front;
18 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

front = front->next; // Move the front pointer to the next node

delete temp; // Free the memory of the removed node

if (front == nullptr) {
rear = nullptr; // If the queue is empty, reset the rear
pointer
}
return dequeuedValue;
}

// Function to get the front element of the queue

int peek() {
if (isEmpty()) {
print("Queue is empty! No front element.");
return -1; // Indicate failure
}
return front->data;
}

// Example usage
void main() {
enqueue(10); // Enqueue 10 to the queue
enqueue(20); // Enqueue 20 to the queue
print(peek()); // Output: 10 (front of the queue)
print(dequeue()); // Output: 10 (removed from the queue)
print(dequeue()); // Output: 20 (removed from the queue)
print(dequeue()); // Output: Queue Underflow!
}

2. Deque

2.1 Basic Concept

19 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion
and deletion operations are performed from both ends. We can say that deque is a generalized
version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does not follow
the FIFO rule. The representation of a deque is given as follows –

Operations on a Deque

1. insertFront(): In this operation, the element is inserted from the front end of the queue.

If the queue is not full, then the element can be inserted from the front end by using the below
conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to
the first element.

o Otherwise, check the position of the front if the front is less than 1 (front < 1), then
reinitialize it by front = n - 1, i.e., the last index of the array.

2. insertRear(): In this operation, the element is inserted from the rear end of the queue

If the queue is not full, then the element can be inserted from the rear end by using the below
conditions -
20 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to
the first element.

o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead
of increasing it by 1, we have to make it equal to 0.

3. deleteFront(): In this operation, the element is deleted from the front end of the queue.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform
the deletion. If the queue is not full, then the element can be inserted from the front end by
using the below conditions -

 If the deque has only one element, set rear = -1 and front = -1.
 Else if front is at end (that means front = size - 1), set front = 0.
 Else increment the front by 1, (i.e., front = front + 1).

4. deleteRear(): In this operation, the element is deleted from the rear end of the queue.
21 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform
the deletion.

If the deque has only one element, set rear = -1 and front = -1.

If rear = 0 (rear is at front), then set rear = n - 1.

Else, decrement the rear by 1 (or, rear = rear -1).

5. isEmpty(): This operation is performed to check whether the deque is empty or not.

If front = -1, it means that the deque is empty.

6. isFull(): This operation is performed to check whether the deque is full or not.

If front = rear + 1, or front = 0 and rear = n - 1 it means that the deque is full.

The time complexity of all of the above operations of the deque is O(1), i.e., constant.

Example: Pseudo C++ Code for Dequeue (Double-Ended Queue)

// Define the structure of a node

struct Node {
int data; // Data part of the node
Node* next; // Pointer to the next node
Node* prev; // Pointer to the previous node
};

// Define the dequeue

Node* front = nullptr; // Front of the dequeue
Node* rear = nullptr; // Rear of the dequeue
22 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Function to check if the dequeue is empty

bool isEmpty() {
return front == nullptr;
}

// Insert an element at the front of the dequeue

void insertFront(int element) {
Node* newNode = new Node();
newNode->data = element;
newNode->next = front;
newNode->prev = nullptr;

if (isEmpty()) {
front = rear = newNode; // If empty, both front and rear
point to the new node
} else {
front->prev = newNode; // Link the previous front to the
new node
front = newNode; // Update front to the new node
}
}

// Insert an element at the rear of the dequeue

void insertRear(int element) {
Node* newNode = new Node();
newNode->data = element;
newNode->prev = rear;
newNode->next = nullptr;

if (isEmpty()) {
front = rear = newNode; // If empty, both front and rear
point to the new node
23 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

} else {
rear->next = newNode; // Link the current rear to the new
node
rear = newNode; // Update rear to the new node
}
}

// Delete an element from the front of the dequeue

int deleteFront() {
if (isEmpty()) {
print("Dequeue Underflow! Cannot delete from front.");
return -1; // Indicate failure
}

int deletedValue = front->data;

Node* temp = front;
front = front->next; // Move front to the next node

if (front == nullptr) {
rear = nullptr; // If the dequeue is empty, reset the rear
pointer
} else {
front->prev = nullptr; // Disconnect the front node
}

delete temp; // Free memory of the removed node

return deletedValue;
}

// Delete an element from the rear of the dequeue

int deleteRear() {
if (isEmpty()) {
24 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

print("Dequeue Underflow! Cannot delete from rear.");

return -1; // Indicate failure
}

int deletedValue = rear->data;

Node* temp = rear;
rear = rear->prev; // Move rear to the previous node

if (rear == nullptr) {
front = nullptr; // If the dequeue is empty, reset the front
pointer
} else {
rear->next = nullptr; // Disconnect the rear node
}

delete temp; // Free memory of the removed node

return deletedValue;
}

// Display elements of the dequeue

void displayDequeue() {
if (isEmpty()) {
print("Dequeue is empty.");
return;
}

Node* temp = front;

while (temp != nullptr) {
print(temp->data);
temp = temp->next;
}
}
25 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Example usage
void main() {
insertFront(10); // Insert 10 at the front
insertRear(20); // Insert 20 at the rear
insertFront(5); // Insert 5 at the front
displayDequeue(); // Display all elements in dequeue
print(deleteFront()); // Output: 5 (deleted from front)
print(deleteRear()); // Output: 20 (deleted from rear)
displayDequeue(); // Display remaining elements
}

2.2 Input restricted Queue

An input restricted queue is a special case of a double-ended queue where data can be inserted
from one end(rear) but can be removed from both ends (front and rear). This kind of Queue
does not follow FIFO (first in first out):

Operations on Input Restricted Queue:

Mainly the following three basic operations are performed on input restricted queue:

 insertRear(): Adds an item at the rear of the queue.

 deleteFront(): Deletes an item from the front of the queue.

 deleteRear(): Deletes an item from rear of the queue.

In addition to above operations, following operations are also supported

 getFront(): Gets the front item from the queue.

26 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

 getRear(): Gets the last item from the queue.

 isEmpty(): Checks whether queue is empty or not.

 isFull(): Checks whether queue is full or not.

Example: Pseudo C++ Code for Insertion and Deletion in Input Restricted Deque

// Define the structure of a node

struct Node {
int data; // Data part of the node
Node* next; // Pointer to the next node
};

// Define the deque

Node* front = nullptr; // Front of the deque
Node* rear = nullptr; // Rear of the deque

// Function to check if the deque is empty

bool isEmpty() {
return front == nullptr;
}

// Function to insert at the rear of the deque

void insertRear(int element) {
// Create a new node for the element
Node* newNode = new Node();
newNode->data = element;
newNode->next = nullptr;

// If the deque is empty, both front and rear are the new node
if (isEmpty()) {
front = rear = newNode;
} else {
27 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Insert the new node at the rear

rear->next = newNode;
rear = newNode;
}
}

// Function to delete from the front of the deque

int deleteFront() {
if (isEmpty()) {
print("Deque Underflow! Cannot delete from front.");
return -1; // Indicate failure
}

// Store the front element to return

int deletedValue = front->data;
Node* temp = front;
front = front->next;

// If the deque becomes empty after deletion, set rear to nullptr

if (front == nullptr) {
rear = nullptr;
}

delete temp; // Free memory of the removed node

return deletedValue;
}

// Function to delete from the rear of the deque

int deleteRear() {
if (isEmpty()) {
print("Deque Underflow! Cannot delete from rear.");
return -1; // Indicate failure
28 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// If there is only one element in the deque

if (front == rear) {
int deletedValue = rear->data;
delete rear;
front = rear = nullptr;
return deletedValue;
}

// Traverse to the second last element

Node* temp = front;
while (temp->next != rear) {
temp = temp->next;
}

// Store the rear element to return

int deletedValue = rear->data;
delete rear;
rear = temp;
rear->next = nullptr;
return deletedValue;
}

// Example usage
void main() {
insertRear(10); // Insert 10 at the rear
insertRear(20); // Insert 20 at the rear
print(deleteFront()); // Output: 10
print(deleteRear()); // Output: 20
}
2.3 Output restricted Queue
29 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

An output-restricted queue is a special case of a double-ended queue where data can be

removed from one end(front) but can be inserted from both ends (front and rear). This kind of
Queue does not follow FIFO (first in first out):

Mainly the following three basic operations are performed on output restricted queue:

 insertRear(): Adds an item at the rear of the queue.

 insertFront(): Adds an item at the front of the queue.

 deleteFront(): Deletes an item from the front of the queue.

In addition to the above operations, the following operations are also supported

 getFront(): Gets the front item from the m queue.

 getRear(): Gets the last item from the m queue.

 isEmpty(): Checks whether the r queue is empty or not.

 isFull(): Checks whether the queue is full or not.

Example: Pseudo C++ Code for Insertion and Deletion in Output Restricted Deque

// Define the structure of a node

struct Node {
int data; // Data part of the node
Node* next; // Pointer to the next node
};

// Define the deque

Node* front = nullptr; // Front of the deque
Node* rear = nullptr; // Rear of the deque
30 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Function to check if the deque is empty

bool isEmpty() {
return front == nullptr;
}

// Function to insert at the front of the deque

void insertFront(int element) {
// Create a new node for the element
Node* newNode = new Node();
newNode->data = element;
newNode->next = front;

// If the deque is empty, both front and rear are the new node
if (isEmpty()) {
front = rear = newNode;
} else {
front = newNode;
}
}

// Function to insert at the rear of the deque

void insertRear(int element) {
// Create a new node for the element
Node* newNode = new Node();
newNode->data = element;
newNode->next = nullptr;

// If the deque is empty, both front and rear are the new node
if (isEmpty()) {
front = rear = newNode;
} else {
31 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

// Insert the new node at the rear

rear->next = newNode;
rear = newNode;
}
}

// Function to delete from the front of the deque

int deleteFront() {
if (isEmpty()) {
print("Deque Underflow! Cannot delete from front.");
return -1; // Indicate failure
}

// Store the front element to return

int deletedValue = front->data;
Node* temp = front;
front = front->next;

// If the deque becomes empty after deletion, set rear to nullptr

if (front == nullptr) {
rear = nullptr;
}

delete temp; // Free memory of the removed node

return deletedValue;
}

// Example usage
void main() {
insertFront(10); // Insert 10 at the front
insertRear(20); // Insert 20 at the rear
print(deleteFront()); // Output: 10
32 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

print(deleteFront()); // Output: 20
}

3. Priority Queue
3.1 Basic concept

A priority queue is a type of queue that arranges elements based on their priority values.
Elements with higher priority values are typically retrieved or removed before elements with
lower priority values. Each element has a priority value associated with it. When we add an
item, it is inserted in a position based on its priority value.

Real Life Application

The hospital emergency queue is an ideal real-life example of a priority queue. In this queue
of patients, the patient with the most critical situation is the first in a queue, and the patient who
doesn’t need immediate medical attention will be the last. In this queue, the priority depends
on the medical condition of the patients.

Representation of priority queue

Now, we will see how to represent the priority queue through a one-way list.

We will create the priority queue by using the list given below in which INFO list contains the
data elements, PRN list contains the priority numbers of each data element available in
the INFO list, and LINK basically contains the address of the next node.
33 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

Let's create the priority queue step by step.

In the case of priority queue, lower priority number is considered the higher priority,
i.e., lower priority number = higher priority.

Step 1: In the list, lower priority number is 1, whose data value is 300, so it will be inserted in
the list as shown in the below diagram:

Step 2: After inserting 300, priority number 2 has a higher priority, and data values associated
with this priority are 100 and 200. So, this data will be inserted based on the FIFO principle;
therefore 200 will be added first and then 100.

Step 3: After inserting the elements of priority 2, the next higher priority number is 4 and data
elements associated with 4 priority numbers are 400, 500, 700. In this case, elements would be
inserted based on the FIFO principle; therefore, 400 will be added first, then 500, and then 700.

Step 4: After inserting the elements of priority 4, the next higher priority number is 5, and the
value associated with priority 5 is 600, so it will be inserted at the end of the queue.

Array implementation of priority queue:

In the Array-based implementation, the queue is represented as an array, and we manage the
insertion and deletion based on the priority of the elements.
34 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

Basic Operations on a Priority Queue:

1. insert(element, priority): Insert an element into the queue with a given

priority.

2. delete(): Remove and return the element with the highest priority.

3. peek(): View the element with the highest priority without removing it.

4. isEmpty(): Check if the priority queue is empty.

5. isFull(): Check if the priority queue is full (in case of a fixed size array).

Example: Pseudo C++ Code for an Array-Based Priority Queue

struct Element {
int data; // Data of the element
int priority; // Priority of the element
};

const int SIZE = 100; // Maximum size of the priority queue

Element pq[SIZE]; // Array representing the priority queue
int rear = -1; // Points to the last element in the queue

// Function to check if the queue is empty

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

// Function to check if the queue is full

bool isFull() {
return rear == SIZE - 1;
}

// Function to insert an element with a given priority

void insert(int element, int priority) {
35 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

if (isFull()) {
print("Queue Overflow! Cannot insert.");
return;
}

rear++;
int i = rear;

// Shift elements with lower priority to make space for the new
element
while (i > 0 && pq[i - 1].priority < priority) {
pq[i] = pq[i - 1];
i--;
}
pq[i].data = element;
pq[i].priority = priority;
}

// Function to delete the element with the highest priority

int deleteElement() {
if (isEmpty()) {
print("Queue Underflow! Cannot delete.");
return -1; // Indicate failure
}

// Element with the highest priority is at the front (index 0)

int removedValue = pq[0].data;

// Shift remaining elements to the left

for (int i = 0; i < rear; i++) {
pq[i] = pq[i + 1];
}
36 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

rear--; // Decrease rear after removal

return removedValue;
}

// Function to peek at the element with the highest priority

int peek() {
if (isEmpty()) {
print("Queue is empty.");
return -1; // Indicate failure
}
return pq[0].data; // Return the element with the highest priority
}

// Main function to demonstrate operations

void main() {
insert(10, 2); // Insert 10 with priority 2
insert(20, 1); // Insert 20 with priority 1
insert(30, 3); // Insert 30 with priority 3

print(peek()); // Output: 30 (highest priority)

print(deleteElement()); // Output: 30 (remove highest priority)
print(peek()); // Output: 10 (next highest priority)
print(deleteElement()); // Output: 10
print(deleteElement()); // Output: 20
print(deleteElement()); // Output: Queue Underflow!
}
37 | P a g e © Haris Chaus | ALL RIGHTS ARE RESERVED as per copyright act.

3.2 Types (Ascending and Descending)

There are two types of priority queue:

1. Ascending order priority queue: In ascending order priority queue, a lower priority number
is given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged
in an ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest
priority in a priority queue.

2. Descending order priority queue: In descending order priority queue, a higher priority
number is given as a higher priority in a priority. For example, we take the numbers from 1 to
5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given
as the highest priority in a priority queue.