Collections - Java Software Solutions: Foundations of Program Design - page 628

not concerned at this point with whether the queue of customers moves toward
the teller, or remains stationary as the teller moves when customers are serviced.
A queue data structure typically has the following operations:

VideoNote

Implementing a queue.

enqueue—adds an item to the rear of the queue

■

dequeue—removes an item from the front of the queue

■

empty—returns true if the queue is empty ■

Stacks

A stack is similar to a queue except that its elements go on and come
off at the same end. The last item to go on a stack is the first item
to come off, like a stack of plates in the cupboard or a stack of hay
bales in the barn. A stack, therefore, processes information in a last-
in, first-out (LIFO) manner, as shown in Figure 13.7.
A typical stack ADT contains the following operations:

KEY CONCEPT
A stack is a linear data structure that
manages data in a last-in, first-out
manner.

■ push—pushes an item onto the top of the stack
■ pop—removes an item from the top of the stack
■ peek—retrieves information from the top item of the stack without remov-
ing it
■ empty—returns true if the stack is empty
The java.util package of the API contains a class called Stack that imple-
ments a stack data structure. It contains methods that correspond to the standard
stack operations, plus a method that searches for a particular object in the stack.
The Stack class has a search method that returns an integer corresponding
to the position in the stack of the particular object. This type of searching is not
usually considered to be part of the classic stack ADT.

The last item to go
on the stack (push)

must be the first item
to come off (pop)

FIGURE 13.7 A stack data structure