Stack Implementations - Data Structures and Abstractions with Java - page 137

Chapter

6

Stack
Implementations

Contents
A Linked Implementation
An Array-Based Implementation
A Vector-Based Implementation
Java Class Library: The Class Vector
Using a Vector to Implement the ADT Stack

Prerequisites
Chapter 2 Bag Implementations That Use Arrays

Chapter 3 A Bag Implementation That Links Data

Chapter 4 The Efficiency of Algorithms

Chapter 5 Stacks

Objectives
After studying this chapter, you should be able to
●

Implement the ADT stack by using either a linked chain, an array, or a vector

Compare and contrast the various implementations and their performance

●

T wo of the implementations of the ADT stack described in this chapter use
techniques like the ones we used to implement the ADT bag. We will use, in turn, a
chain of linked nodes and an array to store the stack's entries. We also will introduce
the standard class Vector as a part of the Java Class Library and use an instance of
Vector to represent a stack. You should be pleasantly surprised by the simplicity and
efficiency of these implementations.

A Linked Implementation

6.1

Each of the operations push , pop , and peek of the ADT stack involve the top of
the stack. If we use a chain of linked nodes to implement a stack, where in the
chain should we place the stack's top entry? If we have only the chain's head