CSC152 2005F, Class 40: Stacks

Admin
* Questions on the exam?
* Enjoy the soccer game
* (Thanks for the good wishes on my health)

Overview:
* Linear structures, revisited
* Stacks
* A stack interface
* A stack implementation

Exam questions
* How do you return null?

        if (pos > stuff.size()) {
          return null;
        }
* Do we need an expandablearray for problem 2?
  * Not, it just may make your life easier
* How big should the array be?
  It need be no bigger than starting-price+1

Building random linear structures with vectors
* Goal: Hard to predict what value you get back
* Strategy: Store values in a vector
  Add: Put the new element at the end
  Get: Pick a random valid index, 
       Remember the value at that index
       Move the last value to that place (shortening the vector)

Stacks
* Philosophy: Linear structures with LIFO policy
* Applications: 
  * Model stacks of plates in a cafeteria
  * Model function calls ; Eliminate recursion
  * Interesting "to do" model
* Methods:
  * The same methods as linear structures
  * Historical artificat: Stacks designed *before* linear structures
    * traditionally "push" and "pop"
    * also "peek"
* Implementation
  * Using a Vector
    * put: use add (to the end of the vector)
    * get: grab and remove the last thing in the vector
    * peek: return the last thing in the vector w/o removing it