SUNY Geneseo Department of Computer Science

Stacks

Previous Lecture

Misc

Exam 2 is next Tuesday, Nov. 9

• Mainly lists, their algorithms, and analyses
• Maybe a little bit on stacks (this Thursday's topic)
• Same rules and format as 1st exam

Hand out Lab 9

Questions?

Stacks

Reading summary

• Intro to Chapter 12 (page 391), Section 12.2 through 12.2.5
• Stack = vertical data structure w/ top and bottom
• Like "FILO" / "LIFO" lists (last-in-first-out)
  • push - add item to top of stack
  • pop - get and remove top item
  • peek - look at top without removing
  • isEmpty - is stack empty
• Items always added and removed from same end (top)
• Stack used to keep track of recursion

An alternative implementation of stacks

• Are stacks really lists?
• What characterizes stacks?
  • peek, pop - get (and remove) top item
  • push - add item to top
  • isEmpty - find out if stack is empty
• What characterizes lists?
  • Head-tail recursive structure
  • Commands
    • getRest - extract tail of list
    • setRest - change tail
    • find - search list
    • delete - remove arbitrary item
    • getFirst - extract first item
    • addItem - add to front of list
    • getAndRemove - extract and remove front
    • isEmpty - is a list empty
• Everything stacks can do can be done with lists
• List is a subclass, i.e., extension, of stack
  • Then stack is restriction of lists
• Subclasses as ways of restricting access to superclass features (not, in my opinion, the best way to use subclasses, although one you will see)

• If stacks aren't really lists, there's another implementation

    class Stack
        private List data
        push( x )
            data.addItem(x)
        pop()
            return data.getAndRemove()
        isEmpty()
            return data.isEmpty()

• This is an example of an adaptor

Stack applications

• Evaluating expressions with precedence
  • (e.g., 31.5+4*5)
• See (and hand out) Homework 2
• Stacks as mechanism for saving information
  • Operators
  • Values
• Accumulate values and operators on stacks as read (push), pop and apply only after enough has been read to see that no higher-precedence operations coming up than the operations already on the stack.
• Expression: T ^ F v F ^ F
  • ~ ( T v F )

Next

Introduction to trees

Read sections 13.1 and 13.2

Next Lecture