Chapter 3:Queue

[Link] Neupane

Lecturer, Jankapur Engineering College

Tathali,Bhaktapur
Queue:(Linear Queue)(Imp)
A Queue is FIFO(First In First Out) data structure i.e. the item which is
inserted at first is the item to be deleted at first. A queue is an ordered
collection of items in which all insertions are made at one end (the rear),
and all deletions are made at the other end (the front).
Enqueue and Dequeue operations in a Queue:
The process of inserting an item in a queue at the rear end is
called an enqueue operation and the process of deleting an from
the front end is called a dequeue operation. The process and
enqueue and dequeue operations in a queue of size of 5 is shown
as:
Illustration

0 1 2 3 4 0 1 2 3 4
Enqueue(32)
Enqueue(18) 32 18 58
Enqueue(58)
r = -1, f = 0 f=0 r=2

Dequeue() → 32
Dequeue() → 18

0 1 2 3 4 0 1 2 3 4
Enqueue(68)
58 68 96 Enqueue(96) 58
f=2 r=4 f = 2, r = 2

A queue with an array of size 5

3
Algorithm for enqueue and dequeue operations in a queue(linear
queue):(Imp)

[Link] and initialize necessary variables: front =0 and rear= -1,maxsize,item,queue[maxsize].

[Link] enqueue operations:
if(rear>=maxsize-1)
print "queue is full”.
Else
Read an item from the user
rear=rear+1
queue[rear]=item
[Link] next enqueue operation, repeat step 2.
[Link] Dequeue operations:
if front> rear
print “queue is empty”
Else
item=queue[front]
front=front+1
display item
[Link] next dequeue operation, repeat step 4.
 Drawbacks(problems) of Linear Queue(Imp):

• Both the rear and front indices are increased but never decreased
• As items are removed from the queue, the storage space at the
beginning of the array is discarded and never used again

0 1 2 3 4

58 68 96
f=2 r=4

This queue is considered full, even though the space at

beginning is vacant
6
Circular Queue:
Circular queue is type of data structure which follows FIFO principle. In circular queue an array is
viewed as a circle rather than a straight a [Link] queue solves the drawbacks of linear queue
Enqueue and dequeue operations in a circular queue:

7
Algorithm for Enqueue and Dequeue Operations in a Circular
Queue(with one position left vacant)(Imp)
[Link] and initialize necessary variables: front
=0,rear=0,maxsize,[Link][maxsize].
[Link] enqueuer operation:
If front==(rear+1) % maxsize
print "queue is full”
Else
Read an item from the user.
queue[rear]=item
rear=(rear+1) % maxsize 8
[Link] next enqueuer operation, repeat step 2
[Link] dequeuer operation:
If front==rear
print” Queue is empty”
Else
item=queue[front]
front=(front+1) % maxsize
display an item
[Link] next dequeuer operation, repeat step 4

9
 Applications of Queue
• Direct Applications
– Access to shared resources
• Within a computer system there may be queues of tasks waiting for the printer, for
access to disk storage, or even in a time-sharing system, for use of the CPU.
-Task Scheduling in operating system
• Indirect Applications
– Auxiliary data structure for algorithms
– Component of other data structures

10
 Checking Palindromes
• Read each letter in the phrase. Enqueue the letter into the queue, and
push the letter onto the stack.
• After we have read all of the letters in the phrase:
– Until the stack is empty, Dequeue a letter from the queue and pop a letter from
the stack.
– If the letters are not the same, the phrase is not a palindrome

11
Priority Queue:(Imp)
A priority queue is a collection of elements such that each element has
been assigned a priority and the order in which elements are deleted
processed comes from following rules.
1]An element of higher priority is processed before any element of lower
priority.
2]An element of lower priority is processed before any element of higher
priority
3]If two elements have same priority then they are processed according
to the order in which they are added to the queue.

12
 Types of Priority Queues
• Ascending (Min) Priority Queue
– A collection of items into which items can be inserted arbitrarily but only the
smallest item can be removed
• Descending (Max) Priority Queue
– A collection of items into which items can be inserted arbitrarily but only the
largest item can be removed

13
 Illustration

69 50 32 69 50 32 78
Insert(78)

Insert(88)

69 50 32 88 78

DeleteMin() → 32

69 88 78 DeleteMin() → 50 69 50 88 78

Fig:A minimum priority queue

14
 Applications of Priority Queue(Imp)

• In a time-sharing computer system, a large number of tasks

may be waiting for the [Link] of these tasks have higher
priority than others. The set of tasks waiting for the CPU forms
a priority queue

15
 Deque
• A deque (double-ended queue) is a data structure consisting of
a list of items, on which the following operations are possible
– Push(D, x) – Insert item x on the front of deque D
– Pop(D) – Remove the front item from deque D and return it
– Inject(D, x) – Insert item x on the rear end of deque D
– Eject(D) – Remove the rear item from deque D and return it

16
 Illustration

69 50 32 78 69 50 32
Push(78)
f r f r
Inject(88)

A deque 78 69 50 32 88
f r

Pop() → 78

69 50 32 Eject() → 88 69 50 32 88
f r f r

17
Queue as an ADT:(Imp)
A queue of elements of type T is a finite sequence of elements of T together with the
operations defined as follows.
Make Empty(Q):To create an empty queue Q
Is Empty(Q):To check whether the queue is empty or not. Return true if Q is empty
otherwise return false
Is Full(Q):To check whether the queue is full or not. Return true if Q is full otherwise
return false.
Enqueue(Q, x):To insert an item x at the rear of the queue if and only if queue is not
full.
Dequeue(Q):To delete an item from the front of the queue if and only if Q is not
empty.
Traverse(Q):To read the entire queue that is to display the content of the queue.
18