Ch.6

Question 1

A [s..k] is a collection of objects that are inserted and removed according to the
[l..t-..n, f..t-o..t] (LIFO) principle. A user may insert objects into a stack at any time, but may only access or remove the most recently inserted object that remains
(at the so-called “top” of the stack). The name “stack” is derived from the metaphor
of a stack of plates in a spring-loaded, cafeteria plate dispenser. In this case, the
fundamental operations involve the “pushing” and “popping” of plates on the stack.
When we need a new plate from the dispenser, we “pop” the top plate off the stack,
and when we add a plate, we “push” it down on the stack to become the new top
plate. Perhaps an even more amusing example is a PEZ® candy dispenser, which…

Answer 1

[stack][last in, first out] 226

Question 2

…228 Chapter 6. Stacks, Queues, and Deques
A Stack Interface in Java
In order to formalize our abstraction of a stack, we define what is known as its [a..n p..g i..e] (API) in the form of a Java [i..e], which describes the names of the methods that the ADT supports and how they are to be
declared and used. This interface is defined in Code Fragment 6.1. We rely on Java’s [g..s f..k] (described in Section 2.5.2), allowing
the elements stored in the stack to belong to any object type . For example,
a variable representing a stack of integers could be declared with type Stack. The formal type parameter is used as the parameter type for
the push method, and the return type for both pop and top.
Recall, from the discussion of Java interfaces in Section 2.3.1, that the interface
serves as a type definition but that it cannot be directly instantiated. For the ADT…

Answer 2

[application programmer interface][interface][generics framework] 228

Question 3

The assignment to [n..l] was not technically required,
as our stack would still operate correctly without it.
Our reason for returning the cell to a null reference is to assist Java’s [g..e] collection mechanism, which searches memory for objects that are no longer actively
referenced and reclaims their space for future use. (For more details, see section…

Answer 3

[null][garbage] 232

Question 4

The Adapter Pattern
The [a..r] design pattern applies to any context where we effectively want to modify an existing class so that its methods match those of a related, but different, class or interface. One general way to apply the adapter pattern is to define a new class in such a way that it contains an instance...

Answer 4

[adapter] 233

Question 5

Such a structure is called a [d..e-
e..d q..e], or [d..e], which is usually pronounced “deck” to avoid confusion with the dequeue method of the regular queue ADT, which is pronounced like the
abbreviation “D.Q.”
The deque abstract data type is more general than both the stack and the queue
ADTs. The extra generality can be useful in some applications. For example, we
described a restaurant using a …

Answer 5

[double-ended deque][deque] 248

Question 6

6.3. Double-Ended Queues 249
1 /**
2 * Interface for a double-ended queue: a collection of elements that can be inserted
3 * and removed at both ends; this interface is a simplified version of java.util.Deque.
4 */
5 [p..c i..e] Deque 6 /** Returns the number of elements in the deque. */
7 [i..t] size( );
8 /** Tests whether the deque is empty. */
9 b..n isEmpty( );
10 /** Returns, but does not remove, the first element of the deque (null if empty). */
11 E first( );
12 /** Returns, but does not remove, the last element of the deque (null if empty). */
13 E last( );
14 /** Inserts an element at the front of the deque. */
15 [v..d] addFirst(E e);
16 /** Inserts an element at the back of the deque. */
17 [v..d] addLast(E e);
18 /** Removes and returns the first element of the deque (null if empty). */
19 E removeFirst( );
20 /** Removes and returns the last element of the deque (null if empty). */
21 E removeLast( );
22 Code Fragment 6.14: A Java interface, Deque, describing the double-ended queue
ADT. Note the use of the generic parameterized type, E, allowing a deque to contain
elements of any specified class.
Example 6.5: The following table shows a series of operations and their effects
on an initially empty deque D of integers.

Answer 6

[public interface][int][void][void] 249