Java Reference
In-Depth Information
What makes data structures such as stacks and queues interesting is that they combine
storage for information with the methods that access that information. Thus, stacks and
queues are
data engines
in which storage and retrieval are provided by the data structure
itself, not manually by your program. Such a combination is, obviously, an excellent choice
for a class, and in this project you will create a simple queue class.
In general, queues support two basic operations: put and get. Each put operation places
a new element on the end of the queue. Each get operation retrieves the next element from
the front of the queue. Queue operations are
consumptive
: once an element has been re-
trieved, it cannot be retrieved again. The queue can also become full, if there is no space
available to store an item, and it can become empty, if all of the elements have been re-
moved.
One last point: There are two basic types of queues—circular and noncircular. A
circular
queue
reuses locations in the underlying array when elements are removed. A
noncircular
queue
does not reuse locations and eventually becomes exhausted. For the sake of simpli-
city, this example creates a noncircular queue, but with a little thought and effort, you can
easily transform it into a circular queue.
1.
Create a file called
QDemo.java
.
2.
Although there are other ways to support a queue, the method we will use is based
upon an array. That is, an array will provide the storage for the items put into the
queue. This array will be accessed through two indices. The
put
index determines
where the next element of data will be stored. The
get
index indicates at what loca-
tion the next element of data will be obtained. Keep in mind that the get operation is
consumptive, and it is not possible to retrieve the same element twice. Although the
queue that we will be creating stores characters, the same logic can be used to store
any type of object. Begin creating the
Queue
class with these lines:
3.
The constructor for the
Queue
class creates a queue of a given size. Here is the
Queue
constructor:
Notice that the put and get indices are initially set to zero.
