Lesson 5.14

Stack: push, pop, last in first out

Part 5: Text, lists, stacks and queuesReading, about 6 min4 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.

Stacks: last in, first out

By the end of this you will be able to say how a stack behaves, name its operations, use a list as a stack, and work out what a stack holds after a run of pushes and pops.

Think of a pile of plates. You put a clean plate on the top, and you take a plate from the top. The plate you take is always the one that went on last.

What a stack is

A stack is a collection of values where you can only reach one end, called the top. It has four operations:

Push puts a new value on the top.
Pop takes the top value off and gives it back.
Peek gives back the top value and leaves it where it is.
Is empty tells you whether the stack holds no values at all.

Every push and every pop happens at the top, so Key idea: the value that comes off is always the one that went on most recently. This is called last in, first out, or LIFO for short.

Play with it

Challenge:make the stack hold 5 with 1 on top of it. You will need a pop.

Given back:

# your moves appear here as code

Each button shows the line of code that does the same thing. Pop the stack until it is empty, then pop once more.

You cannot read the third value from the top without first popping the two above it. That rule is what makes a stack a stack, even when its values are kept in a list that could do more.

A list as a stack

A Python list or a Java ArrayList makes a good stack. Use the end of the list as the top, because adding or removing a value at the end leaves every other value at the index it had. Step through this program and watch the pile.

Step through it

stack = []

stack.append(4)

stack.append(7)

stack.append(2)

print(stack)

print(stack[-1])

top = stack.pop()

print(top)

print(stack)

print(len(stack))

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/10

Here are the four operations in each language, with v as a value:

Python: push stack.append(v), pop stack.pop(), peek stack[-1], is empty len(stack) == 0.
Java: push stack.add(v), pop stack.remove(stack.size() - 1), peek stack.get(stack.size() - 1), is empty stack.isEmpty().

In Java, remove given an int treats it as an index, so stack.remove(stack.size() - 1) takes off the value at the last index, the top. Java also has ready-made stack classes such as ArrayDeque, with methods called push, pop and peek. This course uses an ArrayList so that you can see where the top is.

Pushes and pops in order

To work out what a stack holds, keep track of it after every operation, bottom first. Each pop takes whatever is on top at that moment: the most recent push that is still there.

Quick check

A stack starts empty. Then: push 5, push 9, pop, push 1, push 3, pop, pop. Which values do the three pops give back, in order?

Key idea: If you push some values and then pop them all, they come off in the opposite order to the one they went on in.

Popping an empty stack

An empty stack has no top. In Python, pop() on an empty list stops the program with IndexError: pop from empty list. In Java, stack.size() - 1 is -1 when the list is empty, so remove stops the program with an IndexOutOfBoundsException. Peeking at an empty stack is an error in the same way. If you tried it in the stack above, you saw both.

So check before you pop or peek:

stack = []
if len(stack) == 0:
    print("nothing to take")
else:
    print(stack.pop())

import java.util.ArrayList;

public static void main(String[] args) {
    ArrayList<Integer> stack =
        new ArrayList<>();
    if (stack.isEmpty()) {
        System.out.println("nothing to take");
    } else {
        int last = stack.size() - 1;
        System.out.println(stack.remove(last));
    }
}

This prints nothing to take, and the program carries on.

A stack in a fixed-size array

A stack can also live in a fixed-size array, as you met in the lesson on fixed-size arrays and growable lists. The array never changes length (in Python, a list made with [0] * 3 that the code never appends to), so you keep a count, here called size, of how many places the stack is using. The top is at index size - 1. Step through it and watch the arrow.

Step through it

stack = [0] * 3

size = 0

stack[size] = 5

size = size + 1

stack[size] = 8

size = size + 1

size = size - 1

print(stack[size])

print(stack)

print(size)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/10

In Java, Arrays.toString(stack) shows the values of the array in square brackets, with import java.util.Arrays; at the top of the file. Printing stack on its own would not show the values.

Key idea: A push writes at index size and then adds 1 to size. A pop takes 1 off size and then reads at index size.

This stack can be full. When size equals the length of the array, there is no place left for a push. It is empty when size is 0, so check size before a pop. A stack in a Python list or a Java ArrayList has no fixed limit: the list grows when it needs more places. That is the same trade as in the earlier lesson: the array uses exactly the places asked for, and the list can grow.

Two common mistakes

Taking from the wrong end. pop(0) in Python, or remove(0) in Java, takes the value at the bottom, the one pushed first. A stack always takes from the top.
Popping without checking. If the stack can be empty at that point, check it first, or the program stops with an error.

Quick check

A stack holds 5, 1 and 3, bottom first, in a list. Some code removes the value at index 0. What comes off, and is that a pop?

Now try it yourself on the questions below.

Exercise 5.14.1 · Trace itTrace: stack moves

Complete the trace table for this Python code. stack is used as a stack, and its last value is the top. append pushes a value onto the top, and pop() takes the top value off and gives it back. Write the stack in square brackets, bottom first, as Python prints it. Then answer the question below the table. [3]

Line 1: stack = []1stack = []
Line 2: stack.append(6)2stack.append(6)
Line 3: stack.append(1)3stack.append(1)
Line 4: x = stack.pop()4x = stack.pop()
Line 5: stack.append(8)5stack.append(8)
Line 6: stack.append(x + 3)6stack.append(x + 3)
Line 7: total = 07total = 0
Line 8: while len(stack) > 0:8while len(stack) > 0:
Line 9, indented 1 level: top = stack.pop()9    top = stack.pop()
Line 10, indented 1 level: total = total + top10    total = total + top

Fill in one row each time a line changes stack, x or total. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes.

Row	stack	x	total
1
2
3
4
5
6
7
8
9
10
11
12
13

Which values did the while loop take off the stack, in the order it took them?

Exercise 5.14.1 · Trace itTrace: stack moves (Java)

Complete the trace table for this Java code. The code runs with ArrayList already imported. stack is an ArrayList used as a stack, and its last value is the top. add pushes a value onto the top, and remove(stack.size() - 1) takes the top value off and gives it back. Write the stack in square brackets, bottom first, as Java prints an ArrayList. Then answer the question below the table. [3]

Line 1: ArrayList<Integer> stack =1ArrayList<Integer> stack =
Line 2, indented 1 level: new ArrayList<>();2    new ArrayList<>();
Line 3: stack.add(6);3stack.add(6);
Line 4: stack.add(1);4stack.add(1);
Line 5: int x = stack.remove(stack.size() - 1);5int x = stack.remove(stack.size() - 1);
Line 6: stack.add(8);6stack.add(8);
Line 7: stack.add(x + 3);7stack.add(x + 3);
Line 8: int total = 0;8int total = 0;
Line 9: while (stack.size() > 0) {9while (stack.size() > 0) {
Line 10, indented 1 level: int top = stack.remove(stack.size() - 1);10    int top = stack.remove(stack.size() - 1);
Line 11, indented 1 level: total = total + top;11    total = total + top;
Line 12: }12}

Fill in one row each time a line changes stack, x or total. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes.

Row	stack	x	total
1
2
3
4
5
6
7
8
9
10
11
12
13

Which values did the while loop take off the stack, in the order it took them?

Exercise 5.14.25.14.2 · Write itWhat is left on the stack

A robot stacks numbered boxes in a warehouse. It is given a list of moves, and it carries them out in order on a stack that starts empty. Write a function that returns what the stack holds after the last move.

A move above 0 is a box number: push it onto the stack.
A move of 0 means pop: take the top box off the stack. A 0 when the stack is empty does nothing.
Return the box numbers still on the stack as a list, bottom first, so the top is the last value. An empty stack is an empty list. In Java, return an ArrayList<Integer>.
Every move is between 0 and 999. There are at most 50 moves, and the list of moves can be empty.

Only the list your function returns is checked.

def stack_after(moves: list[int]) -> list[int]

Examples

Your function is tested on 13 cases: the 5 examples below, and 8 hidden ones that check the rules above.

stack_after([4, 9, 0, 6]) should return [4, 6]: the 0 takes off 9, the box pushed last (rule 2)
stack_after([0, 3]) should return [3]: a 0 on an empty stack does nothing (rule 2)
stack_after([1, 2, 3]) should return [1, 2, 3]: no pops: the list is bottom first, in the order the boxes went on (rule 3)
stack_after([5, 0]) should return []: the only box comes off, so the stack is empty (rule 3)
stack_after([9, 1, 9, 0]) should return [9, 1]: the top 9 comes off, not the 9 at the bottom (rule 2)

public static ArrayList<Integer> stackAfter(int[] moves)

Running Java here comes later. You can put this answer's lines in order instead. You can still write your Java answer (it stays while this page is open) and compare it with our worked solution. Or try this exercise in Python.Checking whether Java answers can run here.

Examples

Your function is tested on 13 cases: the 5 examples below, and 8 hidden ones that check the rules above.

stackAfter(new int[]{4, 9, 0, 6}) should return [4, 6]: the 0 takes off 9, the box pushed last (rule 2)
stackAfter(new int[]{0, 3}) should return [3]: a 0 on an empty stack does nothing (rule 2)
stackAfter(new int[]{1, 2, 3}) should return [1, 2, 3]: no pops: the list is bottom first, in the order the boxes went on (rule 3)
stackAfter(new int[]{5, 0}) should return []: the only box comes off, so the stack is empty (rule 3)
stackAfter(new int[]{9, 1, 9, 0}) should return [9, 1]: the top 9 comes off, not the 9 at the bottom (rule 2)

solution.pySolution.java

def stack_after(moves: list[int]) -> list[int]:
    # your code here
    pass

Exercise 5.14.35.14.3 · Write itThe top of a small stack

A cafe has a shelf with room for only a few trays, one on top of the other. Write a function that carries out a list of moves, in order, on a stack that starts empty and can hold at most capacity values, and returns the value on top after the last move.

A move above 0 is pushed onto the stack, unless the stack already holds capacity values. Then that move is refused, and the stack does not change.
A move of 0 pops the top value off the stack. A 0 when the stack is empty does nothing.
Return the value on top of the stack after the last move, without taking it off. If the stack is empty at the end, return -1.
capacity is between 1 and 10. Every move is between 0 and 999. There are at most 50 moves, and the list of moves can be empty.

Only the number your function returns is checked.

def top_after(capacity: int, moves: list[int]) -> int

Examples

Your function is tested on 14 cases: the 5 examples below, and 9 hidden ones that check the rules above.

top_after(3, [4, 9, 0, 6]) should return 6: the 0 takes off 9, and 6 is pushed last, so 6 is on top (rule 3)
top_after(2, [5, 6, 7]) should return 6: the stack is full after 6, so 7 is refused (rule 1)
top_after(3, [8, 0]) should return -1: the stack is empty at the end (rule 3)
top_after(1, [0, 2]) should return 2: a 0 on an empty stack does nothing (rule 2)
top_after(3, [9, 1, 9, 0]) should return 1: the pop takes the top 9, not the bottom one (rule 2)

public static int topAfter(int capacity, int[] moves)

Examples

Your function is tested on 14 cases: the 5 examples below, and 9 hidden ones that check the rules above.

topAfter(3, new int[]{4, 9, 0, 6}) should return 6: the 0 takes off 9, and 6 is pushed last, so 6 is on top (rule 3)
topAfter(2, new int[]{5, 6, 7}) should return 6: the stack is full after 6, so 7 is refused (rule 1)
topAfter(3, new int[]{8, 0}) should return -1: the stack is empty at the end (rule 3)
topAfter(1, new int[]{0, 2}) should return 2: a 0 on an empty stack does nothing (rule 2)
topAfter(3, new int[]{9, 1, 9, 0}) should return 1: the pop takes the top 9, not the bottom one (rule 2)

solution.pySolution.java

def top_after(capacity: int, moves: list[int]) -> int:
    # your code here
    pass

Exercise 5.14.45.14.4 · Answer itStack in words

A teacher collects exam papers in a pile on the desk. Each paper handed in goes on top of the pile, and the teacher always marks the paper on top of the pile next. All the papers are handed in before the teacher starts marking. The pile is a stack.

(a) Explain what last in, first out means for the order in which the papers are marked. [2]

(b) Name the four operations of a stack, and state what each one does. [4]

[6]

Your answer