QUEUE
QUEUE
Queue is a linear data structure in which
insertion is done from one end and deletion is
done from other end.
In stack insertion is from front end and deletion
are done from rear end.
The item inserted first is deleted first.
It is also known as FIFO (First in first out).
Example: Queue of people.
OPERATIONS ON QUEUE
Enque- Insertion of an item into queue is known
as insert operation.
Deque- Deletion of an item from queue is known
as delete operation.
Traverse- Displaying the items of queue.
Note: Insertion in the queue is done from rear
and deletion is done from front.
STATIC IMPLEMENTATION OF QUEUE
Rear increases in insertion.
Front increases in deletion.
F=-1 Initial Queue
R=-1
After insertion of first element.
1 Queue with 1 element
F=0
R=0
After insertion of second element.
1 2 Queue with 2 elements
F=0 R=1
STATIC IMPLEMENTATION OF QUEUE
After insertion of second element.
1 2 3 Queue with 3 elements
F=0 R=2
Now delete an element from queue.
2 3 Queue with 2 elements
F=1 R=2
Delete one more element from queue.
3 Queue with 1 elements
F=2
R=2
STATIC IMPLEMENTATION OF QUEUE
Now insert an element in the queue.
3 4 Queue with 2 elements
F=2 R=3
Now insert one more element in the queue.
3 4 5 Queue with 3 elements
F=2 R=4
Now insert one more element in the queue.
There will be OVERFLOW as rear is at MAXSIZE-
1. Hence, there may be some wastage of space in
simple queue. Complete space can be used after
deleting all the elements from queue.
STATIC IMPLEMENTATION OF QUEUE
INSERT OPERATION
DELETE OPERATION
TRAVERSE OPERATION
DYNAMIC IMPLEMENTATION OF QUEUE
Here the queue is implemented like singly linked
list.
INSERTION
100 rear
Initially Front=Rear=NULL
After insertion of first node.
front 100 1 NULL
100
After insertion of second node.
200 rear
front
100
1 200 2 NULL
100 200
After insertion of third node.
front 300 rear
100
1 200 2 300 3 NULL
100 200 300
DELETION
Lets the queue is:
front 300 rear
100
1 200 2 300 3 NULL
100 200 300
The deletion will be from Front.
front
200 300 rear
2 300 3 NULL
200 300
INSERT OPERATION
DELETE OPERATION
TRAVERSE OPERATION
CIRCULAR QUEUE
LIMITATION OF SIMPLE QUEUES
LIMITATION: FALSE-OVERFLOW
Suppose 6 calls to enqueue () have been made, so now the
queue array is full
2 3 1 6 4 10
[0] [1] [2] [3] [4] [5]
If we try to insert,
Overflow occurs
Assume 3 calls to dequeue ( ) are made Though some
cells are empty
6 4 10
Front Rear
Assume a call to enqueue ( ) is made now. The Rear part
seems to have no space, but the front has 3 unused spaces;
if never used, they are wasted.
SOLUTION: FALSE OVERFLOW
CIRCULAR QUEUE
CIRCULAR QUEUE
A circular queue is one in which the insertion of a new
element is done at the very first location of the queue if the
last location of the queue is full.
If we have queue Q of N elements, then after inserting an
element in last location(i.e N-1), the next will be inserted at
the very first location, if it is empty.
Rear
6 4 10
Next [0] [1] [2] [3] [4] [5]
Element
Front
CIRCULAR QUEUE
This is similar as simple queue. The insertion is
done from rear and deletion is done from front.
Overcome the limitation of simple queue by
inserting new node in begin if there is space in
begin and rear is at MAXSIZE-1.
Insertion and deletion is done in circular manner.
CIRCULAR QUEUE
INSERTION
ENQUEUE: CIRCULAR QUEUE
[2] [3]
Front = -1
Rear = -1
[1] [4]
[0] [5]
ENQUEUE:CIRCULAR QUEUE
[2] [3]
Front = 0
Rear = 0
[1] [4]
10
Rear [0] [5]
Front
ENQUEUE 10
ENQUEUE: CIRCULAR QUEUE
[2] [3]
Front = 0
Rear Rear = 1
20
[1] [4]
10
[0] [5]
Front
ENQUEUE 20
ENQUEUE: CIRCULAR QUEUE
Rear
[2] [3]
30
Front = 0
Rear = 2
20
[1] [4]
10
[0] [5]
Front
ENQUEUE 30
ENQUEUE: CIRCULAR QUEUE
[2] [3]
30 40 Front = 0
Rear = 3
20
[1] [4]
10
[0] [5]
Front
ENQUEUE 40
ENQUEUE: CIRCULAR QUEUE
[2] [3]
30 40 Front = 0
Rear = 4
20
[1] 50 [4]
10
[0] [5]
Front
ENQUEUE 50
CIRCULAR QUEUE
[2] [3]
40
Front = 0
30
Rear = 5
20
[1] 50 [4]
ENQUEUE 60
10
[0] 60 [5]
Rear
Queue is FULL Now, No further insertion is possible
ALGORITHM: INSERTION
Input: Here QUEUE is an array with N locations. FRONT and
REAR points to the front and rear elements of the QUEUE. ITEM is
the value to be inserted.
1. If (FRONT == 0 and REAR == N-1) or (FRONT == REAR + 1) Then
2. Print: Overflow
3. Else
4. If (REAR == -1) Then
(a) Set FRONT = 0
(b) Set REAR = 0
5. Else
7. Set REAR = (REAR + 1) %N
8. Set QUEUE[REAR] = ITEM
9. Print: ITEM inserted
10. Exit
IMPLEMENTATION OF CIRCULAR QUEUE
INSERT OPERATION
CIRCULAR QUEUE
DELETION
[2] [3]
30 40
20
[1] 50 [4]
10
[0] 60 [5]
Rear=5
Front=0
DEQUEUE: CIRCULAR QUEUE
[2] [3] Queue After First Dequeue
30 40
Front
20
[1] 50 [4] Front = 1
Rear = 5
[0] 60 [5]
DEQUEUE: CIRCULAR QUEUE
Front
[2] [3]
30 40
Queue After 2nd Dequeue
[1] 50 [4]
[0] 60 [5] Front = 2
Rear = 5
CIRCULAR QUEUE
Front=2
[2] [3]
40
Front = 2
30
Rear = 0
[1] 50 [4]
70
[0] 60 [5]
Rear=0 Insert 70
ALGORITHM: DELETION
Input: Here QUEUE is an array with N locations. FRONT
and REAR points to the front and rear elements of the
QUEUE.
1. If (FRONT == -1) Then
2. Print: Underflow
3. Else
4. ITEM = QUEUE[FRONT]
5. If (FRONT == REAR) Then [If only element is left]
(a) Set FRONT = -1
(b) Set REAR = -1
6. Else
7. Set FRONT = (FRONT + 1)%N
8. Print: ITEM deleted
9. Exit
DELETE OPERATION
TRAVERSE OPERATION
PRIORITY QUEUES
PRIORITY QUEUES
Each element has been assigned a priority.
Assume Maximum Element has highest priority.
Priority queue is an arrangement of data element that
allows the insertion of data element as simple queue but
allows to delete data according to their priority value.
The highest Priority element always deleted first from
Priority Queue.
Note: in Priority Queue, First-In-First-Out does not
apply.
PRIORITY QUEUES
Insertion:
Insertion is same as normal Queue.
Ex: 2, 3, 8, 6, 1
[0] [1] [2] [3] [4] [5]
2 3 8 6 1
Rear
PRIORITY QUEUES
Deletion:
While deleting, Normal Queue rules are not followed.
Based on the elements priority, following rules are
followed:
An element of higher priority is deleted before any element of
lower priority.
Two elements with the same priority are deleted according to the
order in which they were added to the queue.
DELETION: PRIORITY QUEUES
Rear
2 3 8 6 1
[0] [1] [2] [3] [4] [5]
Delete highest priority element first:==8
3 6 1
[0] [1] [2] [3] [4] [5]
DELETION: PRIORITY QUEUES
Rear
3 6 1
[0] [1] [2] [3] [4] [5]
After deletion shift rest of the element towards left element:
3 6 1
[0] [1] [2] [3] [4] [5]
TYPES OF PRIORITY QUEUES
There are two types of Priority Queue:
Ascending
An ascending priority queue is a collection of items into which
items can be inserted arbitrarily and from which only the smallest
item can be removed.
Descending:
An descending priority queue is a collection of items into which
items can be inserted arbitrarily and from which only the highest
item can be removed.
DOUBLE ENDED QUEUE :DEQUEUE
64
APPLICATIONS OF QUEUES
People waiting in line at a bank/reservation counter.
Queue in Computer Science: Used in time sharing systems
A service and more than one client – arrival rate (of clients) does not
match with the service rate.
E.g. Ticket Counters
A producer and consumer operating at different speeds
E.g. Input devices and programs;
Programs and output devices
ASSIGNMENT I
Q1: Suppose a queue is maintained by a circular array QUEUE with N=12
memory cells. Find the number of elements in QUEUE if
(a) FRONT = 4, REAR = 8 (b) FRONT = 10, REAR= 3
(c) FRONT=5, REAR = 6.
Q2: Consider the initial situation of a circular queue. F=1, R=3
.Q:_,A,C,D,_,_. Perform the following operations:
1. F is added. 2. 2 letters deleted. 3. K,L,M added.
4. 2 letters deleted. 5. R is added. 6. 2 letters deleted.
7. S is added 8. 2 letters deleted 9. 1 letter deleted
10. 1 letter deleted
F is added _,A,C,D,F,_ F=1, R=4
2 letters deleted. (A and C) _,_,_,D,F,_ F=3, R=4
K,L,M added , L,M,_,D,F, K F=3, R=1
2 letters deleted ( D and F ) L, M,_,_,_K F=5, R=1
R is added L, M,R,_,_K F=5, R=2
2 letters deleted (K and L) _, M,R,_,_,_ F=1, R=2
S is added _, M,R,S,_,_ F=1, R=3
2 letters deleted (M and R) _, _,_,S,_,_ F=3, R=3
1 letter deleted (S) _, _,_,_,_,_ F=-1, R=-1
1 letter deleted (No letter) Underflow
