CS231 lecture notes, Fall 1999
Week 6, Wednesday  through Week 7, Monday

Reading: Standish Chapter 6

Linear Data Structures
----------------------

All data structures we have seen so far are kinds of sets.

Strictly, the elements of a set are unordered.

All the implementations we have seen are ordered somehow,
although the ordering may not reflect anything useful
(e.g. array implementation of PQ, where the array indices
are meaningless).

What are the other properties of a set implementation?

1) size limit, or automatic resizing?

   a) does resizing require copying?

2) constant time access or variable time?

3) can the same element be in the set more than once,
   and if so, what do we mean by same?

4) are the elements stored contiguously in memory, or linked?

5) are the elements indexed?

Based on the introduction to Chapter 6, a LINEAR DATA STRUCTURE
appears to be one that grows automatically, and in which the
elements are indexed.  I don't think this is a particularly useful
category, so I think we should move on to talk about Stacks.

Stacks
------

The set of allowable operations is:

1) create an empty stack
2) check whether the stack is empty
   a) why not check the size, like a PQ?
3) push (add something to the stack)
4) pop (remove something from stack)

and sometimes

5) peek (look at the top of the stack without removing it).

Is peek necessary, or could we implement it externally?

What happens if we pop or peek and empty stack?

     EmptyStackException  (how did I find out?)

What happens if we put null into a stack?

     How did I find out?

    Stack stack = new Stack ();
    stack.push ((Object) root);
    stack.push (null);
    stack.push (null);
    root = (Tree) stack.pop ();
    root = (Tree) stack.pop ();
    root = (Tree) stack.pop ();
    System.out.println (root);
     
LIFO discipline: last in, first out.

Called stacks because of similarity to real-world stack in which
adding and removing things in the middle is hard.

Any object can be added to a Stack; no need for comparability.

Uses for stacks:

1) processing nested structure, like matching parentheses

   broader example: context-free grammars and push-down automata

2) searching and backtracking

   see multiple paths, choose one and push rest onto stack.
   hit dead-end; pop something off the stack

3) in conversation, people often maintain an informal stack of
   topics.

4) performing complex tasks, need to keep a stack of goals and
   subgoals.

	Ham and cheese sandwich

	1) two slices of bread

	2) get ham

	   a) get pig
           b) kill it

                  i) hit pig with rock
                  ii) repeat until pig stops moving

           c) drain blood from pig
           d) cut off and cook two slices
           e) discard pig

        3) get cheese

	   a) get cow...


Point of potential confusion: don't confuse the Stack ADT
with the Run-time stack, which is sometimes called the Stack.

1) the RT stack keeps track of which methods have invoked
   which other methods (it is a stack of frames or activation
   records).

2) a Stack can contain anything (including nulls)

Sometimes you can use your own stack to speed up recursive
implementations by making them iterative:

  public static int totalTree2 (Tree root) {
    Stack stack = new Stack ();
    if (root != null) stack.push ((Object) root);
    Tree tree;
    int total = 0;

    while (!stack.empty()) {
      tree = (Tree) stack.pop ();
      // how do I know the popped item is not null?
      total += tree.value;
      if (tree.right != null) stack.push ((Object) tree.right);
      if (tree.left != null) stack.push ((Object) tree.left);
    }
    return total;
  }

But it is generally not a good idea, since the performance
improvement is likely to be small, and the iterative version
is much more difficult to prove correct.


Program development planning
----------------------------

Identify intermediate steps between what you have and what you
want.

Each step should be a small change from its predecessor.

Legal moves:

1) add code that tests the basic function of a new feature
   (like a Stack)

2) add code that implements a simple new feature

3) encapsulate existing code in a method and invoke it

4) generalize existing code by replacing constants with
   variables

5) make syntactic transformations

Ideally, you shouldn't have to add more than a few lines of
code at a time.

Compile, run, and debug the program after every change.

If you can't get it to compile and run, it is almost always
a bad idea to try to move on to something else and come back.

Things to do when you get stuck:

1) make dead certain that the code you are looking at is
   the code you are compiling and running

2) go away and thing about something else for a while

3) go back and "clean up" the code you have that is working.
   Experiment with different ways of doing the things you
   are already doing.  You might improve the program, you
   might get insight into the problem, you might solve the
   problem, or you might make the problem go away altogether.

4) analyze the code you have.  Add comment enumerating
   preconditions and invariants.  Add code that checks
   preconditions.