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

SR 13.7 Suppose first is a reference to a Node object, and that it refers to the
first node in a linked list. Show, in pseudocode, the steps that would
count and return the number of nodes on the list.
SR 13.8 What is a doubly linked list?
SR 13.9 What is a header node for a linked list?

13.3 Linear Data Structures

In addition to lists, some data structures have become classic in that they repre-
sent important generic situations that commonly occur in computing. Like lists, a
queue and a stack are linear data structures , meaning that the data they represent
is organized in a linear fashion. This section explores some linear data structures
in more detail.

Queues
A queue is similar to a list except that it has restrictions on the way
you put items in and take items out. Specifically, a queue uses first-
in, first-out (FIFO) processing. That is, the first item put in the list is
the first item that comes out of the list. Figure 13.6 depicts the FIFO
processing of a queue.
Any waiting line is a queue. Think about a line of people waiting for a teller
at a bank. A customer enters the queue at the back and moves forward as earlier
customers are serviced. Eventually, each customer comes to the front of the queue
to be processed.
Note that the processing of a queue is conceptual. We may speak in terms of
people moving forward until they reach the front of the queue, but the reality
might be that the front of the queue moves as elements come off. That is, we are

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

Items go on the queue
at the rear (enqueue)

Items come off the queue
at the front (dequeue)

FIGURE 13.6 A queue data structure