CS 240: Lecture 12 - Stack

Dear students:

We've been talking about list as an abstract data type. We've also been talking about array lists and linked lists, which are two data structures that are commonly used to implement a list. Today we look at a new abstract data type: the stack.

Stack

A stack is an abstract data type representing a sequence of items. The sequence can gain new items. It can also lose them. It always loses the item that it most recently gained.

Imagine you have been given a subscription to a magazine. You rarely have time to read, so each time you receive a new issue, you throw it on the pile. Then you get fired, so you have time to read. If you pull off the issue on the top, you are treating the pile as a stack.

Imagine a bad stocker at a grocery store. When a delivery arrives, the stocker puts the new items right in the front of the old ones. When a shopper pulls an item down, they also grab the freshest. Meanwhile, the item at the back starts to decompose. That stocker was using a stack.

In software, we have many occasions to use stacks. If we are searching the file system, we will create a stack of directories that haven't been scanned yet. We start by putting the root directory in the stack. We look at its files. Any directories we find inside it also get thrown on the stack. When writing a search engine for the web, we might similarly create a stack of URLs. To manage an undo history, we might create a stack of the user's historical content. In all cases, new items are added at one end and removed from the same end.

These are the common behaviors we see in stacks:

• push, which adds a new element to the sequence
• pop, which removes the newest element from the sequence
• peek, which yields but does not remove the newest element
• size, which yields the number of elements
• isEmpty, which yields the emptiness of a stack

That leads us to a peer instruction exercise. What is the output of this code?

Stack<String> stack = new Stack<>();

stack.push("A");
stack.push("B");
stack.push("C");
stack.pop();
stack.push("D");

while (!stack.isEmpty()) {
  print(stack.pop());
}

When we define an interface, we only describe the stack as an abstract data type. How a stack is implemented is up to us. There are several data structures that are likely choices. We could use an array list. Or we could use a linked list. This begs the question: why do we even have a stack class? Why not just use an array list or linked list directly. I can think of a couple of reasons:

• The stack has a narrower interface, preventing accidental misuse of a list.
• The stack provides a targeted vocabulary.
• The stack's implementation might be optimized for stack operations. Someone implementing a list can't make the same assumptions and might write slower but more general-purpose code.

If we can use either an array list or a linked list, is one better than another? Let's examine their complexities:

The cost of an array list's push operation is amortized over many calls. There's no clear theoretical winner here. Given the realities of hardware, an array list implementation might be faster because contiguous memory tends to be faster thanks to caching policies.

Postfix Evaluation

Let's see an example of an algorithm that uses a stack. Support you want to write code to evaluate an arbitrary arithmetic expression. Something of this form:

You might break the expression up into a list of tokens and then iterate through it. You read the 7, the +, and the 5. But you can't do anything with them. The multiplication operation must happen first. Evaluating expressions requires you to find the operation with the highest precedence, which can be challenging given parentheses and the need to scan the whole expression.

An alternative form was used by some early calculators. Instead of using infix notation, which places the operators between the operands, these calculators used postfix notation, which places the operators after the operands. The expression above has this postfix form:

A postfix expression can be evaluated in one pass through the sequence of tokens if we use a stack. Here's our algorithm:

operands = new stack
for each token
  if operand
    push operand onto operands
  else if operator
    pop right from operands
    pop left from operands
    result = perform operation
    push result onto operands

Suppose you have this infix expression:

If you converted this postfix and evaluated it using the algorithm above, which of the following will be the state of the stack at some point during the evaluation?

• \(2\ 4\ 8 \div \times\)
• \(3\ 7\ 8\ 4\ 2\)
• \(1\ 7\ 3\)
• \(2\ 4\ 8\ 7\ 3\)
• \(8\ 1\ 7\)
• \(4\ 8\ 1\)

The top of the stack is on the left. We'll solve this as a peer instruction exercise.

TODO

You've got a few things to do before we meet again:

See you next time!

P.S. It's time for a haiku!