Java Reference
In-Depth Information
4.3.3
Comparison of Array-Based and Linked Queues
All member functions for both the array-based and linked queue implementations
require constant time. The space comparison issues are the same as for the equiva-
lent stack implementations. Unlike the array-based stack implementation, there is
no convenient way to store two queues in the same array, unless items are always
transferred directly from one queue to the other.
4.4
Dictionaries
The most common objective of computer programs is to store and retrieve data.
Much of this topic is about efficient ways to organize collections of data records
so that they can be stored and retrieved quickly. In this section we describe a
simple interface for such a collection, called a dictionary. The dictionary ADT
provides operations for storing records, finding records, and removing records from
the collection.
This ADT gives us a standard basis for comparing various data
structures.
Before we can discuss the interface for a dictionary, we must first define the
concepts of a key and comparable objects. If we want to search for a given record
in a database, how should we describe what we are looking for? A database record
could simply be a number, or it could be quite complicated, such as a payroll record
with many fields of varying types. We do not want to describe what we are looking
for by detailing and matching the entire contents of the record. If we knew every-
thing about the record already, we probably would not need to look for it. Instead,
we typically define what record we want in terms of a key value. For example, if
searching for payroll records, we might wish to search for the record that matches
a particular ID number. In this example the ID number is the search key.
To implement the search function, we require that keys be comparable. At a
minimum, we must be able to take two keys and reliably determine whether they
are equal or not. That is enough to enable a sequential search through a database
of records and find one that matches a given key. However, we typically would
like for the keys to define a total order (see Section 2.1), which means that we
can tell which of two keys is greater than the other. Using key types with total
orderings gives the database implementor the opportunity to organize a collection
of records in a way that makes searching more efficient. An example is storing the
records in sorted order in an array, which permits a binary search. Fortunately, in
practice most fields of most records consist of simple data types with natural total
orders. For example, integers, floats, doubles, and character strings all are totally
ordered. Ordering fields that are naturally multi-dimensional, such as a point in two
or three dimensions, present special opportunities if we wish to take advantage of
their multidimensional nature. This problem is addressed in Section 13.3.
