Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes: 26-Mar-2007

Logistics:

1. No quiz this week

2. Reading from 21-March lecture modified to include sections 12.8 – 12.9 (on Iterators)

3. Homework #7 modified so that iterators work with Collections.sort().

4. Reading:

a. Java by Dissection, Sections 12.5 – 12.6 (Stacks) and 12.7 (Queues)

b. Javanotes, Section 9.3 (all of it, including Queues)

Topics:

1. Stacks

a. LIFO == “Last In First out”

b. Like a stack of plates (hence the name)

c. Operations:

i. Push: Add to the top of the stack

ii. Pop: Remove from the top of the stack

iii. Others (Peek, IsEmpty, …)

d. Typical Implementation as List

i. Linked List (typical), ArrayList (less so)

ii. Push: Add to front of linked list or end of array (which is the top of the stack)

iii. Pop: Remove from same side of list

e. Java Stack: java.util.Stack

i. Extends Vector (java.util.Vector)

1. Vectors are like an ArrayLists

a. Self-adjusting lists backed by arrays (not linked lists)

2. Key difference: Vectors are synchronized

a. Vectors are “thread-safe”, so they can be used safely in a multithreaded program.

b. Vectors are “slow” because of this.

ii. Could write our own (of course) extending ArrayList

1. For example: StackByInheritance

a. Note that you are responsible for everything in this example code, including:

i. Creating your own interfaces.

ii. Creating your own exceptions.

iii. Creating your own parameterized classes.

f. Q: What are the tradeoffs (including Big-Oh runtimes of push and pop operations) in backing a Stack with:

i. Singly-Linked List

ii. Doubly-Linked List

iii. ArrayList

iv. Vector

v. Array

2. Evaluating Postfix (RPN) with a Stack

a. RPN == “Reverse Polish Notation” (what our book simply calls “Polish”)

b. Also called “Postfix”

c. Operands are followed by an operator

i. 1 2 + == 3

ii. 1 2 3 + + == 1 5 + == 6

iii. 2 3 4 + * == 2 7 * == 14

d. Implemented with a Stack

i. Push each operand onto the stack

ii. For each operator:

1. Pop two operands off the stack

2. Push the result back on the stack

iii. When we are done: pop the result off the stack

iv. Note: for poorly-formed expressions, two cases:

1. Stack is empty when we need to pop an operand, or

2. Stack is not empty after we pop the result

e. Implementation (we will do this in class, but you can also see section 12.6)

3. Evaluating Prefix with an Implicit Stack (Recursion)

a. Operators are followed by operands

i. + 1 2 == 3

ii. + + 1 2 3 == + 3 3 == 6

iii. + * 2 3 4 == + 6 4 == 10

b. Implemented with recursion (hence an implicit stack):

i. For each operator:

1. Recursively find each operand

2. Return result

ii. When we are done: result is simply returned

iii. Note: for poorly-formed expressions, two cases:

1. End-of-input when we need to read an operand, or

2. Not end-of-input when we return our result

c. Implementation (not in book)