DATA STRUCTUREs

QUEUE
 OUTLINES
 Introduction
 Types of Queue data structure
 Linear Queue Operations
 Insertion Operation
 Deletion Operation
 Circular Queue Operations
 Insertion Operation
 Deletion Operation
 Double Ended Queue(Deque)
 Priority Queue
 Applications of Queue
 Question & Answer Discussion

2
QUEUE IN A REAL LIFE

3
INTRODUCTION
 Non-primitive linear data structure
 Ordered collection of homogeneous elements
 A new element is added at one end called rear end and
the existing elements are deleted from the other end
called front end.
 Queue works on the principle of First-In-First-Out
(FIFO),the element that has been added first to the list
will be the element that will be removed first from the
list.

4
MODELS OF QUEUE

5
TYPES:

Linear Queue

Circular Queue

Double-Ended Queue(Deque)

Priority Queue

6
 OPERATIONS ON LINEAR QUEUE

 Insert an element in a Queue

 Delete an element from a Queue

Placing an item in a queue is called

“insertion or enqueue”, which is done
at the end of the queue called “rear”.

Rear Front
7
 Contd...

Removing an item from a queue is

called “deletion or dequeue”, which
is done at the other end of the
queue called “front”.

Rear Front

8
 INSERTION(ENQUEUE) OPERATION

ALGORITHM: Q_INSERT(QUEUE,MAX,FRONT,REAR, ITEM)

Input: QUEUE is the linear array with maximum size
[Link] and REAR are the pointer variables
pointing to Front end and Rear end.
Output: This algorithm inserts an element ITEM on to
the queue QUEUE.

Step 1: If REAR=MAX-1, then

Print “Queue Overflow” and Exit.
Step 2: If FRONT=-1 and REAR=-1,then
Set FRONT=0 and REAR=0
Else
Set REAR=REAR+1
9
 INSERTION(ENQUEUE) OPERATION

Step 3: [Insert an element in to the Queue]

Set QUEUE[REAR]=ITEM
Step 4: Exit

10
INSERTION(ENQUEUE) OPERATION

•Max=5
•Front=-1
•Rear=-1

Q[4] Q[3] Q[2] Q[1] Q[0]

Rear=-1 Front=-1

11
INSERTION(ENQUEUE) OPERATION

Insert 10

Q[4] Q[3] Q[2] Q[1] Q[0]

10

Rear=0 Front=0

12
INSERTION(ENQUEUE) OPERATION

Insert 20

Q[4] Q[3] Q[2] Q[1] Q[0]

20 10

Rear=1 Front=0

13
INSERTION(ENQUEUE) OPERATION

Insert 30

Q[4] Q[3] Q[2] Q[1] Q[0]

30 20 10

Rear=2 Front=0

14
INSERTION(ENQUEUE) OPERATION

Insert 40

Q[4] Q[3] Q[2] Q[1] Q[0]

40 30 20 10

Rear=3 Front=0

15
INSERTION(ENQUEUE) OPERATION

Insert 50

Q[4] Q[3] Q[2] Q[1] Q[0]

50 40 30 20 10

Rear=4 Front=0

16
INSERTION(ENQUEUE) OPERATION

Insert 60

Rear=Max-1 (Rear=4)

Q[4] Q[3] Q[2] Q[1] Q[0]

50 40 30 20 10

Rear=4 Front=0

Queue Overflow 17
Implementation
#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Define maximum size for

the queue

// Global variables for front and rear

int FRONT = -1;
int REAR = -1;

18
 Implementation
// Function to insert an item into the queue // Step 3: Insert the item into the queue
void Q_INSERT(int QUEUE[], int ITEM) { QUEUE[REAR] = ITEM;
// Step 1: Check for queue overflow
if (REAR == MAX - 1) { // Optional: Print the inserted item and
printf("Queue Overflow\n"); current queue state
return; printf("Inserted %d at position %d\n",
} ITEM, REAR);
}
// Step 2: Check if the queue is empty
if (FRONT == -1 && REAR == -1) {
// If empty, set both FRONT and REAR to 0
FRONT = 0;
REAR = 0;
} else {
// Move the rear pointer to the next position
REAR++;
}
19
Implementation
// Function to print the current queue elements
void printQueue(int QUEUE[ ]) {
if (FRONT == -1) {
printf("Queue is empty\n");
return;
}

printf("Queue elements: ");

for (int i = FRONT; i <= REAR; i++) {
printf("%d ", QUEUE[i]);
}
printf("\n");
}

20
Implementation
int main() {
int QUEUE[MAX];

// Insert elements into the queue

Q_INSERT(QUEUE, 10);
Q_INSERT(QUEUE, 20); // Final state of the queue
Q_INSERT(QUEUE, 30); printQueue(QUEUE);

// Print the current queue state return 0;

printQueue(QUEUE); }

// Attempt to insert into a full queue

for (int i = 0; i < MAX - 3; i++) {
Q_INSERT(QUEUE, i + 40);
}

21
 DELETION(DEQUEUE) Operation

ALGORITHM: Q_DELETE(QUEUE,MAX,FRONT,REAR,
ITEM)
Input: QUEUE is the linear array with maximum size
[Link] and REAR are the pointer variables
pointing to Front end and Rear end respectively.
Output: This algorithm deletes an element from the queue
QUEUE and stores it in the variable ITEM.

Step 1: If FRONT=-1 and REAR=-1, then

Print “Queue Underflow” and Exit.
Step 2: [Delete an element from the Queue]
Set ITEM=QUEUE[FRONT]
22
 DELETION(DEQUEUE) Operation

Step 3: If FRONT= REAR , then

Set FRONT=-1 and REAR=-1
Else
Set FRONT=FRONT+1
Step 4: Exit

23
DELETION(DEQUEUE) Operation

Delete

Q[4] Q[3] Q[2] Q[1] Q[0]

50 40 30 20 10

Rear=4 Front=0

Deleted Element=10
24
DELETION(DEQUEUE) Operation

Delete

Q[4] Q[3] Q[2] Q[1] Q[0]

50 40 30 20

Rear=4 Front=1

Deleted Element=20
25
DELETION(DEQUEUE) Operation

Delete

Q[4] Q[3] Q[2] Q[1] Q[0]

50 40 30

Rear=4 Front=2

Deleted Element=30
26
DELETION(DEQUEUE) Operation

Delete

Q[4] Q[3] Q[2] Q[1] Q[0]

50 40

Rear=4 Front=3

Deleted Element=40
27
DELETION(DEQUEUE) Operation

Delete

Q[4] Q[3] Q[2] Q[1] Q[0]

50

Rear=4 Front=4

Deleted Element=50
28
DELETION(DEQUEUE) Operation

Delete

Q[4] Q[3] Q[2] Q[1] Q[0]

Rear=-1 Front=-1

29
DELETION(DEQUEUE) Operation

Delete

Front=-1 and Rear=-1

Q[4] Q[3] Q[2] Q[1] Q[0]

Rear=-1 Front=-1

Queue Underflow 30
Implementation

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

#define MAX 100 // Define maximum size for the queue

// Global variables for front and rear

int FRONT = -1;
int REAR = -1;

31
 Implementation
// Step 3: Check if the queue becomes empty
after deletion
// Function to delete an item from the queue
if (FRONT == REAR) {
int Q_DELETE(int QUEUE[]) {
// If the queue becomes empty, reset
// Step 1: Check for queue underflow
FRONT and REAR
if (FRONT == -1 && REAR == -1) {
FRONT = -1;
printf("Queue Underflow\n");
REAR = -1;
return -1; // Indicate that no item was
} else {
deleted
// Move the front pointer to the next
}
position
FRONT++;
// Step 2: Delete an element from the queue
}
int ITEM = QUEUE[FRONT];
// Optional: Print the deleted item
printf("Deleted %d from position %d\n",
ITEM, FRONT);
return ITEM; // Return the deleted item
}
32
Implementation
// Function to print the current queue elements
void printQueue(int QUEUE[]) {
if (FRONT == -1) {
printf("Queue is empty\n");
return;
}

printf("Queue elements: ");

for (int i = FRONT; i <= REAR; i++) {
printf("%d ", QUEUE[i]);
}
printf("\n");
}

33
Implementation
// Delete an item from the queue
// Example usage
int deletedItem = Q_DELETE(QUEUE);
int main() {
if (deletedItem != -1) {
int QUEUE[MAX];
printf("Deleted item: %d\n", deletedItem);
}
// Insert elements into the queue
Q_INSERT(QUEUE, 10);
// Print the current queue state after deletion
Q_INSERT(QUEUE, 20);
printQueue(QUEUE);
Q_INSERT(QUEUE, 30);
// Final delete to show underflow
// Print the current queue state
deletedItem = Q_DELETE(QUEUE);
printQueue(QUEUE);
deletedItem = Q_DELETE(QUEUE);
deletedItem = Q_DELETE(QUEUE); // This
should trigger underflow

return 0;
}
34
Implementation of Queue using
Linked List

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

// Define the structure of a node

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

// Front and Rear pointers to keep track of the queue

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

36
Implementation
// Enqueue function to add an element to the queue
void enqueue(int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Heap Overflow\n");
return;
}
newNode->data = value; // Set the value
newNode->next = NULL; // Since it's the last node, next is NULL

// If the queue is empty, both front and rear will point to the new node
if (front == NULL) {
front = rear = newNode;
} else {
rear->next = newNode; // Link the new node at the end of the queue
rear = newNode; // Make the new node the rear node
}
printf("Enqueued %d into the queue\n", value);
}
Implementation
// Dequeue function to remove an element from the queue
int dequeue() {
if (front == NULL) {
printf("Queue Underflow\n");
return -1; // Return -1 if the queue is empty
}
int dequeuedValue = front->data; // Get the data of the front node
struct Node* temp = front; // Temporarily store the front node
front = front->next; // Move the front to the next node

// If the queue becomes empty after dequeuing, set rear to NULL

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

free(temp); // Free the memory of the dequeued node

printf("Dequeued %d from the queue\n", dequeuedValue);
return dequeuedValue;
}
Implementation

// Peek function to return the front element of the queue

int peek() {
if (front == NULL) {
printf("Queue is empty\n");
return -1; // Return -1 if the queue is empty
}
return front->data; // Return the data of the front node
}
Implementation

void printQueue() {
if (front == NULL) {
printf("Queue is empty\n");
return;
}

struct Node* temp = front;

printf("Queue elements are: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
Implementation

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printQueue(); // Print all elements in the queue
printf("Front element is %d\n", peek());
dequeue();
printQueue(); // Print the queue after one dequeue operation
dequeue();
printQueue(); // Print the queue after another dequeue operation
printf("Front element after dequeuing is %d\n", peek());
return 0;
}
Circular Queue
Circular Queue is just a variation of the linear queue in
which front and rear-end are connected to each other
to optimize the space wastage of the Linear queue
and make it efficient.

42
Circular Queue
• As the insertion in the queue is from the rear end
and in the case of Linear Queue of fixed size
insertion is not possible when rear reaches the end
of the queue.

• But in the case of Circular Queue, the rear end

moves from the last position to the front position
circularly.

43
OPERATION ON CIRCULAR QUEUE

 Insertion into a Circular Queue

 Deletion from a Circular Queue

44
 INSERTION (ENQUEUE) OPERATION

ALGORITHM: C_Q_INSERT(C_QUEUE,MAX,FRONT,REAR,
ITEM)
Input: C_QUEUE is the Circular Queue with maximum size
[Link] and REAR are the pointer variables
pointing to Front end and Rear end respectively.
Output: This algorithm inserts an element ITEM on to
the circular queue C_QUEUE.

Step 1: If FRONT=(REAR+1)%MAX , then

Print “Circular Queue Overflow” and Exit.
Step 2: If FRONT=-1 and REAR=-1,then
Set FRONT=0 and REAR=0
Else
Set REAR=(REAR+1) % MAX
45
 INSERTION(ENQUEUE) OPERATION

Step 3: [Insert an element in to the Queue]

Set C_QUEUE[REAR]=ITEM
Step 4: Exit

46
INSERTION(ENQUEUE) OPERATION

C_Queue

7 0 rear = -1 front = -1

6 1

5 2

4 3

47
INSERTION(ENQUEUE) OPERATION

rear = 0
C_Queue
Insert 10 front = 0
7 0

10
6 1

5 2

4 3

48
INSERTION(ENQUEUE) OPERATION

C_Queue
Insert 20 front = 0
7 0
rear = 1
10
6 1
20

5 2

4 3

49
INSERTION(ENQUEUE) OPERATION

C_Queue
Insert 30 front = 0
7 0

10
6 1
20

30
5 2
rear = 2

4 3

50
INSERTION(ENQUEUE) OPERATION

C_Queue
Insert 40 front = 0
7 0

10
6 1
20

30
5 2
40

4 3

rear = 3

51
INSERTION(ENQUEUE) OPERATION

C_Queue
Insert 50 front = 0
7 0

10
6 1
20

30
5 2
50 40

4 3

rear = 4

52
INSERTION(ENQUEUE) OPERATION

C_Queue
Insert 60 front = 0
7 0

10
6 1
20

60 30
5 2
50 40
rear = 5
4 3

53
INSERTION(ENQUEUE) OPERATION

C_Queue
Insert 70 front = 0
7 0

10
rear = 6 6 1
70 20

60 30
5 2
50 40

4 3

54
INSERTION(ENQUEUE) OPERATION

rear = 7
C_Queue
Insert 80 front = 0
7 0

80 10
6 1
70 20

60 30
5 2
50 40

4 3

55
INSERTION(ENQUEUE) OPERATION

rear = 7
C_Queue
Insert 90 front = 0
7 0
Front =(rear+1)%max
80 10
6 1
70 20

60 30
5 2
50 40

4 3

Queue Overflow

56
 DELETION(DEQUEUE) Operation

ALGORITHM:
C_Q_DELETE(C_QUEUE,MAX,FRONT,REAR, ITEM)
Input: C_QUEUE is the Circular Queue with maximum size
MAX. FRONT and REAR are the pointer variables
pointing to Front end and Rear end respectively.
Output: This algorithm deletes an element from the Circular
Queue C_QUEUE and stores it in the variable ITEM.

Step 1: If FRONT=-1 and REAR=-1, then

Print “Circular Queue Underflow” and Exit.
Step 2: [Delete an element from the Queue]
Set ITEM=C_QUEUE[FRONT]

57
 DELETION(DEQUEUE) Operation

Step 3: If FRONT= REAR , then

Set FRONT=-1 and REAR=-1
Else
Set FRONT=(FRONT+1)%MAX
Step 4: Exit

58
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
front = 0
7 0

80 10
6 1
70 20

60 30
5 2
50 40

4 3

59
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete front = 0
7 0

80 10
6 1
70 20

60 30
5 2
50 40

4 3

Deleted Element =10

60
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete
7 0

80
6 1
front = 1
70 20

60 30
5 2
50 40

4 3

Deleted Element =20

61
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete
7 0

80
6 1
70

60 30
5 2 front = 2
50 40

4 3

Deleted Element =30

62
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete
7 0

80
6 1
70

60
5 2
50 40

4 3

front = 3

Deleted Element =40

63
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete
7 0

80
6 1
70

60
5 2
50

4 3

front = 4

Deleted Element =50

64
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete
7 0

80
6 1
70

60
5 2

front = 5
4 3

Deleted Element =60

65
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete
7 0

front = 6
80
6 1
70

5 2

4 3

Deleted Element =70

66
DELETION(DEQUEUE) Operation

rear = 7
C_Queue
Delete front = 7
7 0

80
6 1

5 2

4 3

Deleted Element =80

67
DELETION(DEQUEUE) Operation

C_Queue
Delete
7 0 rear = -1 front = -1

Front=-1 and rear=-1

6 1

5 2

4 3

Queue Underflow

68
Example: Consider the following circular queue with N = 8.
1. Initially, Rear = -1, Front =- 1 4. Insert 20, Rear = 2, Front = 0.
7 0 rear = -1 front = -1 front
7 0
6 1 10
6 50 1
5 2 20
5 2 Rear
4 3
4 3
2. Insert 10, Rear = 0, Front = 0 5. Insert 70, Rear = 3, Front = 0
front front
7 0 rear 7 0
10 10
6 1 6 50 1
20
5 2 5 70 2

4 3 4 3 Rear
3. Insert 50, Rear = 1, Front = 0 6. Delete , Rear = 3, Front = 1
7 0
front 6 50 1 front
7 0
20
10
6 50 1 rear 5 70 2

4 3
5 2 Rear

69 4 3
69
7. Insert 35, Rear = 4, Front =1 10. Insert 20, Rear = 7, Front = 1
7 0 Rear
7 0
6 50 1 front
20 front
6 30 50 1
20
5 35 70 2 40 20
5 35 70 2
4 3
Rear
4 3
8. Insert 40, Rear = 5, Front = 1 11. Insert 25,Rear=0,Front=1
Rear
7 0 7 0
20 25
6 50 1 front 6 30 50 1 front
40 20 40 20
Rear 5 35 70 2 5 35 70 2

4 3 4 3
9. Insert 30, Rear = 6, Front = 1 12. Delete , Rear =Rear
0, Front = 2.
7 0
20 25
6 30 1
7 0
40 20
rear 6 30 1 front 5 35 70 2 front
50
40 20 4 3
5 35 70
2

70 4 3
70
DOUBLE ENDED QUEUE(DEQUE)

 Linear list of elements in which insertion and

deletion operations are performed on both ends.
 Inserting an element from both front end rear
end.
 Deleting an element from both the front and rear
end

Insertion Deletion

10 20 30 40 50 60
Deletion Insertion

71 Front Rear
DOUBLE ENDED QUEUE(DEQUE)

 Input Restricted Deque

 Allows insertion at only one end(rear) of the list

 Allows deletion at the both front and rear ends

 Output Restricted Deque

 Allows deletion at only one end(front) of the list

 Allows insertion at the both front and rear ends

72
DOUBLE ENDED QUEUE(DEQUE)

As STACK
 When insertion and deletion is made at the same side.

As Queue

 When items are inserted at one end and removed at the other
end.

73
Uses of Queue
 Simulation of Traffic Control System
 Implementation of CPU Scheduling Algorithms
 Round Robin Scheduling Algorithm
 Multilevel Queue Scheduling Algorithm
 Multilevel Feedback Queue Scheduling Algorithm
 Areas of Customer Services(Railway Reservation)
 Memory Management
 Trees traversing

74
 Priority Queue

 Items are inserted according to priority

 Priority determines the order in which items exists in the
queue
 Simple example is mail sorting, process control systems
 Ascending Priority Queue ( queue which remove lowest
priority item first)
 Descending priority Queue (queue which remove highest
priority item first)
 Implementation is like multiple stack i.e more than one
queues can exist on a single one-dimensional array

75
Priority Queue

 Ascending Priority Queue

 Collection of elements in to which elements can be
inserted arbitrarily and from which only the smallest
element can be removed from the list
 Descending Priority Queue
 Collection of elements in to which elements can be
inserted arbitrarily and from which only the largest
element can be removed from the list

76
 Questions

1. Which data structure allows deleting data elements from

front and inserting at rear?
a. Stack
b. Queue
c. Deque
d. Binary search tree

b)Queue

77
 Questions

[Link] the data structure which allows deletions at both ends

of the list but insertion at only one end.

a. Input-restricted deque
b. Output-restricted deque
c. Priority queues
d. None of above

a)Input-restricted Deque

78
 Questions

3. A .................... is a linear list in which insertions and deletions are made

to from either end of the structure.

a) Circular Queue
b) Random Queue
c) Priority Queue
d) Deque

d)Deque

79
 Questions

4. Which of the following data structure is linear type?

a. Strings
b. Lists
c. Queues
[Link] of above

d)All of the above

80