IMPLEMENTING LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 921

Pedagogical Note
For an interactive demo on how stacks and queues work, go to www.cs.armstrong.edu/
liang/animation/web/Stack.html , and www.cs.armstrong.edu/liang/animation/web/Queue.html , as
shown in Figure 24.20.

stack and queue animation on
Companion Website

(a) Stack animation (b) Queue animation

F IGURE 24.20

The animation tool enables you to see how stacks and queues work.

Since the insertion and deletion operations on a stack are made only at the end of the stack,
it is more efficient to implement a stack with an array list than a linked list. Since deletions are
made at the beginning of the list, it is more efficient to implement a queue using a linked list
than an array list. This section implements a stack class using an array list and a queue class
using a linked list.
There are two ways to design the stack and queue classes:

Using inheritance: You can define a stack class by extending ArrayList , and a
queue class by extending LinkedList , as shown in Figure 24.21a.

■

inheritance

Using composition: You can define an array list as a data field in the stack class, and
a linked list as a data field in the queue class, as shown in Figure 24.21b.

composition ■

ArrayList GenericStack LinkedList GenericQueue

(a) Using inheritance

GenericStack ArrayList GenericQueue LinkedList

(b) Using composition

F IGURE 24.21

GenericStack and GenericQueue may be implemented using inheritance
or composition.

Both designs are fine, but using composition is better because it enables you to define a com-
pletely new stack class and queue class without inheriting the unnecessary and inappropriate
methods from the array list and linked list. The implementation of the stack class using the com-
position approach was given in Listing 19.1, GenericStack.java. Listing 24.7 implements the
GenericQueue class using the composition approach. Figure 24.22 shows the UML of the class.