CSC152 2006S, Class 27: Stacks

Admin:
* Eryn teaches Friday
* No class Monday
* Reading on Queues for Friday
* Homework on Stacks for Tuesday
* Alternate way to start Eclipse
  /home/rebelsky/bin/eclipse &

Overview:
* ADTs
* Linear Structures
* Stacks
* Lab

Abstract Data Types
* Way to organize data / information
* Example integers
* Can focus on the values
  0 is an integer
  1 is an integer
  2 is an integer
  3 is an integer
  ...
* Can focus on rules to produce the values
  0 is an integer
  if i is an integer, i+1 is an integer // recursive def'n
  if i is an integer, -i is an integer
* Can focus on what we want to do with the values
  * integers are things we can add, subtract, and multiply
* In CSC152, we will generally focus on "what to do with values"
  * And then how
* Four issues for ADTs
  * P - Philosophy: How are we organizing the data
  * A - Applications: How do we use the structure
  * M - Methods: What methods support P and A
  * I - Implemention(s): How do we build the thing

/Linear Structures/

* Common activity: Group data (e.g., list, vector, tree, file)
* Our goal: Design those ADTs carefully
  * Mixture of "Sam suggests, you reflect" and "You design"
* Linear Structures: Very general collection
  * Philosophy: Simple way to collect data
  * Methods: Add something to the collection, Get something from the collection, Check if you can get something (isEmpty)
  * Applications: To do list, Job jar, Calling on students in class
* Issue: What protocol/policy guides what "get" means
  * FIFO - Queue (Friday)
  * LIFO - Stacks (Today)
  * Random - Random (???)
  * Priority - Priority Queues

/How do we implement?/

* Strategy one: Using arrays