Data Structures

6.40
The procedures which insert and delete elements in deques and the variati.
are given as supplementary problems. As with queues, a complication mas tions on those pr
overflow, that is,
when an element is to may arise (a) when
be inserted into a deque which is
there is underflow. that is, when an element is to be deleted from a dec 1s alrea
procedures must consider these possibilities.
nehfulls, or (b
6.13 PRIORITY QUEUESS
emn
A priority queue is a collection of elements such
that each element has been
and such that the order in which elements are deleted ac

sed comes from ed a

and processed
rules:
An element of higher priority is processed before any element
Two elements with the same of lower prioritv
2 priority
were added to the
are
processed according to the
order in whi
hich
queue.
A prototype of a priority queue is a timesharing System:
first, and programs with the programs of high priority aret
There are various ways
same
priority form a standard queue. procs
of maintaining a priority queue in
here: one uses a memory. We discuss two af
one-way list, and the other uses multiple queues. The ease or
elements to or deleting them from a priority queue clearly depends on the difficulty in
chooses. representation tha

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, as follows:
(a) Each node in the list will contain three items of
information: an information field INAD
priority number PRN and a link number LINK.
(b) A node X precedes a node Y in the
list (1) when X has higher priority than Y or
both have the same
prioritybut X (
was added to the list before Y. This means that tne e
in the one-way list
corresponds to the order of the
priority queue.
Priority numbers will operate in the usual
way: the lower the
priority. priority number, the
ngher

Example 6.13
Figure 6.27 shows a schematic
diagram of a priority queue with 7 elements. Ine
diagram does not tell us whether BBB was added to the list before or after On
the other hand, the
diagram does tell us that BBB was inserted before CC, ausebD
BBB and CCC have the same
priority number and BBB appears before CCC in
Detalist.
Figure 6.28 shows the way the priority queue tne
near
arrays INFO, PRN and LINK. (See Sec. may appear in memory using
5.2.)
 ursion

START 6.41

AAA 1 BBB 2 ccc| 2 DDD

DDD 4
EEE 4-FFF 4
Fig. 6.27 GGG5
INFO PRN
LINK
BBB 2
START 5 2
6

3 DDD
AVAIL 4
EEE 4
9
5 AAA
6 CCC 2
3

10
8
GGG 5
9 FFF
8
10
11
11
12
12

Fig. 6.28
Ihe
main
property of the
element in the queue that one-way list
should be representation of a
priority
queue is that the
0r the
one-way list. Accordingly, processed first always appears the at
matter to delete and beginning
ement from our it is a
very simple
priority queue. The outline of the process an
algorithm follows.
gorithm 6.17: This
algorithm deletes and processes the first element in a
which appears in
memory as a one-way list. priority queue
1. Set ITEM :=
2. Delete
INFOJSTART]. [This saves the data in the first node.]
first node from the list.
3. Process ITEM.
4. Exit.
 Data Structures
6.42
The details ofthe algorithm. including the possibility of underflow. are left
AAding an element to our priority queue iS much more complicated thanas
left an
exerg
Xercise
element. NetAningoutanline
because we need to find the correct
from the queue, place to insert the element
algorithm follows.

Algorithm 6.18: This algorithm adds an ITEM with priority number N ta

which is maintained in memory as a one-way list.
number
N to a
priont
(a) Traverse the one-way list until finding a node X
exceeds N. Insert ITEM in front of node X. whose prior
whose priority tun
(b) If no such node is found, insert I'TEM as the last
element of the
The above insertion algorithm may be pictured as a weighted object ist.
elements until it meets an element with a heavier "sinking" throueh
weight.
The details of the above algorithm are left as an
la
exercise. The main
comes from the fact that ITEM is inserted before node X. difficulty in the al.
This means that, while
traversino algor
one must also keep track of the address of the
node preceding the node he
being accessed
Example 6.14
Consider the priority queue in Fig. 6.27.
Suppose an item XXX with priority number 2
is to be inserted into the
queue. We traverse the list, comparing priority numbers.
Observe that DDD is the first element in the list whose
of XXX. Hence XXX is inserted in the list in front of priority number exceeds that
DDD, as pictured in Fig. 6.29.
Observe that XXX comes after BBB and CCC, which have the
Suppose now that an element is to be deleted from the queue. It priority
same as XXx.
will be AAA, the
first element in the list.
Assuming no other insertions, the next element to be deleted
will be BBB, then CCC, then XXX, and so on.

START
Xxx 2
AAA 1 BBB 1
ccc| 2| DoD 4
EEE 4 FFF 4 GGc 5
Fig. 6.29

Array Representation of a Priority

Another way to maintain a
Queue
leve
priority queue in is to use a separate queuc
priority (or for each priority number). Each memory aray
such queue will appear in its
must have its
own pair of
pointers. FRONT and REAR. In fact, if each queue isow e d
llocatea the s
a
 Stacks, Queues, Recursion 6.43

space,
a a two-dimensional array QUEUE can be used instead of the linear arrays. Figure
two-di

of representation for the priority queue in Fig. 6.29. Observe that FRONT[K] and
tes t h i s representation
amount
63.0
indicales
respectively, the front and rear elements of row K of QUEUE, the row that
REARIK/ C o n t a i n ,

o felements with priority number K.

queue
maintains the
FRONT
REAR 2 3 5

2 AAA
2 BBB CCC XXX
2
0
FFF DDD EEE
4
4 GGG

Fig. 6.30o

of algorithms for deleting and clements in a priority queue

inserting
are outlines
The following
The
a two-dimensi1onal array QUEUE. as above.
The details of the
in memory by
hof is maintained exercises.
are lelt as
algorithms
the first element in a priority queue
Alporithm 6.19: This algorithm deletes and processes
maintained by a two-dimensional array
QUEUE.

1. Find the first nonempty queuc.]

Find the smallest K such that FRONT|KJ
NULL
front element in row K of QUEUE.
2. Delete and process the
3. Exit.
number M to a priority queue
ITEM with priority
Algorithm 6.20: This algorithm adds
an
two-dimensional array QUEUE.
maintained by a

row M of QUEUE.
the rear element in
1. Insert ITEM as

2. Exit.

Summary data structures for a

between different
Once again we see the ume-space tradeoff when choosing time-efficient than
the one-way
tin is more
given problem. The array ne
of priority queue
array representation a list, o n e must perform a linear
search on

HSt. This element to a one-way

more be
is
because may
wnet
when adding an of the priority queue
the list. Onu s e
the list representation
one-way the array representaion
for
ntation,

O n e r hand, in using
Space-
Overtlowef icient than the array
Ccurs
representation.

of elements in any
This is because

single priority
level
exceeds

total numb
the
imber
capacity
of clements

thtat level, but when the number

only when the ity level.

list. overflow
occurs

for each priorit,

in using he one-way list
ceds the total a l t e r n a t i v e is to
use a linked

capac
capacity. Another