Java Reference
In-Depth Information
Display 15.30
Demonstration of the
Queue
Class
1
public
class
QueueDemo
2{
3
public
static
void
main(String[] args)
4
{
5
Queue q =
new
Queue( );
6
q.addToBack("Tom");
Items come out of the queue in
the same order that they went
into the queue.
7
q.addToBack("Dick");
8
q.addToBack("Harriet");
9
while
(!q.isEmpty( ))
10
{
11
System.out.println(q.whoIsNext( ));
12
q.removeFront( );
13
}
14
System.out.println("The queue is empty.");
15
}
16
}
Sample Dialogue
Tom
Dick
Harriet
The queue is empty.
Items come out of the queue in
the same order that they went
into the queue.
In order to have some terminology to discuss the efficiency of our
Queue
class and
linked list algorithms, we first present some background on how the efficiency of algo-
rithms is usually measured.
Running Times and Big-
O
Notation
If you ask a programmer how fast his or her program is, you might expect an answer like
“two seconds.” However, the speed of a program cannot be given by a single number. A
program will typically take a longer amount of time on larger inputs than it will on smaller
inputs. You would expect that a program for sorting numbers would take less time to sort
ten numbers than it would to sort one thousand numbers. Perhaps it takes two seconds to
sort ten numbers, but ten seconds to sort one thousand numbers. How, then, should the
programmer answer the question “How fast is your program?” The programmer would
have to give a table of values showing how long the program took for different sizes of
input. For example, the table might be as shown in Display 15.31. This table does not give
a single time, but instead gives different times for a variety of different input sizes.
