Stacks

What is an ADT?

• An Abstract Data Type (ADT) is a collection of data plus a set of operations on it.
• You use the operations and ignore how it is built inside.
• A stack, a queue, and a linked list are all ADTs.

A stack is LIFO

• A stack is Last In, First Out (LIFO).
• The last item you add is the first one you take off.
• Think of a stack of plates: you take the top plate first.

push and pop with a list

• We can build a stack from a Python list.
• push = stack.append(x) — add to the end (the top).
• pop = stack.pop() — remove and return the end (the top).

stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)

peek and empty

• peek at the top without removing it: stack[-1].
• A stack is empty when len(stack) == 0.
• Popping an empty stack is an error, so check first.

stack = [10, 20, 30]
print(stack[-1])        # peek the top
print(len(stack) == 0)  # is it empty?

In Cambridge pseudocode

• The exam builds a stack from an array plus a top pointer (an index).

DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0                 // 0 means empty

// push value
top ← top + 1
stack[top] ← value

// pop into value
value ← stack[top]
top ← top - 1

Common mistakes

• A stack is last-in, first-out: push to the top, pop from the top.
• Check it is not empty before you pop.

Now you try

• Use a list as your stack (append to push, pop to remove).
• Press Check answer to test your code.