cs230 Lecture Notes
Week 6 Wednesday which is Monday

Lessons from Homework 3 resumed (see notes13.txt)

Homework 4 Hints

1) use character arithmetic to make the histogram (Appendix A.7)

2) use substring to implement middle

3) use toLowerCase to handle cases

   See String documentation for both

   print Stack documentation while you're there.

   and StringTokenizer

4) proof of correctness for countChange

5) fibonacci



Chapter 8: stacks
-----------------


Data structure
--------------

Usually a collection of something.

Arrays, lists, strings.

Each one has a set of operations we can perform.

Different names, slightly different semantics.


Abstract data type
------------------

Also a collection of things, often generic.

     (example, array of int, Stack of Object)

A set of operations defines the ADT

Usually there are many ways we might implement those operations,
	some more efficiently than others.

Fundamental goals

1) versatile libraries: write applications using ADTs, programming
   environment provides implementations of ADTs

2) facilitate alternative representation: write the application once
   and test it with several implementation


Definition of the stack ADT
---------------------------

push: add something new to the stack

pop:  remove one thing from the stack, always the most recent entry

Why is this a common, useful abstraction?

1) fundamental to the implementation of the run-time stack, the
   instantiation of methods

2) fundamental to many algorithms for parsing formal languages
   (interpreting expressions)


The built-in Java Stack implementation
--------------------------------------

Stack implementation is generic (we can put in any kind of
Object).  There are other ways to make generic data types---
this is one.

don't forget

    import java.util.Stack;

constructor

    Stack stack = new Stack ();

check

    System.out.println (stack.empty ());

push the nodes of a list

    for (Node node = list.head; node != null; node = node.next) {
        stack.push (node);
    }

    implicit type conversion!

pop a single node

    Object obj = stack.pop ();
    Node node = (Node) obj;
    System.out.println (obj);

    careful: ClassCastException

pop all the nodes

    while (!stack.empty ()) {
        Node node = (Node) stack.pop ();
        System.out.print (node + " ");
    }

    Compare printBackwards and the stack version.