**Summary:** We consider the essential features of
*stacks*, one of the forms of linear structures. We also consider
a straightforward implementation of stacks.

**Prerequisites:** Linear Structures, Arrays, Polymorphism,
Inheritance, Generics.

**Contents:**

- Stack Basics
- An Interface
- Applications of Stacks
- A Vector-Based Implementation of Stacks
- Terminology

Given your prior understanding of linear structures, you should
find that stacks are a
fairly simple abstract data type. Stacks are linear
structures that implement that *last in, first out*
policy. That is, the value returned by `get`

is
the value most recently added to the stack.

/** * A linear structure that follows the "last in, first out" policy. * * @author Samuel A. Rebelsky * @version 1.1 of March 2006 */publicinterfaceStack<T>extendsLinearStructure<T> {/** * Add an element to the stack. * * @param val * The object that is to be added. * @post * The stack now contains an additional copy of val. */publicvoidput(T val);/** * Remove the most-recently-added element that is still in the * stack. * * @return val * An object in the structure. * @pre * The structure is not empty. * @post * The structure contains one fewer copy of val. * @post * Every value in the stack was added less recently than val. */publicT get();/** * Determine which object will next be returned by get. * * @return val * An object in the stack * @pre * The structure is not empty. * @post * Every other value in the stack was added less recently than val. */publicT peek();/** * Determine if the stack is empty. */publicbooleanisEmpty(); } // interface Stack

One aspect of this code you may find of interest is that we have said
that `Stack<T> `

.
This extension is similar to the extension you've seen for classes,
although it is used primarily for polymorphism. It means that
you can use a __extends__ LinearStructure<T>`Stack`

whereever code expects a
`LinearStructure`

There are a variety of ways in which computer scientists use stacks. At times, they use them simply because they need some linear structure, and stacks are convenient to use. More frequently, they identify problems for which the last-in, first-out policy is particularly appropriate.

One such class of problems involves matching symbols, such as tags in an
HTML document or parens in a Scheme program. In essence, whenever you
see an opening symbol, such as `<b>`

in an HTML
document or `(`

in a Scheme program, you push it on the
stack. When you see a closing symbol, such as `</b>`

in an HTML document or `)`

in a Scheme program, you pop
the value on the stack and compare it to the closing symbol. If they
match, you continue on. If they fail to match, you report an error.
Clearly, if you encounter an end symbol with an empty stack, there's
something seriously wrong with the document or program. Similarly,
if the stack contains values at the end, there are also significant
problems, since not all opening symbols are matched.

Stacks are also useful for certain kinds of operations. For example,
some mathematicians like to use *reverse polish notation* (RPN), in
which the operation follows the operands. In such a system, we would
write add 2 and the product of 3 and 7

as
`2 3 7 * +`

. RPN is useful because you don't have to worry
about precedence rules. RPN is also very easy to implement using stacks.

- Whenever you encounter a value, you push it.
- Whenever you encounter an operation, pop the parameters and push the result.
- The value on the top of the stack when you are done is the final result.

It is also fairly easy to implement stacks, at least once we have another
data structure, such as a vector. In a vector-based implementation of
stacks, we typically store the values as they come in, starting at index 0.
When we pop a value, we use the index of the last value added and decrease
that value. (Typically, we use a field called `top`

to keep
track of where to add values, but we might also use the size of the
vector.)

When we create the stack, we need to initialize the two fields.

publicVectorBasedStack() {this.top = 0;this.contents =newVector<T>(); } // VectorBasedStack()

or

publicArrayBasedStack() {this.size = 0;this.stuff =newObject[10]; } // ArrayBasedStack()

Given that strategy, here's the basic code for `put`

in `VectorBasedStack`

.

this.contents.put(this.top, newvalue);this.top++;

The `put`

operation is similar for an `ArrayBasedStack`

, provided we know that the put is safe.

this.stuff[this.size] = newvalue;this.size++;

It is equally easy to get the value at the top of the stack: We just reverse those two steps.

this.top--;returnthis.contents.get(this.top);

or

this.size--;return(T)this.stuff[this.top];

Note that we need to *cast* the return value because of a design
issue in Java that prevents us from creating arrays whose base type is
a type parameter.

However, it is also better

to clear out the cell in the
vector when we delete a value. Hence, we will need to temporarily store
the value to be returned before clearing the cell and then returning
that value.

this.top--; T returnme =this.contents.get(this.top);this.contents.set(this.top,null);this.contents.setSize(this.top);returnreturnme;

or

this.size--; Object returnme =this.stuff[this.size];this.contents[this.size] =null;return(T) returnme;

Determining whether or not the stack is empty is also easy: The stack
is empty only when `top`

is 0.

The only hard part is what to do when the stack fills

. If
we use arrays to implement the stack, we would need to
do something clever, like make a bigger array and copy the values over.
If we use vectors, the stack automatically expands.

Unfortunately, some bright computer scientist designed the stack
before some other bright computer scientist designed the more general
linear structure. Hence, the terms that many folks use for the
basic stack operations are not `put`

and `get`

,
but rather `push`

and `pop`

.

To make our code more usable, we will stick with the linear structure terms.

Sunday, 6 March 2005 [Samuel A. Rebelsky]

- Created.

Tuesday, 7 March 2006 [Samuel A. Rebelsky]

- Updated for parameterized types.
- Updated to show both vector and array implementations.
- Minor edits.

This page was generated by
Siteweaver on Tue Mar 7 12:50:54 2006.

The source to the page was last modified on Tue Mar 7 12:50:51 2006.

This page may be found at `http://www.cs.grinnell.edu/~rebelsky/TAO/Readings/stacks.html`

.

You may wish to validate this page's HTML ; ; Check with Bobby

rebelsky@grinnell.edu