Stacks and queues - Data Structures and Problem Solving Using Java - page 595

chapter 16

stacks and queues

I n this chapter we discuss implementation of the stack and queue data struc-
tures. Recall from Chapter 6 that the basic operations are expected to take con-
stant time. For both the stack and queue, there are two basic ways to arrange for
constant-time operations. The first is to store the items contiguously in an array,
and the second is to store items noncontiguously in a linked list. We present
implementations for both data structures, using both methods, in this chapter.
In this chapter, we show

An array-based implementation of the stack and queue

n

A linked list-based implementation of the stack and queue

n

A brief comparison of the two methods

n

An illustration of Collections API stack implementation

n

dynamic array implementations

16.1

In this section we use a simple array to implement the stack and queue. The
resulting algorithms are extremely efficient and also are simple to code. Recall
that we have been using ArrayList instead of arrays. The add method of ArrayList