Java Reference
In-Depth Information
8.2.3 An application of queues: Set enumeration
As a basic straightforward application of queues, consider the following
mathematical puzzle:
Let
A⊂
N
be a set of integers such that:
-
1 belongs to
A
,and
-
If element
a
belongs to
A
, then 2
a
+1and 3
a
also belong to
A
.
For a given
n
, we are asked to display all integers less or equal to
n
that belong
to
. To solve this problem algorithmically, consider starting with a queue
initialized with element 1. We also use a boolean array to indicate whether
integer
a
belongs to
A
by tagging them
using a boolean array. Initially, all elements except 1 are marked to
false
. Once
this initialization is completed, for each element
a
of the queue, we perform in
turn the following process:
A
or not. That is, we mark elements of
A
-
Compute 2
a
+ 1, add this element to the queue if
a
is less than
n and
not
yet marked,
-
Compute 3
a
, add this element to the queue if
a
is less than
n and
not yet
marked.
The algorithm terminates when the queue becomes empty, and we terminate
by displaying all marked elements: the set
A
restricted to integers less or equal
to
n
.
The listing below describes this simple application of queues:
Program 8.2
Enumerating set elements using queues
class
QueueIntGame
final static int
n=1000;
static int
lastProcessed=
−
1;
static int
freePlace=0;
static int
[] container=
new i n t
[n];
static boolean
[] mark=
new boolean
[n];
static void
add(
int
a)
{
if
(freePlace
<
n)
{
container [ freePlace]=a;
freePlace++;
}
}
static boolean
Empty ( )
{
return
(( freePlace
−
lastProcessed )==1);
}
static void
process ()
Search WWH ::
Custom Search