Stack contd…

Linear Data Structure- Queue

May 5, 2021 16
 Queue
• Widely used linear data structure
• Deletions of data can take place at one front.
• Insertions can take at the rear.
 Definition
• A queue is an ordered collection of items from
which item may be deleted at one end called
the front end of the queue and into which
item may be inserted at the other end called
the rear of the queue.
• FIFO (First In First Out).

May 5, 2021 19
Rear= Rear+1
Font= Font+1
• Static implementation (using arrays)
• Dynamic implementation (using pointers)

May 5, 2021 20
May 5, 2021 21
 Operations on Queue
• Insert (enqueue) : adding a new item to the
rear end.
• Remove (dequeue): removing the front item
from queue and returning it.
• isEmpty operation: checks whether the queue
is empty or not. If it is empty, the function
returns true otherwise false.

May 5, 2021 22
May 5, 2021 23
May 5, 2021 24
• A new element can always be added.
• It can also be empty, at which point removing
an element will be impossible until a new
element has been added again.

May 5, 2021 25
May 5, 2021 26
May 5, 2021 27
Figure 5-6
• Queue overflow results from trying to add an
element onto a full queue
• Queue underflow happens when trying to
remove an element from an empty queue.

May 5, 2021 29
 Queue linked list design

May 5, 2021 30
 Queue data structure

May 5, 2021 31
May 5, 2021 32
 Create queue

May 5, 2021 33
 Enqueue

May 5, 2021 34
 Enqueue algorithm

May 5, 2021 35
May 5, 2021 36
May 5, 2021 37
 Dequeue algorithm

May 5, 2021 38
May 5, 2021 39
 Queue data structure

May 5, 2021 40
 Representing Queue in C

May 5, 2021 41
May 5, 2021 42
 Implementation of Operations
(remove/insert)

May 5, 2021 43
May 5, 2021 44
 Priority Queue
• The intrinsic ordering of the elements
determines the results of the basic operations.
• Two types of priority queue.
-Ascending Priority Queue
-Descending Priority Queue

May 5, 2021 45
 Addition in a Queue
Queue is declared a int queue [5], Front= -1 and rear = -1
void queue ( )
{ int item
if (Rear < 4)
{ printf (“Enter the number”) ;
scanf (“%d” & item) ;
if (front = -1)
{ front = 0 ;
rear = 0 ;
}

May 5, 2021 46
else
{ rear = rear+1 ;
}
queue [rear] = item ;
}
else
print f (“queue is full”)
}

May 5, 2021 47
 Deletion from a Queue
void delete ( )
{ int item ;
if (front = -1)
{ item = queue [front] ;
if (front = rear)
{ front = -1 ;
rear = -1 ;
}

May 5, 2021 48
else
front = front + 1 ;
printf (“No deleted is = %d”, item) ;
}
else
printf (“queue is empty”) ;
}

May 5, 2021 49
• An ascending priority queue is a collection of
items into which items can be inserted
randomly and from which only the smallest
item can be removed.
• A descending priority queue is similar but
allows deletion of only the largest item.

May 5, 2021 50
 Array implementation of queue
• Since a queue usually holds a bunch of items
with the same type, we could implement by
means of one way list or linear array.
• Here the queue in a linear way is maintained
with two pointers called FRONT, containing
the location of the front element of the queue
and REAR, to hold the location which is at rear.
May 5, 2021 52
May 5, 2021 53
• Here, whenever the element is deleted from
the queue the value of the FRONT is increased
by 1 this can be implemented by FRONT:
=FRONT+1.
• Similarly whenever an element is added to the
queue, the value of REAR is increased by 1 by
assigning REAR: =REAR +1.
May 5, 2021 55
• After N insertions, the rear element of the
queue will occupy QUEUE[N] and this occurs
even the array is not full.
• If we insert a new element when REAR =N,
one way to handle this is to simply move the
entire queue to the beginning of the array and
change FRONT AND REAR accordingly and
then insert an item.
• This procedure may be expensive, an alternate
is consider the queue is circular that is
QUEUE[1] comes after QUEUE[N] in the array.
• With this assumption we can insert ITEM into
the queue by assigning ITEM to QUEUE[1],
instead of increasing the REAR to N+1 we can
reset REAR=1 then the assignment will be
QUEUE[REAR]:=ITEM.
• Similarly if FRONT=N and an element of queue
is deleted we can reset FRONT=1 instead of
increasing FRONT to N+1.
• Insert an element into the queue with the
procedure QINSERT(): Before insertion we
need to check the overflow status of the
queue and find the current position of REAR
and increment that with one and this is the
new location for inserting a new item .
Delete an item from the queue with the
procedure QDELETE():
• It checks for the underflow status if queue
contains items it deletes an first element from
the queue by assigning it to the variable ITEM
and calculate new value for REAR.
 Linked implementation of queue
• Queues are almost similar to linked list except
the ability to manipulate items on the lists, a
linked queue is a queue implemented as a
linked list.
• As we know insertion can happen only with
REAR, the NEW node is linked with the LINK
[REAR] and the Value of the REAR will
increase.
• The rear point will be updated in order to
point the node which is recently entered.
• To insert a new node into the queue, new
node is availed from the AVAIL list and ITEM D
is assigned with the new node. Before
insertion the value of the REAR was REAR = 3
and having NULL pointer.
Deletion of element from linked queue
• The deletion can happen only from the FRONT
end.
• In case of deletion the first node of the list
pointed to by FRONT is deleted and the
FRONT pointer is updated to point to the next
node in the list and the deleted node will be
return to the AVAIL list.
 Example

May 5, 2021 71
May 5, 2021 72
 Application of queues
• Direct applications
– Waiting lists, bureaucracy
– Access to shared resources (e.g., printer)
– Multiprogramming
• Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures

May 5, 2021 73
 A Circular Queue
qbuff qbuff
front = rear min front min
38
rear 45

max max
(a) (b)

empty Containing 2 values

inc rear
if rear > max
then rear = min
if front = rear
then queue is full
dec rear
if rear < min
then rear = max
else store value at rear

Algorithm to store a value in the circular queue

if front = rear
then queue is empty (set false flag)
else inc front
if front > max
then front = min
read byte at front
set true flag

Algorithm to check queue for a value

; A circular queue

qbuff
qsize equ 16 qbuff

front dw 0 front = rear min front min

rear dw 0 38
qmin dw 0 rear 45
qmax dw 0
qbuff rmb qsize

initq
ldd #qbuff
std front
std rear max max
std qmin (a) (b)
addd #(qsize-1)
std qmax
rts
; Store A in queue
qstore
psha ;save A
ldd rear
addd #1 ;inc rear
cpd qmax
bls qs1 ;if rear > qmax
ldd qmin
qs1 std rear ; rear = qmin
cpd front ;if rear = front
bne qs3 ; queue if full
subd #1 ; dec rear
cpd qmin
bhs qs2 ; if rear < qmin
ldd qmax
qs2 std rear ; rear = qmax
pula ; pop A
bra qs4 ; and return
qs3 pula ;else
ldx rear
staa 0,x ; store A at rear
qs4 rts
; Check queue
; if queue is empty, carry = 1
; else, carry = 0 and A = value taken from queue
checkq
ldd front
cpd rear ;if front = rear
bne cq0 ; queue is empty
orcc #$01 ; set carry flag
bra cq2
cq0 ldd front ;else
addd #1 ; inc front
cpd qmax
bls cq1 ; if front > qmax
ldd qmin
cq1 std front ; front = qmin
ldx front
ldaa 0,x ; A = @front
andcc #$fe ; clear carry flag
cq2 rts
• Use Linear Array to implement a queue.
 Implementation of Circular queue with (n-
1) space used
• Create(Q)
Q: Array[0…n-1] 0 1 2 … n-1
front = rear = 0 //initialize
• Enqueue(item, Q) Queue
begin
R  R = (R+1) mod n
rear = (rear+1) mod n; //rear moves forward;
if rear = front
QueueFull; // Queue is full.
rear = rear-1 mod n; // rear back to the previous position;
else
Q[rear]=item;
end;
Implementation of Circular queue with (n-
1) space used
• Dequeue(Q) item
X X
X X
begin
if front=rear X X
QueueEmpty; X X
else X
X
front = (front+1) mod n; R X X
F
item = Q[front];
end;
end;
• Note: only (n-1 ) space used;
Implementation of Circular Queue with n
space used
• A parameter “Tag” is introduced to help to make sure the
queue is Empty or Full:
– Boolean
– If Tag = True, combined with other conditions => queue is
Full
– If Tag = False, combined with other conditions => queue is
Null
– “Tag” can determine the states of the queue solely!
 Implementation of Circular Queue with n
space used
• Create(Q)

Q: Array[0…n-1]
front = rear: int = 0
Tag: Boolean = False

• Enqueue(item, Q) Queue

begin
if (rear = front &Tag = 1)
QueueFull;
else begin
rear = (rear+1) mod n; //rear moves forward;
Q[rear]=item;
if (rear=front)
Tag=1;
end;
end;
 Implementation of Circular Queue with n
space used
• Dequeue(Q) item
begin X X
if (Front=Rear and Tag=0) X X
QueueEmpty;
X X
else begin
Front = (Front+1) mod n; X X
item = Q[Front]; X
X
if (Front=Rear) R X X
Tag=0; F
end;
end;

• Note: n space can be used

 Assignment # 1
(Submission due: April 23, 2021)
1. What is asymptotic notation? Discuss the various types of
notations.
2. What is algorithm? Briefly explain the levels of data
structure.
3. What is stack?
a. Find postfix expression of A+B*(C+D)/F+D*E
b. Convert 4*2/(3-2)+2*(6-1) into prefix expression
4. Explain the logical representation of stacks in memory with
example. What are the different application areas of stack?
5. What is queue? Describe array and linked implementation of
queue.

May 5, 2021 85