CSC152 2004F, Class 30: Stacks

Admin:
* I hope you had a good break.
* Due tomorrow: Reflections on design.
* Due Wednesday: Finish today's coding.
* Exam to be distributed Wednesday or Friday.

Overview:
* Collections
* Linear Structures
* Stacks
* Implementing Stacks

/Reminder: Key topic in 152 is Abstract Data Types (ADTs)/

* What is an abstract data type?
  * A way to organize information.
* Distinguished from data structures in that we care about *what*, not *how*
* Typical things we talk about:
  * Name
  * Overriding philosophy
  * Key methods
* Example
  * Name: Array
  * Overriding philosophy: A collection of values which you access by an index number/position
  * Key methods: put-value-at(i,Value), get-value-at(i), length

/Note: Most ADTS collect values/

* Arrays: Collection of values indexed by number.
* Sets: Collections of values in which membership is the most important operation
  * Add x,
  * Add y
  * Add z
  * Does my set contain q?
  * Other important operations: intersect, union
* Lists: Collections of values which you visit element by element
* Maps: Collections of values indexed by other objects.
* Many more

/Linear Structures: A Simple Collection ADT/

* Philosophy: We add things and get things.
* Different policies for what you get:
  * Random
  * Most-important-first
  * First in, first out (FIFO)
  * Last in, first out (LIFO)
* Each policy leads to a different ADT
* Different policies are useful in different situations
  * FIFO models what happens in most lines (e.g., at a store)
  * LIFO models the calling structure of most programming languages
  * LIFO also models the stacks of plates in most dining halls
* What methods should "Linear" contain?
  * add something to the collection
  * get something from the collection (the policy determines what you get)
  * how many things are in the collection?
  * is it empty? - to meet preconditions for get
* If we phrase them in Java
	public void put(Object thingToAdd)
	public Object get()
	public boolean isEmpty()
	public long size()

Once we've designed an interface, what should we do next?
* Implement it (build the data structure)
* Write the test suite

/Stacks: Linear Structures with a LIFO policy/

* Operations?
  * The same operations as Linear, just the meaning changes (slightly)

/How can we implement stacks?/

* Traditional answer: Using something else we already know.
* We know arrays!
* Add objects in the first unused index
* Keep track of index of highest added object
* Find the last object at that index

/Problems/

* Our stacks can fill up.  When they fill up, the program crashes.
* Solutions?
  * The hard solution: Make a new bigger array and copy over values.
    * Homework for Wednesday
    * How much bigger?  How about twice as big.
  * The easy solution: Add an isFull method and make it a precondition that the stack isn't full.

/Back to Arrays/

* Why doesn't Java give you variable-size arrays?  Because these then can overwrite memory used for other purposes.
* Competent programmers can build a bigger array and copy.
* Less competent programmers can use java.util.Vector, which does that copying for you.

/Our next ADT: The Queue/

* Linear structures with a FIFO policy.
* Can we implement queues with arrays?
  * Keep track of both highest and lowest indices.
  * When you add, add after the highest.
  * When you get, use the lowest and increment.
* Can we use less space?
  * See next class.

/Fun with Prospies/

* Vincent from Iowa City
* My parents made me visit Grinnell
* Senior
* Iowa, Berkeley, USC, Princeton
  * We're snobby about not being snobby
  * Our endowment may be smaller than Princeton's, but we have fewer students (our per-capita is higher)
  * Likely to have larger classes at Grinnell
  * Back table beats eating clubs any day