Queue
C E – S E – D ATA S TR U CT U RE S
DR. DEEPTI REDDY
A S S O C I AT E P R O F E S S O R
D E P T. O F C O M P U T E R E N G I N E E R IN G ,
Learning Outcomes
•To be able to write ADT of queue
•To be able to represent data using linear data structures- queue.
•To be able to perform various operations on data structure- queue
•To be able to demonstrate the applications of queue.
Module2- Stack and Queue
◦ Introduction to Queue,
◦ Operation on Queues,
◦ Linear queue
◦ Circular queue,
◦ Priority queue,
◦ Application of Queues.
Queue Real Examples
People standing in a queue Cars lined at a toll bridge
People moving on an escalator Luggage kept on conveyor belts
Queue
A queue is a FIFO (First-In, First-Out) data structure in which the element that is
inserted first is the first one to be taken out.
The elements in a queue are added at one end called the REAR and removed from
the other end called the FRONT.
Front Rear Rear Rear
Queue ADT
Queue Q, Front, Rear
Operations
1. Insert(Q, val) – Insert new element at the end of the queue.
2. Remove (Q)- Removes element from the front of the queue.
3. isEmpty(Q)- returns true if queue is empty else returns false
4. IsFull(Q)- returns true if queue is full else returns false
Insert operation
Step 1: IF REAR == MAX-1
◦ Write OVERFLOW
◦ Goto step 4
◦ [END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
◦ SET FRONT = REAR = 0
◦ ELSE
◦ SET REAR = REAR + 1
◦ [END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
C++ function to insert
int queue[100], MAX = 5, front = - 1, rear = - 1
void insert(int num )
{
if(_________)
cout<<"Queue Overflow"<<endl;
else
{
if(_________)
front=0;
rear++;
queue[rear]=_____;
}
}
C++ function to insert
int queue[100], MAX = 5, front = - 1, rear = - 1
void insert(int num )
{
if(rear==MAX–1)
cout<<"Queue Overflow"<<endl;
else
{
if(front==–1)
front=0;
rear++;
queue[rear]=num;
}
}
Remove operation
Step 1: IF FRONT == -1 OR FRONT > REAR
◦ Write UNDERFLOW
ELSE
◦ SET VAL = QUEUE[FRONT]
◦ SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
C++ function to delete
void delete(int num )
{
if (_________________)
cout<<"Queue Underflow"<<endl;
else
{
cout<<"Element deleted from queue is : "<< queue[front] <<endl;
__________
}
}
C++ function to delete
void delete(int num )
{
if (front == - 1 || front > rear)
cout<<"Queue Underflow"<<endl;
else
{
cout<<"Element deleted from queue is : "<< queue[front] <<endl;
front++;
}
}
Example
Queue[5], front=Rear=-1
1. Insert(A)
2.Insert(B)
3. Insert(C)
4. Remove()
5. Remove()
6. Insert(D)
7. Remove()
8. Insert(E)
10. Insert(F)
Simulate the algorithm and at each step show the instance of the queue and values in
Front and Rear.
Example
Queue[5], front=Rear=-1
1. Insert(A)
2.Insert(B)
3. Remove()
4. Remove()
5. Remove()
6. Insert(D)
8. Insert(E)
10. Insert(F)
Simulate the algorithm and at each step show the instance of the queue
and values in Front and Rear.
Circular queue
Overcomes the disadvantage of linear queue
Even though there is space available, the overflow condition still exists
because the condition rear = MAX – 1 still holds true.
This is a major drawback of a linear queue.
Circular queue
Circular queue overcomes the disadvantage of linear queue.
In the circular queue, the first index comes right after the last index.
Conceptually, you can think of a circular queue as shown in Fig. 8.15
Circular Queue- Insert
When is circular queue full?
2 5 6 8 9 10 3 89 34 67
Front=0 and Rear=9
After deleting one element
5 6 8 9 10 3 89 34 67
After inserting one element
5 6 8 9 10 3 89 34 67
Circular Queue- Insert
Conditions to be checked to insert new element, if circular queue is not
empty.
1. If first element is inserted
Front=-1, Rear=-1
2. if else rear is pointing to last position and queue is not full
6 8 9 10 3 89 34 67
Front=2, Rear=9
3. Else increment rear
Circular Queue- Insert
Algorithm
Step 1: IF ((FRONT = 0 and Rear = MAX – 1 ) || (Front==Rear +1 ))
◦ Write OVERFLOW, Goto step 4
◦ [END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
◦ SET FRONT = REAR = 0
◦ ELSE IF REAR = MAX - 1 and FRONT != 0
◦ SET REAR = 0
◦ ELSE
◦ SET REAR = REAR + 1
◦ [END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
C++ function to insert
int cqueue[100], MAX = 5, front = - 1, rear = - 1
void insert(int queue[],int num )
{
If((front==0 && rear==MAX–1)||(front==rear+1))
cout<<"Queue Overflow"<<endl;
else 1. rear++;
{ 2. queue[rear]=num
if(front==–1 && rear==–1)
front=rear=0; 4. rear=0
else if(rear==MAX–1 && front!=0)
___________;
else
___________;
queue[rear]=num;
}
}
Circular Queue- Delete
1. Check underflow condition
Front=-1, Rear=-1
2. If deleting the last element
3
Front=1, Rear=1
3. if the front is pointing to the last
2 5 4 5 10
Front=9, Rear=3
4. Else front=0, Rear=3
2 5 4 5
C++ function to delete
void delete_element() 1. front=rear=–1
{
int val; 2. front==–1 && rear==–1
if(___________)
cout<<"Queue Underflow"<<endl; 3. front++;
else
{
cout<<"Element deleted from queue is : "<< queue[front] <<endl;
if(front==rear)
____________;
else if(front==MAX–1)
front=0;
else
_________
}
}
Circular Queue- Delete
Algorithm
Step 1: IF FRONT = -1
◦ Write UNDERFLOW
◦ Goto Step 4
◦ [END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT == REAR
◦ SET FRONT = REAR = -1
◦ ELSE
◦ IF FRONT = MAX -1
◦ SET FRONT = 0
◦ ELSE
◦ SET FRONT = FRONT + 1
◦ [END of IF]
◦ [END OF IF]
Step 4: EXIT
Algorithm to simulate bank
queue
Queue[10], Max=10
Input: customer_id
Delete customer_id in FIFO manner.
Reflection
Consider the following pseudo-code. Assume that IntQueue is an integer
queue. What does the function fun do?
void fun(int n)
{
IntQueue q = new IntQueue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < n; i++)
{
int a = q.dequeue();
int b = q.dequeue();
q.enqueue(b);
q.enqueue(a + b);
print(a);
}
}
Reflection
A standard circular Queue 'q' implemented whose size is 11 from 0 to
10. The front & rear pointers start to point at q[2]. The ninth element
be added at which position?
Activity
Draw the queue structure in each case when the following operations are
performed on an empty queue.
(a) Add A, B, C, D, E, F
(b) Delete two letters
(c) Add G
(d) Add H
(e) Delete four letters
(f) Add I
Priority Queue
In priority queue, the operations are based on the priority of the
element.
Example- Priority queues are widely used in operating systems to execute the
highest priority process first.
Types of priority queue
Types of priority queue
1. ascending priority queue
An ascending priority queue is a collections of items into which
elements can be inserted arbitrarily and from which only the smallest
item can be removed.
Operations-
apq – ascending PQ.
pqinsert(apq, x)- inserts item x into ascending PQ.
pqmindelete(apq)- removes the smallest element from the apq and
returns its value.
Types of priority queue
2. descending priority queue
An descending priority queue is a collections of items into which
elements can be inserted arbitrarily and from which only the largest
item will be removed.
Operations-
dpq – descending PQ.
pqinsert(dpq, x)- inserts item x into descending PQ.
pqmaxdelete(dpq)- removes the largest element from the dpq and
returns its value.
Isempty()- determines if PQ is empty. Returns true if empty otherwise
returns false.
Array implementation of
Priority Queue
In stack and queue are implemented using an array such that insertion and
deletion involves accessing only one element of an array. However, this is not
possible in priority queue.
Suppose that n elements of the priority queue pq are maintained in positions 0
to n-1 of an array of size maxpq, and suppose rear equals to the first empty
position, n. Then pqinsert (pq, x) is straightforward operation:
pqinsert(int pq[], int x)
{
if (rear >= maxpq)
{
cout<<" priority queue overflow “<<endl;
exit(1);
}
pq[rear]=x;
rear++;
}
Array implementation of
Priority Queue
If we want to attempt operation pqmindelete(pq) on a ascending priority
queue.
This raises two issues:
First, to locate smallest element, every element of the array from items
pq[0] to pq[rear-1] must be examined.
Second, how to delete the element from the middle of the array.
pq[], maxpq=10, rear=5
6 5 2 18 7
insertpq (pq, 10)
pqmindelete(pq)
Solution to deal with empty location after delete operation is
1. to mark the location as -1 to indicate that it is a empty location and
when rear reaches the maxpq, then compact the array by and reset the
rear.
2. for every insertion, find the first empty location and insert the new
item.
3. compact the array on each deletion.
4. maintain the elements in a ordered manner (ascending order), then
deletion will be simple operation where only the first element is to be
removed, however insertion operation involves to search for the
position to insert into the ordered array.
Priority queue program
#define MAX 10
int pq[MAX], rear=0;
void insertpq(int pq[], int x)
rear=4
{
int i;
1 2 4 5 6
if (rear>=MAX)
cout<<" priority queue overflow “<<endl;
else
Insertpq(pq, 3)
{
3 is inserted after 2
i=rear;
while(i>=0 && pq[i]> x)
1 2 3 4 5 6
{pq[i+1]=pq[i]; i--;}
shift
pq[i+1]=x; rear++;
} rear=5
}
Priority queue program
#define MAX 10
rear=4
int pq[MAX], front=0, rear=0;
void deletepq(int pq[]) 1 2 4 5 6
{
int i;
if (rear==-1)
deletpq(pq)
cout<<" priority queue underflow “<<endl;
else
2 4 5 6
{
cout<<"Element deleted from queue is : "<< queue[0] <<endl;
shift rear=3
i=0;
while(i<rear)
{
__________
i++;
}
rear--
}
}
APPLICATIONs OF QUEUES
1. Queues are widely used as waiting lists for a single shared resource like
printer, disk, CPU.
2. Queues are used to transfer data asynchronously (data not necessarily
received at same rate as sent) between two processes (IO buffers), e.g.,
pipes, file IO, sockets.
3. Queues are used as buffers on MP3 players and portable CD players,
iPod playlist.
4. Queues are used in Playlist for jukebox to add songs to the end, play
from the front of the list.
5. Queues are used in operating system for handling interrupts. When
programming a real-time system that can be interrupted, for example,
by a mouse click, it is necessary to process the interrupts immediately,
before proceeding with the current job. If the interrupts have to be
handled in the order of arrival, then a FIFO queue is the appropriate
data structure
