Sedgewick & Wayne · §4.3 Stacks and Queues · pp. 566-571

Stacks: The Stack API and an Array Stack

A stack removes the item most recently added (last in, first out), a queue the item least recently added (first in, first out). Start with the stack you already know, the call stack, then run both collections on the same input, look inside ArrayStackOfStrings, and find out which pop orders a stack can make.

1 · The call stack of a recursion

Each call of sum(n) puts a frame on top of the call stack and waits for sum(n - 1). Each return takes the top frame off. The call that returns first is the one that was called last. This JVM has room for only a few frames: pick an n that is too big and you get the StackOverflowError that sum(20000) gave on a real JVM.

room on the call stack

Code: Sum.java

What happens

Call stack (top first)

frames now0

most frames0

2 · The same input on a stack and a queue

One operation per word: - removes an item and prints it, any other word adds it. The stack pushes onto the top and pops from the top; the queue enqueues at the end and dequeues from the front. Change the words in the box to try your own; the trace starts over as you type.

Input

Stack · LIFO top ↓

Queue · FIFO front ← ← end

stack prints

queue prints

3 · Inside ArrayStackOfStrings

The items live in items[0..n-1], the top is items[n-1], and n is also the index of the next free slot. Step through tobe.txt or push and pop your own words. Watch the slots above the top: after a pop they still hold the old string (loitering) until you switch on the fix. Make the capacity too small, or switch on the bug from slide 15, and see what breaks.

capacity

pop()

your word

on the stack, items[0..n-1] top, items[n-1] above the top: a popped string still referenced

Code

True after every operation

What happens

prints

capacity5

loitering references0

4 · Which pop orders are possible?

Push 1, 2, ..., N in this order and pop in between whenever you like; each pop prints. Type an order of the numbers 1 to N and find out whether a stack can print it. If it can, you see the pushes and pops (-) that do it; if not, where it gets stuck. Make your guess before you click.

Order to print

Built to accompany COSC 2230 (Computer Science III), lecture The stack API and an array stack. The code panels show the class code (book Program 4.3.1 and Sum.java); every step is computed live in the browser.