# Class 30: Stacks and Their Implementation

Back to Class Cancelled. On to Project Discussion.

Held: Monday, 25 October 2004

Summary: Today we investigate the first important linear structure: The Stack. A stack collects objects and returns them in the reverse order that they were added.

Related Pages:

Assignments

Notes:

• Don't forget that you have project homework due tomorrow.

Overview:

• Collections.
• Linear structures.
• Implementing stacks.

## Collections

• One of the key topics of ADT design is the of collections: ADTs that group values together.
• Note that are a variety of ways we think about collecting values:
• We might organize them into a set, with a key operation of membership.
• We might organize them in the list, with a key operation of iteration (visiting each element).
• We might organize them in an array, with a key operation of access by position.
• You can think of other ways to organize values.
• Much of our focus these next few weeks will be on collections and how to implement them.

• Linear Structures are one of the simplest forms of collections.
• Linear structures typically provide two basic operations:
• `put`, add an element to the collection
• `get`, get an element from the collection, removing it from the collection
• Since `get` requires a non-empty collection, most collections provide an `isEmpty` predicate.
• You can think of linear structures as a form of "job jar" or "to do list".
• The choice of what `get` returns is up to the policy of the particular kind of linear structure.
• The Stack ADT uses a last in, first out (LIFO) policy.
• The Queue ADT uses a first in, first out (FIFO) policy.
• Priority queues use a best first policy. (They therefore need a way to determine what is best.)
• There are a few related operations that you may find helpful:
• `peek` returns the object to be returned by `get`, but without deleting it.
• `size` returns the number of elements in the structure.
• It might also be useful to have an `isFull` operation.
• Why might you argue for or against `isFull`?
• The individual operations traditionally have different names in the different types of linear structures.
• Why? The structures were invented first. Then someone realized they had a commonality. By that point, the names were ingrained.

## Stacks

• LIFO policy.
• LIFO mimics many common operations,
• What happens with procedure calls in most programming languages.
• The plates in a cafeteria.
• ...
• Naming is somewhat different (since stacks were designed before the general linear structures).
• `put` is typically called `push`.
• `get` is typically called `pop`.
• `peek` is typically called `top`.

## Implementing Stacks

• How do we implement stacks?
• One technique is to use partially-filled arrays.
• When we put something on the stack, we add it to the end of the filled section.
• When we pop something from the stack, we remove the last thing from the filled section.

Back to Class Cancelled. On to Project Discussion.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed Dec 8 10:37:20 2004.
The source to the document was last modified on Thu Aug 26 20:22:23 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2004F/Outlines/outline.30.html`.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu