cs230 Lecture Notes
Week 6, Monday

Homework 4 is due on Tuesday in lab.

Homework 5 will be handed out in lab and is due next Monday.

For Thursday, please read Chapter 15 and prepare for a quiz.

Also, please read the solutions to Homework 3.  I demonstrate
some techniques there that I want you to see.

I will hand back and go over the exams on Thursday.


What is an ADT?
---------------

Abstract data type.

   A definition of a data structure that specifies the
   interface but not the implementation.

   Interface = set of methods, their parameters and return
               values, and their semantics

   Implementation = the bodies of those method

A class definition is a concrete data type.

   It specifies an 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

empty: return boolean, true if the stack is empty


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 + " ");
    }

As an exercise, encapsulate this code in a method called
printBackwards.

Compare this version of printBackwards to the recursive version.