SUNY Geneseo Department of Computer Science

Introduction to Stacks

Previous Lecture

Misc

No office hours today

Labs 9 waiting for me when I get in tomorrow considered on time

Lab 10 available in labs tomorrow

• List extension & experiment

Second hour exam is Friday (April 1)

• Lists, their algorithms and analyses, related structures
• Rules and format similar to first exam
• I'll put sample exam on Web

Questions?

Homework & buffered readers - deciding which file to read and then making a room from its contents?

• Picking file name:
  • Read it from user via JOptionPane
  • Or define as string constant

        final String fileName = "left.txt";
        .... new FileReader( fileName ) ...

• Defining room

        String roomDescription = b.readLine();
        RobotRoom room = new RobotRoom( roomDescription );

• Some Web browsers put blank lines at the front of files

Stacks

Section 12.2

Like queues

• First-in-last-out
• Last-in-first-out

Main methods of stacks

• push
• pop
• peek
• (isEmpty)

Visualize as vertical structures rather than horizontal

Examples, how to apply stacks

Algorithms with Stacks

Purely iterative version of text's prefix expression evaluator

e.g., + * 2 7 * 12 3 <end>

    if current input is an operator
        push it on operator stack
    else if current input is an operand
        push it on operand stack
    if operand stack has 2n + 1 elements (n is size of operator stack)
        pop operand stack twice
        pop operator stack
        apply popped operator to popped operands
        push result to operands

Or simplify and only use one stack

    push current input on stack
    if top two elements of stack are operands
        pop stack 3 times (two operands & operator)
        apply popped operator to popped operands
        push result 

Next

Is Stack really a subclass of List?

An alternative implementation

Next Lecture