SUNY Geneseo Department of Computer Science

Stacks

Previous Lecture

Questions?

Density of primes

• Number of primes <= n is asymptotically n / ln n

Careful about curve fitting

• Data analysis programs will always find a curve, even if it's not a very good fit.

Stacks

Intro to chapter 12, section 12.2 through 12.2.4

• Stacks in real world
  • Storage shelves
  • In-box
  • etc
• FILO, FIFO
• Stacks in CS
  • Reversing a string
    • Push string onto stack
    • Take characters out in reverse order
  • Palindromes
• Designing stack class
  • push = add object to top of stack
  • pop = remove top object and return it
  • isEmpty = see if stack is empty
  • peek = returns value of top item without removing it
• Code for stack class

Stack class in book is subclass of List

• So needs makeNewList method
• Subclasses of stack would need it too

pop changes stack

• s.pop() // s is now smaller
• s.pop().pop() doesn't pop stack twice because pop returns top item, not smaller stack

Analogy to lists

Difference between stack and list

• (OOP implications)
• Stack has different commands
  • So stack is completely different from list
• Stack is a subclass of list
  • ... so designed for more specific applications than list
  • i.e., stack is just a kind of list, no big differences
• But you're not supposed to do list-style things to stacks (getRest, etc.)
• Internally stacks are lists
• Like towers of Hanoi, only look at top
• Definition of stack says some list operations aren't appropriate
• Hawaiians vs New Yorkers vs US citizens
  • New Yorkers pay NY tax, Hawaiians don't
  • Hawaii and NY as subclasses of US citizen
    • all pay US taxes
    • all have US passports
• OOP point:
  • Inheritance/subclasses
    • Because of what something is
      • Subclass appropriate when one class is an extension to another's interface
    • vs because of how it's implemented
      • Subclass appropriate when you can reuse lots of code from superclass
  • Type
    • As defined by interface
      • Stack defined by push, pop, isEmpty,...
      • List defined by addItem, concat, isEmpty, ...
    • vs type as implementation
      • Stack, list both built as sequences of values
  • Type as the interface wins
    • Deeper notion of "same kind of thing"
    • vs coincidences of implementation
• Maybe list is a subclass of stack -- extended stack with same push, pop, etc. plus ways of getting at inside of the sequence

Another Implementation of Stacks

Argument: Stack shouldn't be a subclass of List at all, because stacks aren't quite lists (e.g., can't search a stack, concatenate stacks, remove an item without returning it, etc.)

But: It sure is convenient to build stack operations from List operations.

Design a Stack subclass that respects both of these arguments

Can "simulate" stack operations using a list

Hide this idea inside a Stack class

    class Stack {
        private List stackedData;
        public Stack() {
            stackedData = new List();
        }
        public void push( Object x ) {
            stackedData.addItem( x );
        }
        public Object pop() {
            return stackedData.getAndRemove();
        }
        public boolean isEmpty() {
            return stackedData.isEmpty();
        }
        public Object peek() {
            return stackedData.getFirst();
        }
    }

Example of "adaptor pattern"

But List and Stack are still similar in many ways. Maybe both should both be subclasses of some common "ur-list" class

Next

Introduction to Trees

Read sections 13.1, 13.2, 13.4

Next Lecture