CHAPTER 5.

QUEUES
5.1 Introduction
5.2 Representation - Static & Dynamic
5.3 Primitive Operations on Queue
5.4 Circular queue, priority queue
5.5 Concept of doubly ended queue

INTRODUCTION :

⮚ Queue is similar to the queue which is usually seen in our day today life like a queue of
people on a railway station.
⮚ Queues are also used in computers for maintaining job queue.
In multiprogramming system there are many jobs present in the system. These jobs are
to be allocated to the CPU one at a time only on context-switching basis. How should the operating
system decide as to which job should get the CPU turn? For doing this jobs job pool is maintained
in the form of queue. The queue can be maintained according to first come first serve basis or
according to the priority i.e jobs with highest priority is first in the queue and job with lowest
priority is last in queue. The job is dispatched from the front of queue and given to the CPU and
whenever a new job arrives it is placed at the rear of the queue.

⮚ DEFINITION :
A queue is an ordered collection of items from which items may be deleted from (or
removed from ) one end called the front and into which items may be inserted at the other end
called rear.
⮚ The elements are added and deleted in FIFO ( first in first out) manner

⮚ Example : The 3 elements A,B,C are added to queue. C is at the rear.

-1
A B C

Front rear

A new element D will be added at the rear.

A B C D
-1

Front rear
An element can be deleted only from the front. Thus A will be the front to be removed.
B C D

Front rear

⮚ DIFFERENCE BETWEEN STACK AND QUEUE.

 Stack Queue
It is a LIFO structure. It is a FIFO structure.
A stack is open at one end called the top. A queue is open at two ends front and rear.

Elements are added and removed from the Elements are added and removed from
same end. different ends.
The basic operations are PUSH and POP The basic operations are ADD and
DELETE.
Top moves in both directions. Hence vacant Front and rear move in one direction only.
positions are reused.
No concept of circular stack The concept of a circular queue exists.
We cannot have a priority stack We have a priority queue.

⮚ BASIC OPERATIONS ON QUEUE

1) Create:
Creates a new queue. This operation creates an empty queue.
2) Add or insert:
Adds an element to the queue. A new element can be added to the queue at
the rear.
3) Delete:
Remove an element from the queue. This operation removes the elements,
which is at the front of the queue. This operation can only be performed if the queue is
not empty.
The result of an illegal attempt to remove an element from an empty queue
is called underflow.
4) Isempty:
Checks whether a queue is empty. The operation return true if the queue
isempty and false otherwise
5) isfull

⮚ TYPES OF QUEUE
1) linear:
In this queue the elements are arranged into a sequential manner, Such that
front position is always less than or equal to the rear position. When an element is
added, rear is incremented and when an element is removed front is advanced. Thus
front always follows rear.
Example:
A B
-1 C
Front rear
2) Circular queue:
In this queue, the elements are arranged in a sequential manner but can logically be
regarded as circularly arranged
C D
B

A
Example: (rear)
CC

Empty position
(front)

⮚ REPRESENTATION OF LINEAR QUEUES.

There are two ways to represent a queue in memory.

1) Static (using an array)
2) Dynamic (using an linked list)
1) Static implementation of queue
Static implementation or array representation of queue requires three
entities-
- An array to hold queue elements.
- A variable to hold the index of the front element.
- A variable to hold the index of the rear element.

The implementation of a queue using sequential representation is done by using

some size MAX and two integer variable front and rear. Initially front and rear is
set to -1. Whenever new element is added it is added from the rear and whenever an
element is to be removed from the front. The queue full condition is when rear
reaches to MAX - 1. Queue empty condition is when front is equal to rear.

#include<stdio.h>
#define MAX 5
//create the queue
Struct queue
{
int Q[MAX];
int front,rear;
};
typedef struct queue QUEUE;

//Initialiaing the queue

void initqueue(QUEUE *q)
{
int i;
for(i=0;i<MAX;i++)
q->Q[i]=0;
 q->front=-1;
q->rear=-1;
}

//checking for an empty queue

A queue will be empty when both front and rear are at the same position.
int isempty(QUEUE *q)
{
if(q->front==q->rear)
return 1;
else
return 0;
}

//checking for a full queue

As we insert elements into the queue, rear gets incremented. At some stage, it will reach
the array limit i.e. MAX-1 after which no more elements can be added.
int isfull(QUEUE *q)
{
if(q->rear==MAX-1)
return 1;
else
return 0;
}
//adding an element to the queue
A new element is added at the rear end of the queue. Since we have initialized rear to -1 the
first element should be put at position 0. Thus rear should be first incremented and the
element should be stored at that position.
void addQ(int val, QUEUE *q)
{
q->Q[++q->rear]=val;
}
//deleted an element from the queue
An element has to be deleted from front. Front has to be first incremented (since it
has been initialized to -1 and then the element at that position has to be returned)
int delete(QUEUE *q)
{
int val;
++q->front;
val=q->Q[q->front];
return val;
‘or’
return(q->Q[++q->front]);
}
//Peek – it Shows the front element of the queue
int peek(QUEUE *q)
{
return(q->Q[q->front+1]);
}

//display the elements of queue

void display(QUEUE *q)
{
int i;
for(i=q->front+1;i<=q->rear;i++)
printf(“%4d”,q->Q[i]);
}
main()
{
int ch,val;
QUEUE q;
initqueue(&q);
while(1)
{
printf(“Main menu”);
printf(“\n 1 : Add queue”);
printf(“\n 2 : Delete queue”);
printf(“\n 3 : Display queue”);
printf(“\n 4 : Exit”);
printf(“\n Enter your choice”);
scanf(“%d”, &ch);
switch(ch)
{
case 1 :
if(isfull(&q))
printf(“\n Queue is full”);
else
{
printf(“\n Enter value”);
scanf(“%d”,&val);
addQ(val,&q);
}
break;
case 2 :
if(isempty(&q))
printf(“\n Queue is empty”);
else
printf(“\n Deleted elements = %d”,deleteQ(&q));
break;
case 3 :
if(isempty(&q))
printf(“\n Queue is empty”);
else
display(&q);
break;
case 4 : exit(0);
}
}
}

2) Dynamic implementation of linear queue (using an linked list)

 A queue can be considered as a list in which all insertions are made at one
end called the rear and all deletions from the other end from front.
A queue can be easily represented using a linked list. The front and rear will be two
pointers pointing to the first and last node respectively.
//program to implement dynamic queue
#include<stdio.h>
#include<stdlib.h>
struct queue
{
int data;
struct queue *next;
};

typedef struct queue QUEUE;

void addq(int data);

int deleteq();
void displayq();
QUEUE *alloc(int);
int isemptyq();
QUEUE *findlast();

QUEUE *front=NULL,*rear=NULL;

main()
{
int ch,data;
while(1)
{
printf("\n \t 1 : Add");
printf("\n \t 2 : Delete");
printf("\n \t 3 : Peek");
printf("\n \t 4 : Display");
printf("\n \t 5 : Exit");
printf("\n \t Enter UR choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1 :
printf("\nEnter the data to be added-> ");
scanf("%d",&data);

addq(data);

break;
case 2:
if(isemptyq())
printf("\nqueue is empty");
else
printf("\ndeleted data is %d",deleteq());
break;
 case 3:
if(isemptyq())
printf("\nqueue is empty");
else
printf("\nFront element is %d",peek());
break;
case 4:
if(isemptyq())
printf("\nqueue is empty");
else
displayq();
break;

case 5:
exit(1);
}
}
}
int isemptyq()
{
if (front==NULL)
return 1;
else
return 0;
}

int peek()
{
return(front->data);
}

void addq(int data)

{
QUEUE *ptr=NULL,*temp=NULL;
temp=alloc(data);
if(front==NULL)
{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=temp;
}
}

int deleteq()
{
QUEUE *ptr1,*ptr=NULL;
int val;
 ptr=front;
val=ptr->data;
if(front->next!=NULL)
{
front=front->next;

}
else
{
front=NULL;
rear=NULL;
}
free(ptr);
return(val);
}

void displayq()
{
QUEUE *ptr;
printf("\n \t Ur Queue Lokks Like...\n ");
for(ptr=front;ptr->next!=NULL;ptr=ptr->next)
{
printf("%d-> ",ptr->data);

}
printf("%d",ptr->data);
}

QUEUE *alloc(int data)

{
QUEUE *temp;
temp=(QUEUE *)malloc(sizeof(QUEUE));
temp->data=data;
temp->next=NULL;
return(temp);
}

/*

1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 1

Enter the data to be added-> 1

1 : Add
2 : Delete
 3 : Peek
4 : Display
5 : Exit
Enter UR choice : 1

Enter the data to be added-> 2

1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 1

Enter the data to be added-> 3

1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 4

Ur Queue Lokks Like...

1-> 2-> 3
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 3

Front element is 1
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 4

Ur Queue Lokks Like...

1-> 2-> 3
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2

deleted data is 1
1 : Add
 2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2

deleted data is 2
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2

deleted data is 3
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2

queue is empty
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 3

queue is empty
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 4

queue is empty
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 5

*/

● Applications of queue:
1) Various features of operating system are implemented using a queue
 - Scheduling of processes (round robin algorithm)
- Spooling (to maintain a queue of jobs to be printed)
- A queue of client process waiting to receive the service from the server process.
2) Queues are used in simulation.
E.g. In airport simulation, to keep the track of problems like number of plane
processed, the average time spent waiting etc. queue are used.
3) Multiple print jobs given to a printer are organized in the FIFO number in a print
queue and given to the printer.
4) In batch programming multiple jobs are combined into a batch and the first program is
executed next and so on in a sequential manner.

● Circular queue
Disadvantage of linear queue
Consider queue with maximum size 5. Initially the queue is empty i.e. front and rear
are at -1. After the elements ABCD and E are added, the queue will look like

-1 A B C D E
C
Front rear
If we remove two elements from the queue

C D E
C
Front rear
We have two vacant positions at the beginning of the queue but we cannot add new elements
there since rear has reached MAX-1. Which is the queue full condition? Thus even if elements are
removed from the queue, new elements cannot take their positions.

The simple solution to the above problem is that whenever rear gets to the end of the array, it
wrapped around to the beginning. Now array can be thought of as a circle. The first position
follows the last element.

A B C D E
C
Next of A is E

Assume that the queue contains three elements as previous

C D E
C
Front rear
Now we can insert element at the beginning by bringing rear to the first position in the queue.

F C D E
C
Rear front
A peculiar situation arises when the queue is full.
In the above example if another element G is added to the queue, it will look like:

F G C D E
C
Rear , front
i.e. rear and front coincide. But rear and front coincide even when queue is empty. Hence there is
an ambiguity. Rear==front cannot be used for both i.e. to check for an empty queue as well as the
condition for a full queue. Hence some method of resolving this problem is needed. We shall keep
the rear==front condition as a check for an empty queue since initially both are initialized to the
same value. Thus we need another method to check for a full queue.

There are 3 possible solutions:-

1) use a counter to keep track of the number of elements in the queue. If this counter reaches MAX,
the queue is full.
2) Allow only MAX-1 values to be put in the queue i.e use one less element of queue. Thus the queue
full condition will occur when (rear+1)%MAX==front
3) The values of front and rear could be set to same values that are not valid array indices to
indicate an empty condition. i.e. if rear becomes equal to front after a remove operation it indicates
queue empty and hence they could be reset to -1 and (rear==-1) and (front==-1) will be the
conditions for queue empty. If rear becomes equal to front after an add operation it implies queue
is full. Then the condition for full will arise when rear and front coincide but are not -1.
Static Implementation of Circular queue
//ass5 setB (a) program to implement static circular queue
#define MAX 5
struct queue
{
int front,rear;
int Q[MAX];
};
typedef struct queue QUEUE;
int newrear;
void initqueue(QUEUE *q)
{
int i;
for(i=0;i<MAX;i++)
q->Q[i]=0;
q->rear=-1;
q->front=-1;
printf("\nQueue created");
}

int isemptyq(QUEUE *q)

{
if (q->rear==-1)
return 1;
else
return 0;
}

int isfullq(QUEUE *q)

{
newrear=(q->rear+1)%(MAX);
if (q->front==newrear)
return(1);
else
return(0);
}
void addq(QUEUE *q,int data)
{

if(q->rear==-1)
{
q->rear=q->front=0;
q->Q[q->rear]=data;
}
else
{
q->rear=(q->rear+1)%MAX;
q->Q[q->rear]=data;
}
}

int deleteq(QUEUE *q)

{
int data;
data=q->Q[q->front];
if(q->rear==q->front)
{
q->rear=-1;
q->front=-1;
}
else
q->front=(q->front+1)%MAX;
return(data);

void displayq(QUEUE *q)

{
int i;

for(i=q->front;i!=q->rear;i=(i+1)%MAX)
printf("%d\t",q->Q[i]);

printf("%d\t",q->Q[i]);
}
#include<stdio.h>
#include<stdlib.h>
#include"stcqueue.h"
main()
{
 QUEUE q;
int ch,data;
initqueue(&q);
while(1)
{
printf("\n\nMain Menu");
printf("\n1 : ADD");
printf("\n2 : DELETE");
printf("\n3 : DISPLAY");
printf("\n4 : EXIT");
printf("\nEnter the choice=> ");
scanf("%d",&ch);
switch(ch)
{
case 1:

if (isfullq(&q))
printf("\nqueue is full");
else
{
printf("\nEnter the data to be added-> ");
scanf("%d",&data);

addq(&q,data);
}
break;
case 2:
if(isemptyq(&q))
printf("\nqueue is empty");
else
printf("\ndeleted data is %d",deleteq(&q));
break;
case 3:
if(isemptyq(&q))
printf("\nqueue is empty");
else
displayq(&q);
break;
case 4:
exit(1);
}
}
}

Queue created

Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 1
Enter the data to be added-> 12
Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 1
Enter the data to be added-> 2
Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 1
Enter the data to be added-> 14
Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 3
12 2 14

Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 2
deleted data is 12

Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 2
deleted data is 2

Main Menu
1 : ADD
2 : DELETE
3 : DISPLAY
4 : EXIT
Enter the choice=> 2
deleted data is 14

Main Menu
1 : ADD
2 : DELETE
 3 : DISPLAY
4 : EXIT
Enter the choice=> 3
queue is empty

Data Structures:

1. The code defines a constant MAX with a value of 5, which represents the maximum size of the
queue.
2. It defines a struct named queue with members front, rear, and an array Q to store the elements
in the queue.
3. A typedef statement creates an alias QUEUE for the struct queue.

Global Variables:

● There's a global variable newrear, which is used to check if the queue is full.

Queue Initialization:

● The initqueue function initializes the queue. It sets all elements of the Q array to 0, and both the
front and rear are set to -1, indicating an empty queue. It also prints "Queue created."

Queue Operations:

● isemptyq checks if the queue is empty by verifying if the rear is -1.

● isfullq checks if the queue is full by calculating a new value for rear and comparing it to front.
● addq is used to add an element to the queue. It handles both the case when the queue is empty
and when it's not.
● deleteq removes an element from the queue and returns it. If the queue becomes empty after the
deletion, both front and rear are set to -1.
● displayq function is used to display the elements of the queue.

Main Function:

● In the main function, an instance of the QUEUE struct is created, and it is initialized using
initqueue.
● The main menu is displayed in a loop, and the user can choose from four options:

● Option 1 (ADD): Calls addq to add an element to the queue if it's not full.
 ● Option 2 (DELETE): Calls deleteq to remove and display an element from the queue if
it's not empty.
● Option 3 (DISPLAY): Calls displayq to display the elements in the queue if it's not
empty.
● Option 4 (EXIT): Exits the program.
Dry & Run
1. initqueue function is called, and it prints "Queue created."
2. The program enters a menu loop where you can choose options.
3. You choose option 1 (ADD) and input the value 12. The addq function adds 12 to the queue.
4. You choose option 1 (ADD) again and input the value 2. The addq function adds 2 to the queue.
5. You choose option 1 (ADD) once more and input the value 14. The addq function adds 14 to the
queue.
6. You choose option 3 (DISPLAY), and the displayq function prints the contents of the queue:
"12 2 14."
7. You choose option 2 (DELETE), and the deleteq function removes and prints "12" from the
queue.
8. You choose option 2 (DELETE) again, and the deleteq function removes and prints "2" from the
queue.
9. You choose option 2 (DELETE) one more time, and the deleteq function removes and prints
"14" from the queue.
10. You choose option 3 (DISPLAY) again, and the displayq function shows that the queue is
empty, as it prints "queue is empty."
11. The menu loop continues, allowing you to perform more operations.

It appears that the code is working correctly, managing the queue, adding, deleting, and
displaying elements while checking for empty and full conditions.

Dynamic Implementation of Circular queue

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

typedef struct queue QUEUE;

QUEUE *rear=NULL,*front=NULL;
int isemptyq()
{
if (front==NULL)
return 1;
else
return 0;
}
QUEUE *alloc(int data)
{
 QUEUE *temp;
temp=(QUEUE *)malloc(sizeof(QUEUE));
temp->data=data;
temp->next=NULL;
return(temp);
}

int peek()
{
return(front->data);
}

void addq(int data)

{
QUEUE *ptr=NULL,*temp=NULL;
temp=alloc(data);
if(front==NULL)
{
front=temp;
rear=temp;
rear->next=front;
}
else
{
rear->next=temp;
rear=temp;
rear->next=front;
}
}

int deleteq()
{
QUEUE *ptr1,*ptr=NULL;
int val;
ptr=front;
val=ptr->data;
if(front->next!=front)
{
front=front->next;
rear->next=front;
}
else
{
front=NULL;
rear=NULL;
}
free(ptr);
return(val);
}
void displayq()
{
QUEUE *ptr;
printf("\n \t Ur Queue Lokks Like...\n ");
for(ptr=front;ptr->next!=front;ptr=ptr->next)
{
printf("%d-> ",ptr->data);

}
printf("%d",ptr->data);
}

// dynamic circular queue dycqueue.c

#include<stdio.h>
#include<stdlib.h>
#include"dycqueue.h"
main()
{
int ch,data;
while(1)
{
printf("\n \t 1 : Add");
printf("\n \t 2 : Delete");
printf("\n \t 3 : Peek");
printf("\n \t 4 : Display");
printf("\n \t 5 : Exit");
printf("\n \t Enter UR choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1 :
printf("\nEnter the data to be addded: ");
scanf("%d",&data);
addq(data);
break;
case 2:
if(isemptyq())
printf("\nqueue is empty");
else
printf("\ndeleted data is %d",deleteq());
break;
case 3:
if(isemptyq())
printf("\nqueue is empty");
else
printf("\nFront element is %d",peek());
break;
case 4:
if(isemptyq())
printf("\nqueue is empty");
 else
displayq();
break;

case 5:
exit(1);
}
}
}
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 1
Enter the data to be addded: 6
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 1
Enter the data to be addded: 9
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice :
1
Enter the data to be addded: 5
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 4
Ur Queue Lokks Like...
6-> 9-> 5
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 3
Front element is 6
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
 Enter UR choice : 2
deleted data is 6
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2
deleted data is 9
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2
deleted data is 5
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice : 2
queue is empty
1 : Add
2 : Delete
3 : Peek
4 : Display
5 : Exit
Enter UR choice :
The provided C code implements a dynamic circular queue using a linked list data structure. This
code allows you to add elements to the queue, delete elements from the queue, peek at the front
element, display the queue, and exit the program.

Here's a breakdown of the code and a dry run based on your input:

Data Structures:

● The code defines a structure named queue with two members: data to store the data and next to
point to the next element in the queue.

Global Variables:

● Two global pointers, rear and front, are initialized as NULL. These pointers are used to keep
track of the rear and front of the circular queue.

Queue Operations:
● isemptyq checks if the queue is empty by checking if front is NULL.
● alloc allocates memory for a new element in the queue and initializes it with the given data.
● peek returns the data stored in the front element of the queue.
● addq adds an element to the queue by allocating memory for it and updating front and rear
pointers accordingly. It handles both empty and non-empty queue cases.
● deleteq removes the front element from the queue and returns its data. It also updates front and
rear pointers accordingly. It handles both single-element and multiple-element cases.
● displayq displays the elements of the queue from front to rear.

Main Function:

● The main function contains a menu-driven loop allowing the user to perform queue operations.
● You can add elements to the queue (Option 1), delete elements (Option 2), peek at the front
element (Option 3), display the queue (Option 4), or exit the program (Option 5).

Dry Run:

1. You choose option 1 (Add) and add the value 6 to the queue.
2. You choose option 1 (Add) again and add the value 9 to the queue.
3. You choose option 1 (Add) once more and add the value 5 to the queue.
4. You choose option 4 (Display), and the queue is displayed: "6 -> 9 -> 5."
5. You choose option 3 (Peek), and it displays "Front element is 6."
6. You choose option 2 (Delete), and it deletes the front element (6) and displays it.
7. You choose option 2 (Delete) again, and it deletes the front element (9) and displays it.
8. You choose option 2 (Delete) one more time, and it deletes the last element (5) and displays it.
9. You choose option 2 (Delete) again, and it informs you that the queue is empty.
10. You can continue to perform more operations or exit the program.

The code appears to work as expected, correctly managing the dynamic circular queue and
handling various queue conditions.

● ADVANTAGES OF CIRCULAR QUEUE

1) It avoids shifting of queue elements.
2) If the number of elements to be stored in queue is fixed i.e.
if queue size is fix, circular queue is advantageous.
3) Circular queue are used in many applications such as printer queue, priority queue and
simulation.

PRIORITY QUEUE:
It is an ordered list of homogeneous elements. In normal queue Service is provided on first in first
out. In Priority queue service is not provided on the basis of FIFO rather than each element has a
priority based on the urgency of need.
 ● An element with higher priority is processed before other elements with lower priority.

● Elements with the same priority are processed on FIFO basis

Eg Hospital waiting room .A patient having a more fatal problem will be admitted before other
patients.

Implementation of Priority Queue

Priority Queue can be implemented using
� linked List

� Circular array

As the services must be provided to an element having highest priority, there could be a choice
between
a) List is always maintained sorted on priority of elements with the highest priority element at
the front. Here deletion is trivial but insertion is complicated as the elements must be
inserted at the correct place depending on its priority.
b) List is maintained in the FIFO form but the service is provided by selecting the element
with highest priority. Deletion is difficult as the entire queue must be traversed to locate the
element with highest priority. Here insertion is trivial

● DEQUEUE:-

⮚ The word dequeue is a short form of double ended queue.

⮚ It is general representation of both stack and queue and can be used as stack and queue

⮚ A dequeue is a linear list in which insertion as well as deletion can be carried out either at
the rear and or at the front end, but not in the middle.
⮚ In practice , it becomes necessary to fix the type of operation to be performed on front and
rear end.
⮚ The two ends are called left and right respectively. thus four possible operations on a
dequeue.
1) Insert left
2) Insert right
3) Delete left
4) Delete right

● Types of Dequeue
a) Input restricted Dequeue:-
It is a queue which allows insertion at one end of the list but allows deletion at both ends of
the lists.
i.e. The following operations are possible:-
- Insertion of an element at the rear.
- Deletion of an element from front.
- Deletion of an element from rear.
 b) Output restricted dequeue:-
It is a Dequeue which allows deletion at one end of the list, but allows insertion at both ends
of the list.
i.e. The following operations are possible in an output restricted dequeue.
- Deletion of an element from front end
- Insertion of an element at the rear.
- Insertion of an element at the front.

● Operations associated with dequeue:-

1) Empty() : to check whether queue is empty.
2) Full() : to check whether queue is full.
3) Initialize() : To make queue empty.
4) enqueueR() : To add item at the rear end of the queue.
5) enqueueF() : To add item at the front end of the queue.
6) dequeueR() : To delete item from the rear end of the queue.
7) dequeueF() : To delete item from the front end of the queue.

Multilevel Queue (MLQ) CPU Scheduling

Features of Multilevel Queue (MLQ) CPU Scheduling:

● Multiple queues: In MLQ scheduling, processes are divided into multiple queues based
on their priority, with each queue having a different priority level. Higher-priority
processes are placed in queues with higher priority levels, while lower-priority
processes are placed in queues with lower priority levels.
● Priorities assigned: Priorities are assigned to processes based on their type,
characteristics, and importance. For example, interactive processes like user
input/output may have a higher priority than batch processes like file backups.
● Preemption: Preemption is allowed in MLQ scheduling, which means a higher priority
process can preempt a lower priority process, and the CPU is allocated to the higher
priority process. This helps ensure that high-priority processes are executed in a
timely manner.
● Scheduling algorithm: Different scheduling algorithms can be used for each queue,
depending on the requirements of the processes in that queue. For example, Round
Robin scheduling may be used for interactive processes, while First Come First Serve
scheduling may be used for batch processes.
● Feedback mechanism: A feedback mechanism can be implemented to adjust the
priority of a process based on its behavior over time. For example, if an interactive
process has been waiting in a lower-priority queue for a long time, its priority may be
increased to ensure it is executed in a timely manner.
● Efficient allocation of CPU time: MLQ scheduling ensures that processes with higher
priority levels are executed in a timely manner, while still allowing lower priority
processes to execute when the CPU is idle.
● Fairness: MLQ scheduling provides a fair allocation of CPU time to different types of
processes, based on their priority and requirements.
● Customizable: MLQ scheduling can be customized to meet the specific requirements
of different types of processes.
Advantages of Multilevel Queue CPU Scheduling:
● Low scheduling overhead: Since processes are permanently assigned to their
respective queues, the overhead of scheduling is low, as the scheduler only needs to
select the appropriate queue for execution.
● Efficient allocation of CPU time: The scheduling algorithm ensures that processes
with higher priority levels are executed in a timely manner, while still allowing lower
priority processes to execute when the CPU is idle. This ensures optimal utilization of
CPU time.
● Fairness: The scheduling algorithm provides a fair allocation of CPU time to different
types of processes, based on their priority and requirements.
● Customizable: The scheduling algorithm can be customized to meet the specific
requirements of different types of processes. Different scheduling algorithms can be
used for each queue, depending on the requirements of the processes in that queue.
● Prioritization: Priorities are assigned to processes based on their type, characteristics,
and importance, which ensures that important processes are executed in a timely
manner.
● Preemption: Preemption is allowed in Multilevel Queue Scheduling, which means that
higher-priority processes can preempt lower-priority processes, and the CPU is
allocated to the higher-priority process. This helps ensure that high-priority processes
are executed in a timely manner.
Disadvantages of Multilevel Queue CPU Scheduling:
● Some processes may starve for CPU if some higher priority queues are never becoming
empty.
● It is inflexible in nature.

● There may be added complexity in implementing and maintaining multiple queues and
scheduling algorithms.
Ready Queue is divided into separate queues for each class of processes. For
example, let us take three different types of processes System processes, Interactive
processes, and Batch Processes. All three processes have their own queue. Now, look
at the below figure.

The Description of the processes in the above diagram is as follows:

● System Processes: The CPU itself has its own process to run which is generally
termed a System Process.
● Interactive Processes: An Interactive Process is a type of process in which there
should be the same type of interaction.
● Batch Processes: Batch processing is generally a technique in the Operating
system that collects the programs and data together in the form of a batch before
the processing starts.
All three different type of processes have their own queue. Each queue has its own
Scheduling algorithm. For example, queue 1 and queue 2 use Round Robin while
queue 3 can use FCFS to schedule their processes.
Scheduling among the queues: What will happen if all the queues have some
processes? Which process should get the CPU? To determine this Scheduling
among the queues is necessary. There are two ways to do so –
1. Fixed priority preemptive scheduling method – Each queue has absolute
priority over the lower priority queue. Let us consider the following priority
order queue 1 > queue 2 > queue 3. According to this algorithm, no process in
the batch queue(queue 3) can run unless queues 1 and 2 are empty. If any batch
process (queue 3) is running and any system (queue 1) or Interactive
process(queue 2) entered the ready queue the batch process is preempted.
2. Time slicing – In this method, each queue gets a certain portion of CPU time and
can use it to schedule its own processes. For instance, queue 1 takes 50 percent of
CPU time queue 2 takes 30 percent and queue 3 gets 20 percent of CPU time.
Example Problem:
Consider the below table of four processes under Multilevel queue
scheduling. Queue number denotes the queue of the process.

Priority of queue 1 is greater than queue 2. queue 1 uses Round Robin (Time
Quantum = 2) and queue 2 uses FCFS.
Below is the Gantt chart of the problem:

Working:
● At starting, both queues have process so process in queue 1 (P1, P2) runs first
(because of higher priority) in the round-robin fashion and completes after 7 units
● Then process in queue 2 (P3) starts running (as there is no process in queue 1) but
while it is running P4 comes in queue 1 and interrupts P3 and start running for 5
seconds and
● After its completion P3 takes the CPU and completes its execution.