CS 455 Lecture Notes

Week Ten, Tuesday: Stacks

Introduction to Stacks

A stack is a data structure with many commonly occurring physical counterparts. For example, if one has an in-basket on one's desk, and to-do assignments are placed in the basket from the top as they are received, when one takes an assignment from the in-basket (from the top), it's the last one in (most recent), not the first one in (oldest). Hence a stack will maintain the order of reverse priority.

Stacks have a number of applications in computer science and programming. Stacks also form the basis for some computing machine components, and operating systems utilize stacks when running programs.

One of the oldest uses for a stack is in theoretical computer science. The simplest machines are called "finite control" or "finite state" machines. These simple machines have a set of states (and a set of rules for changing states) but no memory. Finite controls have many uses, but are quite limited in their computational capability. The simplest form of memory to add to a finite state machine is stack memory. A finite control with stack memory is called a "pushdown automaton."

Pushdown automota have the power to recognize a class of languages called "context free grammars." Hence, stacks have application in compilers, as we will see in some examples.

Stack Applications

This page established November 2, 1999; last updated November 2, 1999.