Lecture Notes for Computer Algorithms I

4 November 2003 - Stacks

1. Linked list access is cheap only at the ends.

   1. Restrict access to linked-list ends an maybe get better (more efficient, simpler) data structures.

   2. You have two choices: restrict to one end, or to both ends.

   3. We'll consider the one-end case here; the two-end case later.

2. Four problems.

   1. In a card game, how do you represent the discard pile?

      1. The most recent card discarded should be the card that can be picked up.

   2. How can I reverse a train at a terminus?

      1. A turntable's expensive, a loop's cheaper but inflexible

   3. Keeping track of function call information.

      1. The most recent call frame is the one that should be accessed.

   4. right-to-left conversion on left-to-right data.

      1. Converting bases is easy (right digit order) but hard (what's the divisor) in one direction and hard (wrong digit order) but easy (the divisor's the base) in the other direction.

3. Stacks

   1. A stack is a linked list in which access to the list is restricted to one end.

      1. Given the data access patterns, a stacks is also known as a last in first out queue or a LIFO queue.

   2. Operations

      1. Make an empty stack.

      2. Test for an empty stack.

      3. Add an element to the stack (push).

      4. Remove an element from the stack (pop).

         1. pop() may or may not return the element removed from the stack.

      5. Return the value at the top of the stack (top).

      6. There are many other stack operations available. See the Forth or PostScript instruction sets for examples.

   3. Error states.

      1. You can't pop from an empty stack - stack underflow.

      2. Depending on implementation, you can't push into a full stack - stack overflow.

4. The four problems revisited.

   1. In a card game, how do you represent the discard pile?

      1. The discard pile can be implemented with a stack.

   2. How can I reverse a train at a terminus?

      1. A shunt can turn the train around flexibly.

      2. The shunt acts like a stack.

   3. Keeping track of function call information.

      1. The call frames can be stored on a stack.

   4. right-to-left conversion on left-to-right data.

      1. Convert the number from right-to-left, storing the digits in a stack.

5. The two prime properties of a stack are:

   1. Provides access to the most recently entered value (discard piles and call frames).

   2. Offers up values in reverse order (train shunt and conversion digits).

   3. When you have a problem requiring either of these two properties (access to most recent values, reversing the order of values), you should think "stack".

This page last modified on 13 November 2003.