Skip to content
ExamSpine

Lesson 5.15

A problem a stack solves

Part 5: Text, lists, stacks and queuesReading, about 6 min2 exercises in this lesson

Java answers can't run on Spine yet. You can still read Java, trace it, and put an answer's lines in order.

Problems a stack solves

By the end of this you will be able to spot a problem that a stack solves well, and explain why a stack fits it.

In the last lesson you met the stack. You push values onto the top and pop them off the top, so the value that comes off is always the one that went on most recently. Now the question is the other way round: given a problem, how do you know a stack is the right tool?

The sign of a stack problem

A stack fits a problem when the thing you need next is always the newest thing still waiting. Ask yourself: when I take something back, do I want the one that arrived most recently? If the answer is always yes, a stack fits.

Problems like this often have one of these shapes:

  • Undoing. The last change made is the first one to undo.
  • Reversing. Values pushed in one order come off in the opposite order.
  • Going back. You return to the place you left most recently, then the one before that, and so on. The Back button of a web browser works like this.

Undo

A text editor keeps a history of changes. Each change is pushed when it is made, and the undo button pops the top one.

history = []
history.append("type Hello")
history.append("make it bold")
history.append("type World")
change = history.pop()
print("Undo: " + change)
change = history.pop()
print("Undo: " + change)
print(len(history))
import java.util.ArrayList;

public static void main(String[] args) {
    ArrayList<String> history =
        new ArrayList<>();
    history.add("type Hello");
    history.add("make it bold");
    history.add("type World");
    int last = history.size() - 1;
    String change = history.remove(last);
    System.out.println("Undo: " + change);
    last = history.size() - 1;
    change = history.remove(last);
    System.out.println("Undo: " + change);
    System.out.println(history.size());
}

When it runs:

Undo: type World
Undo: make it bold
1

The first undo takes off the newest change, typing World. The second takes off the change made just before it. One change is left in the history. If the program took changes from the front of the list instead, the first undo would remove the oldest change, typing Hello, which is not what anyone pressing undo wants.

Before an undo, check that the history is not empty, as in the last lesson. With nothing left to undo, the button should do nothing.

Reversing

Push the characters of a word one at a time, then pop them all off. The last character pushed is the first one popped, so they come off back to front.

word = "stop"
stack = []
for ch in word:
    stack.append(ch)
backwards = ""
while len(stack) > 0:
    backwards = backwards + stack.pop()
print(backwards)
import java.util.ArrayList;

public static void main(String[] args) {
    String word = "stop";
    ArrayList<Character> stack =
        new ArrayList<>();
    for (int i = 0; i < word.length(); i++) {
        stack.add(word.charAt(i));
    }
    String backwards = "";
    while (stack.size() > 0) {
        int last = stack.size() - 1;
        char ch = stack.remove(last);
        backwards = backwards + ch;
    }
    System.out.println(backwards);
}

When it runs:

pots

In Java, a list of char values is an ArrayList<Character>. Between the angle brackets Java wants Character, with a capital, just as a list of int values is an ArrayList<Integer>.

The stack held s, t, o, p, bottom first. The p went on last, so it came off first.

When a stack is the wrong tool

Some problems need the opposite order. Think of people waiting to buy lunch: the person who arrived first should be served first. A stack would serve the person who arrived last, so it gets the order backwards. That problem needs a queue, which is the next lesson.

A stack is also the wrong tool when you need to read values in the middle. A stack only lets you reach the top, so if you need any value at any time, use a plain list.

Explaining why a stack fits

When a question asks you to explain why a stack suits a problem, make two points.

  1. Say what the problem needs next: the item that arrived most recently.
  2. Link it to the stack: a stack is last in, first out, so the item needed next is always on top, and a pop gives it straight away.

Here is an explanation for the undo button. Each change is pushed when it is made. The change to undo next is always the most recent one not yet undone. A stack is last in, first out, so that change is always on top, and a pop gives it without searching.

Saying only "a stack is last in, first out" is not enough. You have to show why that order is the one the problem needs.

Now try it yourself on the questions below.

Exercise 5.15.15.15.1 · Write itDo the brackets match?

A calculator app checks the brackets in a sum before it works the sum out. Write a function that is given just the brackets of a sum, in order, and returns whether they are balanced.

  1. The text holds only the characters (, ), [ and ]. It has at most 50 characters, and it can be empty.
  2. Each closing bracket must close the most recent opening bracket that is still open, and it must be the same kind: ) closes (, and ] closes [. So ([]) is balanced, but ([)] is not.
  3. A closing bracket when no bracket is open makes the text not balanced.
  4. Every opening bracket must be closed by the end of the text. Empty text is balanced.
  5. Return True in Python or true in Java when the brackets are balanced, and False or false when they are not.

Only the value your function returns is checked.

def balanced_brackets(text: str) -> bool

Examples

Your function is tested on 17 cases: the 6 examples below, and 11 hidden ones that check the rules above.

  • balanced_brackets("([])") should return True: the [ opened last, so it closes first (rule 2)
  • balanced_brackets("(]") should return False: a ] cannot close a ( (rule 2)
  • balanced_brackets("((") should return False: two brackets are never closed (rule 4)
  • balanced_brackets(")(") should return False: the ) comes when no bracket is open (rule 3)
  • balanced_brackets("()[]") should return True: two pairs, one after the other (rule 2)
  • balanced_brackets("[)") should return False: a ) cannot close a [ (rule 2)

public static boolean balancedBrackets(String text)

Checking whether Java answers can run here.

Examples

Your function is tested on 17 cases: the 6 examples below, and 11 hidden ones that check the rules above.

  • balancedBrackets("([])") should return true: the [ opened last, so it closes first (rule 2)
  • balancedBrackets("(]") should return false: a ] cannot close a ( (rule 2)
  • balancedBrackets("((") should return false: two brackets are never closed (rule 4)
  • balancedBrackets(")(") should return false: the ) comes when no bracket is open (rule 3)
  • balancedBrackets("()[]") should return true: two pairs, one after the other (rule 2)
  • balancedBrackets("[)") should return false: a ) cannot close a [ (rule 2)
solution.pySolution.java

Exercise 5.15.25.15.2 · Answer itTasks on hold

Sam works on a help desk. While Sam is working on a task, a more urgent task can arrive. Sam then puts the task in hand on hold and starts the new one, and that new task can be interrupted in the same way. When Sam finishes a task, Sam goes back to the task that was put on hold most recently. The tasks on hold are kept in a stack.

(a) Sam is working on task A. Task B arrives and interrupts A; later, while Sam works on B, task C arrives. State the tasks on hold now, bottom first. [1]

(b) Sam then finishes task C. State the task Sam goes back to, and name the stack operation used, so that the stack again holds only the tasks on hold. [2]

(c) Suppose the tasks on hold were kept in a queue instead, joining at the back and leaving from the front. Using tasks A, B and C, explain why the queue would give Sam the wrong task when C is finished. [2]

[5]