Java Reference
In-Depth Information
In spite of our examples of a stack, everyday life usually does not follow this
last-in
,
first-out
,
or
LIFO
, behavior. Although the employee hired most recently is often the first one fired during a
layoff, we live in a first-come, first-served society. In the computer science world, however, last-in,
first-out is exactly the behavior required by many important algorithms. These algorithms often use
the abstract data type stack, which is an ADT that exhibits a last-in, first-out behavior. For example,
a compiler uses a stack to interpret the meaning of an algebraic expression, and a run-time environ-
ment uses a stack when executing a recursive method.
This chapter describes the ADT stack and provides several examples of its use.
VideoNote
The ADT stack
5.1
The ADT
stack
organizes its entries according to the order in which they were added. All additions
are to one end of the stack called the
top
. The
top entry
—that is, the entry at the top—is thus the
newest item among the items currently in a stack. Figure 5-1 shows some stacks that should be
familiar to you.
FIGURE 5-1
Some familiar stacks
Note:
Among the items currently in a stack, the one added most recently is at the top of the
stack. (Other items might have been added to the stack more recently and then removed.)
The stack restricts access to its entries. A client can look at or remove only the top entry. The
only way to look at an entry that is not at the top of the stack is to repeatedly remove items from the
stack until the desired item reaches the top. If you were to remove all of a stack's entries, one by
one, you would get them in reverse chronological order, beginning with the most recent and ending
with the first item added to the stack.
5.2
The operation that adds an entry to a stack is traditionally called
push
. The remove operation is
pop
.
The operation that retrieves the top entry without removing it is named
peek
. Typically, you cannot
search a stack
1
for a particular entry. The following specifications define a set of operations for the
ADT stack.
1. However, the Java Class Library has a class of stacks that does define a search method, as you will see later in
this chapter.
