QUEUE

Definition of Queue
• A Queue is an ordered collection of items from which items
may be deleted at one end (called the front of the queue) and
into which items may be inserted at the other end (the rear of
the queue).
• The first element inserted into the queue is the first element to
be removed. For this reason a queue is sometimes called a FIFO
(first-in first-out) list as opposed to the stack, which is a LIFO
(last-in first-out).
 Representing a Queue Using an Array
A Queue is maintained by a linear array and two pointer
variables: FRONT, containing the location of front element of
the queue and REAR, containing the location of rear(last)
element of the queue. The condition FRONT=NULL indicates
that queue is empty. Whenever an element is deleted from
the queue, the value of FRONT is increased by 1. Similarly,
whenever an element is added to queue, the value of REAR
is increased by 1.
 Queue as a circular queue
It can be seen that after N insertions in a Queue represented by
an array of N elements, the rear element of Queue will occupy
last part of array. This occurs even though the queue itself
may not contain many elements.
Now, if we want to insert an element ITEM into a queue, we
have to move or rearrange the elements of entire queue to
the beginning of the queue. This procedure may be very
expensive.
Another method to do so is to represent a queue as a circular
queue
i,e QUEUE[1] comes after QUEUE[N] in array. With this
assumption, we insert ITEM into queue by assigning
ITEM to QUEUE[1]. Thus instead of increasing REAR
to N+1, we reset REAR=1 and then assign
QUEUE[REAR]=ITEM
Similarly, If FRONT=N and an element of QUEUE is
deleted, we reset FRONT=1 instead of increasing
FRONT to N+1
 Algorithm for Inserting in a QUEUE
• Algorithm: QINSERT(QUEUE, N, FRONT, REAR,ITEM)
This algorithm inserts an element in a linear queue
• Step 1:[Queue already filled]
If REAR=N, then:
Write: ‘OVERFLOW’ and Exit.
• Step 2: If FRONT=NULL, then: [Queue initially empty]
Set FRONT:=1 and REAR:=1
Else:
Set REAR:=REAR+1
[End of If structure]
• Step 3: Set QUEUE[REAR]:=ITEM
• Step 4: Return
• Algorithm: QDELETE(QUEUE,N,FRONT,REAR,ITEM)
This algorithm deletes an element from a queue
• Step 1: If FRONT=NULL, then:
Write: ‘UNDERFLOW’
Exit
• Step 2: Set ITEM:=QUEUE[FRONT]
• Step 3: If FRONT=REAR, then: [Empty Queue]
Set FRONT:=NULL and REAR:=NULL
Else:
Set FRONT:=FRONT+1
[End of If structure]
• Step 4: Return
Algorithm: QINSERT(QUEUE, N, FRONT, REAR,ITEM)
This algorithm inserts an element in a circular queue
• Step 1:[Queue already filled]
If FRONT=1 and REAR=N or FRONT=REAR+1, then:
Write: ‘OVERFLOW’
Exit
• Step 2: If FRONT=NULL, then: [Queue initially empty]
Set FRONT:=1 and REAR:=1
Else If REAR=N, then:
Set REAR:=1
Else:
Set REAR:=REAR+1
[End of If structure]
• Step 3: Set QUEUE[REAR]:=ITEM
• Algorithm: QDELETE(QUEUE,N,FRONT,REAR,ITEM)
This algorithm deletes an element from a circular queue
• Step 1: If FRONT=NULL, then:
Write: ‘UNDERFLOW’
Exit
• Step 2: Set ITEM:=QUEUE[FRONT]
• Step 3: If FRONT=REAR, then: [Empty Queue]
Set FRONT:=NULL and REAR:=NULL
Else If FRONT=N, then:
Set FRONT:=1
Else:
Set FRONT:=FRONT+1
[End of If structure]
• Step 4: Return
• Consider the following queue of characters where QUEUE
is a circular array which is allocated six memory cells
FRONT=2, REAR=4 QUEUE: _ A C D _ _
Describe the queue as following operations take place:
(a) F is added to queue
(b) Two letters are deleted
(c) K , L and M are added
(d) Two letters are deleted
(e) R is added to queue
(f) Two letters are deleted
(g) S is added to queue
(h) Two letters are deleted
(i) One letter is deleted
(j) One letter is deleted
• Solution:
(a) FRONT=2, REAR=5 QUEUE: _ A C D F_
(b) FRONT=4, REAR=5 QUEUE: _ _ _ D F _
(c) REAR=2, FRONT=4 QUEUE: L M _ D F K
(d) FRONT=6, REAR=2 QUEUE: L M _ _ _ K
(e) FRONT=6, REAR=3 QUEUE: L M R_ _ K
(f) FRONT=2, REAR=3 QUEUE: _M R _ _ _
(g) REAR=4, FRONT=2 QUEUE: _ M R S _ _
(h) FRONT=4, REAR=4 QUEUE: _ _ _ S _ _
(i) FRONT=REAR=0 [ As FRONT=REAR, queue is empty]
(j) Since FRONT=NULL, no deletion can take place.
Underflow occurred
• DEQUE(Double ended Queue)-
A deque is a queue in which elements can be added or
removed at either end but not in the middle. A deque is
usually maintained by a circular array DEQUE with pointers
LEFT and RIGHT, which point to two ends of deque. The
elements extend from LEFT end to RIGHT end of deque.
The term circular comes from the fact that DEQUE[1]
comes after DEQUE [N].The condition LEFT=NULL will be
used to indicate that a deque is empty.
• There are two variations of a deque
• Input-restricted deque- It is a deque which allows
insertions at only one end of list but allows
deletions at both ends of the list.
• Output-restricted deque- It is a deque which allows
deletions at only one end of list but allows
insertions at both ends of list
• Consider the following deque of characters where DEQUE is a circular
array which is allocated six memory cells.
LEFT=2, RIGHT=4 DEQUE: _ A,C,D, _ , _
• Describe deque while the following operation take place
(a) F is added to right of deque

(b) Two letters on right are deleted

(c) K,L and M are added to the left of the deque

(d) One letter on left is deleted.

(e) R is added to the left of deque.

(f) S is added to right of deque

(g) T is added to the right of deque

(a) F is added to right of deque
LFET=2, RIGHT=5 _A C D F _
(b) Two letters on right are deleted
LEFT=2 RIGHT=3 _A C _ _ _
(c) K,L and M are added to the left of the deque
LEFT=5 RIGHT=3 KAC_ML
(d) One letter on left is deleted.
LEFT=6 RIGHT=3 KAC__L
(e) R is added to the left of deque.
LEFT=5 RIGHT= 3 KAC_RL
(f) S is added to right of deque
LEFT=5 RIGHT= 4 KACSRL
(g) T is added to the right of deque
Since LEFT= RIGHT+1 , the array is full and hence T cannot
be added to the deque
 Linked representation of the Queue
• A linked queue is a queue implemented as a linked list
with two pointer variables FRONT and REAR pointing to
the nodes in the front and rear of the queue. The INFO
field of list hold the elements of the queue and LINK field
holds pointer to neighboring element of queue.
• In case of insertion in linked queue, a node borrowed
from AVAIL list and carrying the item to be inserted is
added as the last node of linked list representing the
queue. Rear pointer is updated to point to last node just
added to the list In case of deletion, first node of list
pointed to by FRONT is deleted and FRONT pointer is
updated to point to next node in the list.
• Unlike the array representation, linked queue
functions as a linear queue and there is no need to
view it as circular for efficient management of
space.
Algorithm:LINKQINSRT(INFO,LINK,FRONT,REAR,AVAIL,ITEM
This algorithm inserts an item in linked list implementation
of the queue.
Step 1: If AVAIL=NULL,then:
Write: ‘OVERFLOW’
Exit
Step 2: Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
Step 3: Set INFO[NEW]:=ITEM and LINK[NEW]:=NULL
Step 4: If FRONT=NULL, then:
Set FRONT=REAR=NEW
Else:
Set LINK[REAR]:=NEW and REAR:=NEW
Step 5: Return
Algorithm: LINKQDEL(INFO,LINK,FRONT,AVAIL,ITEM)
This algorithm deletes an element from the front of the queue
• Step 1: If FRONT=NULL,then:
Write:’UNDERFLOW’
Exit
• Step 2: Set TEMP:=FRONT
• Step 3: Set ITEM:=INFO[FRONT]
• Step 4: Set FRONT:=LINK[FRONT]
• Step 5: Set LINK[TEMP]:=AVAIL and AVAIL:=TEMP
• Step 6: Return
• Priority Queue- A priority queue is a collection of elements
such that each element has been assigned a priority and
such that the order in which elements are deleted and
processed comes from following rules:
• An element of higher priority is processed before any
element of lower priority
• Two elements of same priority are processed according to
the order in which they were added to queue
• An example of a priority queue is a time sharing system.
Programs of higher priority are processed first and
programs with same priority form a standard queue
 One-way list representation of a priority queue

One way to maintain a priority queue in memory is by means

of a one-way list Each node in list will contain three items
of information: an information field INFO, a priority
number PRN and a link field LINK.
• A node X precedes a node Y in list
– If X has higher priority than Y
– Or when both have same priority but X was added to list before Y
Algorithm:LKQINS(INFO,LINK,FRONT,PRN,AVAIL,ITEM, P)
This algorithm inserts an item in linked list implementation of priority queue
Step 1: If AVAIL=NULL,then:
Write: ‘OVERFLOW’
Exit
Step 2: Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
Step 3: [Enter the data and priority of new node] Set INFO[NEW]:=ITEM and
PRN[NEW]:=P
Step 4: Set PTR:=FRONT
Step 5: If PRN[PTR]>PRN[NEW], then
LINK[NEW]:=FRONT
FRONT:=NEW
Return
[End of If Structure]
Step 5: Repeat while PTR≠NULL and PRN[PTR]<=PRN[NEW]
Set SAVE:=PTR
Set PTR:=LINK[PTR]
[End of If Structure]

Step 6: If PRN[PTR]>PRN[NEW]
Set LINK[SAVE]:=NEW
Set LINK[NEW]:=PTR
Else:
Set LINK[SAVE]:=NEW
Set LINK[NEW]=NULL
[End of If Structure]

Step 7: Return
• Another way to maintain a priority queue in memory is to use a
separate queue for each level of priority . Each such queue will appear
in its own circular array and must have its own pair of pointers, FRONT
and REAR.
• If each queue is allocated the same amount of space, a two
dimensional array QUEUE can be used instead of the linear arrays for
representing a priority queue.
• If K represents the row K of the queue, FRONT[K] and REAR[K] are the
front and rear indexes of the Kth row.
1 2 3 4 5 6
Priority

1 AAA
2 BBB CCC XXX
3
4 FFF DDD EEE
Algorithm: QINSERT( QUEUE,N, FRONT, REAR,ITEM,K)
This algorithm inserts an element in a priority queue in a row with priority
K. N is the size of the Kth row.
• Step 1:[Queue already filled]
If FRONT[K]=1 and REAR[K]=N or FRONT[K]=REAR[K]+1, then:
Write: ‘OVERFLOW’
Exit
• Step 2: If FRONT[K]=NULL, then: [Queue initially empty]
Set FRONT[K]:=1 and REAR[K]:=1
Else If REAR[K]=N, then:
Set REAR[K]:=1
Else:
Set REAR[K]:=REAR[K]+1
[End of If structure]
• Step 3: Set QUEUE[K][REAR[K]]:=ITEM