Outline

reasoning about programs

a precondition must be true before a method is called
the code in the method may (and usually will) assume that the precondition is true
the caller of a method must guarantee (be sure) that the precondition holds
a postcondition will be true after a method is called
the code in the method must guarantee that the postcondition is true
preconditions and postconditions are a little bit like a contract or any other agreement: if the caller provides the preconditions, the method will provide the postconditions
preconditions and postconditions are documented in Javadoc
invariants are postconditions of every method, including the constructors
invariants are preconditions of every method except the constructors
invariants are usually documented for the entire class rather than for each method

stacks of dishes or trays in a cafeteria
on a spring-loaded mechanism so only the top one is accessible
adding more dishes pushes down the stack, so only the new top is still accessible
Last In First Out discipline (LIFO -- FIFO will be discussed at a later lecture)

a data structure to hold a variable number of elements
of which only the top one is accessible at any given time
the stack may be empty if it holds no elements
the stack keeps track of the number of elements it has, as well as the individual elements
some stack implementations set a fixed maximum size for the stack, so the stack overflows if more data is added to a full stack

consider a stack to store objects of some type E:
void push(E item) adds the value to the top of the stack
E pop() throws EmptyStackException removes the value on top of the stack and returns it (or throws the exception)
E peek() throws EmptyStackException is like pop, except it doesn't remove the element
boolean empty() reports whether the stack is empty
only the topmost element of the stack is accessible
as in every ADT, we have specified only what the stack does, and not how that is accomplished. The how part belongs in the implementation

can the same name be reused for different methods?
Java: yes
programmers: yes, if they do the same thing
Java uses a signature for each method that includes the method's name, and the type/class and order (sequence) of its parameters
each method's signature must be unique within a class
example:
push(E) is the signature for the push method (above)
in an interface, this is written with the method prototype:
```
void push (E item);
```

in a class implementation, the signature is taken from the method header:

    /* @param	value to push onto the stack */
    public void push(E value) {
         ...

even though arrays and stacks are very different, we can use an array in implementing our stack
implementing a stack using an array is similar to implementing a list using an array
instead of the size of the list, we keep track of where the top of the stack is: an integer we call top
the code outside the class does not know and does not need to know that the stack is implemented using an array

given ArrayStack.java:
in-class exercise (everyone together): what is the runtime (big O) of empty(), push(), and pop()?

even though linked lists and stacks are very different, we can use a linked list in implementing our stack
implementing a stack using a linked list is similar to implementing a list using an array
all operations occur at the head of the list

given ArrayStack.java:
in-class exercise (everyone together): what is the runtime (big O) of empty(), push(), and pop()?
given LinkedStack.java:
in-class exercise (everyone together): what is the runtime (big O) of empty(), push(), and pop()?

any extensible data structure that has access at one end can be used to implement a stack
this includes java Vectors and java Lists
new data is added to or removed from the end of the Vector or ArrayList in O(1) time (when the array doesn't have to grow)
in the code in the book (p. 164/272), note that the data is stored in an object of type List<E>, that is created as an ArrayList<E>: this is an example of polymorphism, and makes it easy to switch to a different kind of list
new data is added to or removed from the front of the Linked List, in O(1) time
in the code on p. 162/270, instead of having an instance variable of type Vector, the stack class itself is a subclass of vector -- this kind of stack is also a vector!

a palindrome is a string that is the same when read backwards or forwards: "radar", "level", "racecar"
there are many algorithms for recognizing palindromes, and most are equivalent
one such algorithm uses a stack:
- the characters of the string are pushed onto the stack, one by one
- as they are removed from the stack in LIFO order, they are removed in reverse order
- they can be compared to the characters in the string
if the characters from the stack match the characters from the string, the string is a palindrome

balanced parenteses: "(a (b c) [d (e)] f g)"
unbalanced parenteses: "(a (b c {d (e)) f g]"
algorithm to check for balanced parentheses:
- when encountering an open parenthesis, put it on the stack
- when encountering a closed parenthesis, remove the matching one from the top of the stack, or declare an error (if the top of stack does not match, or if the stack was empty)
- at the end of the string, should have an empty stack
if the stack is not empty at the end of the string, the parentheses are not balanced