IB COMPUTER SCIENCE | B2.2.3 Stacks and LIFO

Lesson objective

Explain LIFO stack behaviour and push, pop, peek and isEmpty, connecting implementation performance and memory use to an appropriate problem.

Learn

B2.2.3 | STACKS AND LIFO

01 | THE LAST THING ADDED IS THE FIRST THING REMOVED

Imagine stacking three trays: A first, then B, then C. To remove one without reaching through the stack, you take C. C was added last and is removed first.

A stack is a data structure with last in, first out (LIFO) access. Additions and removals occur at one designated end, called the top. The bottom entry waits until the entries above it have been removed.

This common SL/HL lesson explains push, pop, peek and isEmpty, traces their effects and connects stack implementations to performance, memory and suitable problems. A stack is defined by its access rules, not by whether the drawing is vertical.

02 | SEE THE TOP AND BOTTOM

After pushing A, then B, then C, the stack is shown below. The top is C. Its stored order from bottom to top is [A, B, C], but its next removal order is C, B, A.

TOP C
B
BOTTOM A
One top end for both push and pop. Next out: C.

Do not read a bottom-to-top list as the order in which values will be popped. Label your chosen convention in a trace. This page writes stack contents bottom → top, with the top at the right of a bracketed list.

03 | FOUR CORE OPERATIONS

Operation Purpose Changes contents? Example on [A,B,C], top C
push(value) Add a new entry at the top. Yes push(D) gives [A,B,C,D].
pop() Remove and return the top entry. Yes pop returns C and leaves [A,B].
peek() Return/read the top entry without removing it. No peek returns C; contents remain [A,B,C].
isEmpty() Report whether there are no entries. No False for this stack.

These names describe an abstract interface. A programming language may supply different method names or failure behaviour. Python list.append is used for push in our list-backed implementation; a wrapper function can expose the name push.

04 | PUSH: ADD AT THE TOP

Start empty. push(A) creates [A]. push(B) creates [A,B]. push(C) creates [A,B,C]. The new item becomes the top; earlier entries retain their relative order.

Push does not remove the previous top. It places the new entry above it. If A was below B before the push, it remains below B afterwards.

A fixed-capacity stack can reject a push when it has no free slot. A dynamic implementation can attempt to acquire more storage, but is still limited by resources and any application bound.

05 | POP: RETURN AND REMOVE

Popping [A,B,C] returns C and changes the stack to [A,B]. A second pop returns B. After the third pop returns A, the stack is empty.

The returned item and the remaining stack are different results of the operation. Record both in a trace: “returned C; remaining [A,B]”.

Popping an empty stack is an underflow condition. The interface must define a response, such as an exception or an explicit failure result. It must not silently invent a valid item.

06 | PEEK AND ISEMPTY DO NOT REMOVE

stack = ["A", "B", "C"]
print(stack[-1])      # C: peek
print(len(stack) == 0)  # False
print(stack)          # ['A', 'B', 'C']

Peek lets a program inspect the next item without consuming it. Repeated peeks return the same top value if no intervening operation changes the stack.

isEmpty answers a condition; it does not empty the collection. Check it before a top access when the calling code needs a controlled empty case.

Python stack[-1] on an empty list raises IndexError. Use the interface’s stated empty policy rather than assuming every peek in every language behaves identically.

07 | TRACE A MIXED SEQUENCE

Operation Returned item / result Contents bottom → top
Start No item []
push(A) No item required by this interface [A]
push(B) No item required [A,B]
peek() B [A,B]
pop() B [A]
push(C) No item required [A,C]
pop() C [A]
isEmpty() False [A]
pop() A []

The removal sequence is B, C, A because a new push occurs between the first and second pops. “Reverse the original input” only describes a sequence that pushes all values before popping them all.

At every step, derive the current top from the current contents. Do not keep using the most recent item ever pushed after it has already been removed.

08 | INTERACTIVE: CONTROL A BOUNDED STACK

Push values, predict the next result and try each operation. The diagram shows top first; the textual contents are bottom → top. The selected capacity is an application limit for this teaching model, not a claim about Python list’s internal capacity. Changing it resets the experiment.

Operation history; contents shown bottom to top
Operation Result Contents after operation

Try push A, push B, peek, pop, isEmpty, pop and pop again. Then fill the stack and attempt one extra push. A rejected operation leaves contents unchanged. History displays the most recent 12 operations.

09 | EMPTY AND FULL ARE DIFFERENT QUESTIONS

Underflow concerns attempting a top operation when size is zero. Overflow concerns exceeding a bounded capacity on push. An empty stack is not full; a nonempty stack is not necessarily full.

For a capacity-five stack, isEmpty is true at size 0, while isFull would be true at size 5. isFull can be useful for a bounded implementation, though the core syllabus operations here are push, pop, peek and isEmpty.

Do not use None as an ambiguous empty marker if None can be a valid stored entry. An exception or a separate success flag can distinguish failure from returning a legitimate value.

10 | PYTHON: A LIST-BACKED STACK

stack = []
stack.append("A")  # push
stack.append("B")  # push
print(stack[-1])   # peek: B
print(stack.pop()) # pop: B
print(stack)       # ['A']
print(len(stack) == 0)  # isEmpty: False

Use the end of the list as the top. append and pop() work at that end, while [-1] accesses it without removal. Removing index 0 would implement a different access rule for these additions.

Although the list supports arbitrary indexing, a stack interface deliberately restricts how clients use it. The underlying collection’s extra capabilities do not change the intended LIFO contract.

11 | CONSTRUCT THE STACK INTERFACE

def push(stack, item):
    stack.append(item)

def is_empty(stack):
    return len(stack) == 0

def pop(stack):
    if is_empty(stack):
        raise IndexError("Cannot pop an empty stack")
    return stack.pop()

def peek(stack):
    if is_empty(stack):
        raise IndexError("Cannot peek an empty stack")
    return stack[-1]

work = []
push(work, "A")
push(work, "B")
print(peek(work))  # B
print(pop(work))   # B
print(pop(work))   # A
print(is_empty(work))  # True

These functions define one explicit empty policy: pop and peek raise IndexError. push mutates the supplied list and returns None implicitly; is_empty returns a Boolean.

The list passed as an argument is shared with the caller. Mutating it inside push changes the same list, unlike merely rebinding a local parameter to a different object.

12 | FIXED ARRAY MODEL: DEFINE THE TOP POINTER

A fixed-array implementation reserves slots and keeps an integer top. We choose top = −1 for empty, meaning top is the index of the most recently occupied slot. Capacity four therefore has valid storage indexes 0 through 3.

With this convention, size is top + 1. Empty means top == −1, and full means top == capacity − 1. Another textbook may use a pointer to the next free slot instead; its formulas will differ. Always state which convention applies.

Contents top size
[] −1 0
[A] 0 1
[A,B] 1 2
[A,B,C,D] 3 4

13 | FIXED ARRAY PUSH AND POP

capacity = 4
storage = [None] * capacity
top = -1

# Push A under the last-occupied-index convention.
if top == capacity - 1:
    print("Stack full")
else:
    top = top + 1
    storage[top] = "A"

# Pop: save the item before moving the pointer.
if top == -1:
    print("Stack empty")
else:
    item = storage[top]
    storage[top] = None
    top = top - 1
    print(item)  # A

Check bounds before changing the pointer or accessing storage. Push increases top, then writes the new entry; pop reads the old top, clears that slot in this model, then decreases top.

Clearing a removed reference can avoid retaining an object unnecessarily. Moving top changes logical size but does not reduce the reserved array’s capacity.

This Python list simulates a fixed backing array by policy. Its built-in type is still resizable; the stack operations choose to use only the reserved slots.

14 | PERFORMANCE: ONE END MAKES OPERATIONS SIMPLE

A fixed-array push or pop normally updates one pointer and one slot, so its basic work is constant with respect to the number of stored entries. Peek reads one slot and isEmpty checks a pointer or count.

A resizable-array stack has similarly small ordinary end operations, but a growth-triggering push can allocate and copy existing entries. Push is commonly amortised constant time over a sequence, rather than guaranteed identical latency for every call.

Python list.pop() removes the final entry without shifting all preceding entries. Shrinking, allocation and runtime effects still matter. Treat asymptotic descriptions as growth behaviour, not exact timings in milliseconds.

15 | MEMORY: SIZE, CAPACITY AND PEAK USE

A fixed-capacity stack reserves room for its maximum. Unused slots cost storage, and exceeding the bound needs a defined overflow response. A resizable stack can reserve spare capacity and may temporarily need old and new backing blocks during growth.

A linked stack can add and remove nodes at its head, using a top reference. It avoids a single growing backing array, but each node needs link storage and allocation. Abstract push/pop can be constant-time link operations, while actual allocation cost depends on the system.

No dynamic stack has unlimited storage. Removing an entry changes logical size; freeing a backing block or returning memory to the operating system is a separate implementation concern.

16 | CHOOSE AN IMPLEMENTATION FOR THE WORKLOAD

Implementation Useful property Trade-off
Fixed-capacity indexed storage Known maximum and no capacity-growth copy while within the bound. Unused reserved slots and overflow at the fixed limit.
Resizable array/list Convenient growth and compact indexed backing storage. Spare capacity and occasional resizing work.
Linked nodes at the top/head Top changes by link updates without copying all entries. Per-node links, allocation overhead and less contiguous storage.

A stack is an abstract LIFO interface; the implementation determines storage costs. Do not claim that every stack is a static array or that dynamic stacks must use links.

17 | JAVA: A DEQUE USED AS A STACK

import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("A");
        stack.push("B");
        System.out.println(stack.peek());    // B
        System.out.println(stack.pop());     // B
        System.out.println(stack.pop());     // A
        System.out.println(stack.isEmpty()); // true
    }
}

Deque supports a stack interface at one end. These operations provide the same LIFO behaviour even though Python list uses different method names.

For this Java ArrayDeque, peek on empty returns null while pop on empty throws NoSuchElementException. It does not permit null entries, so the empty peek result is distinguishable. Our Python wrapper instead raises IndexError for empty peek. Read the chosen interface’s contract.

18 | AN APPROPRIATE PROBLEM: UNDO

A simple text editor lets a user undo the most recent change before earlier changes. That ordering matches LIFO: the last edit is the next one reversed.

One teaching implementation stores a snapshot of the previous document before each accepted edit. Push the old text; apply the new text. Undo pops the most recent saved snapshot and restores it.

For documents of length m and k snapshots, retained text can be large, roughly proportional to the sum of snapshot lengths. A production editor may store edit commands or differences instead. A stack provides the ordering, not a guarantee of low memory use.

19 | INTERACTIVE: WHY UNDO USES A STACK

The current document starts as CODE. Apply a new document value, then undo. Each actual edit pushes the previous text. Undo restores and removes the most recent snapshot. Empty text is allowed as document content; it is not used to indicate an empty history. This model retains up to five snapshots.

Current document:

Try CODE → CODER → CODING, then undo twice. The states restored are CODER and CODE. A third undo has no saved snapshot. Undo does not automatically enable redo: a separate redo history and a policy for new edits would be needed.

20 | OTHER LIFO APPLICATIONS

Nested function calls resume in the reverse order in which unfinished calls were entered. Conceptually, a call stack holds frames containing return context and local state. The most recently entered unfinished call must finish before its caller resumes.

Bracket matching also uses nesting: the last opening bracket must be matched by the next appropriate closing bracket. A closing square bracket cannot correctly match an opening parenthesis merely because a stack is nonempty.

Backtracking can store earlier choices or states so the most recent unresolved decision is revisited first. The application must define what data each entry contains and what restoration means.

21 | WORKED PROGRAM: REVERSE A SEQUENCE

letters = ["C", "O", "D", "E"]
stack = []
for letter in letters:
    stack.append(letter)

reversed_letters = []
while len(stack) > 0:
    reversed_letters.append(stack.pop())

print(reversed_letters)  # ['E', 'D', 'O', 'C']
print(stack)             # []

Pushing all entries then popping them all reverses their order. Each letter is pushed and popped once, so the number of core operations grows linearly with the input length. The stack can hold the entire input, using linear additional entry storage.

The original letters list remains available, but the working stack is consumed. In Python there are shorter reversal methods; this program demonstrates why LIFO reverses a sequence.

22 | WORKED PROGRAM: MATCH PARENTHESES

def balanced_parentheses(text):
    stack = []
    for character in text:
        if character == "(":
            stack.append(character)
        elif character == ")":
            if len(stack) == 0:
                return False
            stack.pop()
    return len(stack) == 0

print(balanced_parentheses("(a+(b*c))"))  # True
print(balanced_parentheses(")("))        # False
print(balanced_parentheses("(()"))       # False

A closing parenthesis requires an unmatched opening parenthesis. Pop it when matched. At the end, no openings may remain. Other characters are ignored in this particular task.

This checks parentheses only, not square/curly brackets, quoted text or a complete programming language. A multi-bracket version must also compare each closing type with the latest opening type.

Worst-case stored openings grow with input length. Every character is inspected once, but a list-backed push may occasionally trigger resizing.

23 | WHY A STACK DOES NOT FIT EVERY TASK

A first-come, first-served printer queue normally needs the oldest pending job next. A stack would give priority to the newest job, potentially delaying old jobs indefinitely as more arrive.

Choosing a stack therefore requires an explanation of why reversing access to pending entries matches the problem. For undo, the last edit is reversed first; for fair arrival-order service, that is usually the wrong rule.

A stack does not automatically allow efficient search for an arbitrary middle item through its abstract interface. If the task frequently needs unrelated indexed access, a different interface may suit it better.

24 | TEST OPERATIONS AND BOUNDARIES

Test Expected evidence
Pop or peek when empty Defined underflow response; contents unchanged.
Push A, push B, peek Return B without removal.
Push A, push B, pop twice Return B then A; become empty.
Push after a pop New item becomes the top.
One more push than bounded capacity Defined overflow response; no overwritten entries.
Duplicate values Each push creates a separate entry even when values are equal.

Track size, contents, returned values and the pointer convention, rather than only checking the last output. A history or undo stack must preserve the correct state, not merely return a plausible-looking value.

25 | WRITE AN EXPLAIN ANSWER

Connect rule → operation → consequence. For example: “Undo stores the previous state before each edit. The most recent saved state is on top, therefore popping it reverses the latest edit before earlier ones.”

For performance, name the implementation and operation: a fixed-array pop updates the top and one slot; a resizable-array push may need a growth copy; a linked push allocates a node and updates references. Avoid saying every stack operation takes exactly the same measured time.

For memory, distinguish current entries, reserved capacity, per-entry overhead and any data stored inside each entry.

26 | READY FOR THE NEXT ACCESS RULE

You should now be able to trace LIFO behaviour, implement push/pop/peek/isEmpty, handle empty/full cases and justify an appropriate application with performance and memory considerations.

The next lesson introduces FIFO queues, where the earliest pending entry is removed first.

Python lists as stacks | Java ArrayDeque documentation

MATCH THE STACK IDEA

Terminology

Terminology

Stack

A collection whose entries are added and removed at its top using LIFO access.

LIFO

Last in, first out: the most recently added remaining entry is removed next.

Top

The designated end used for stack additions, removals and inspection.

Bottom

The earliest remaining entry beneath entries added after it.

push

Add an entry at the top.

pop

Remove and return the top entry.

peek

Inspect/return the top entry without removing it.

isEmpty

Report whether the stack has zero entries.

Underflow

Attempting a removal or top access with no stored entry.

Overflow

Attempting to exceed a bounded stack’s capacity.

Bounded stack

A stack with a specified maximum number of entries.

Dynamic stack

A stack whose storage can grow under its implementation and resource limits.

Size

The number of currently stored entries.

Capacity

The number of entries accommodated by currently reserved storage or an explicitly stated limit.

Top pointer

A reference or index identifying the top under a specified convention.

Last-occupied-index convention

A pointer convention using −1 for empty and top+1 for size.

Abstract interface

The operations and behaviour promised independently of the storage implementation.

List-backed stack

A stack implemented using one end of a resizable list.

Fixed-array stack

A stack implemented in reserved indexed slots with a top pointer.

Linked stack

A stack using linked nodes with the head/top reference updated on operations.

Amortised cost

Average per-operation cost over a sequence that includes occasional expensive operations.

Growth copy

Copying existing backing entries when obtaining larger array-style storage.

Memory overhead

Storage beyond entry payload, including spare slots, links and metadata.

Peak storage

Maximum simultaneously held storage during an operation or workload.

Undo history

Saved states or edit operations ordered for reversing the most recent edit first.

Snapshot

A saved representation of a state, such as prior document text.

Call stack

A stack of active call frames and their return context.

Backtracking

Returning to recent choices or states to explore another possibility.

Bracket matching

Checking that closing delimiters correspond to the most recent unmatched opening delimiters.

Return value

The item or result supplied to a caller, distinct from stored contents and printed output.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe LIFO?
2. Which describe peek and isEmpty?
3. Push A, push B, pop, push C. Which are true?
4. Which describe empty/full cases?
5. Which follow the last-occupied-index convention?
6. Which describe Python list-backed operations?
7. Which explain performance accurately?
8. Which explain memory trade-offs?
9. Which suit a stack?
10. Which describe Java ArrayDeque in the example?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Explain LIFO using three pushed values.

2. Distinguish pop from peek.

3. Trace push A, push B, peek, pop, push C, pop.

4. Construct a Python stack interface in outline.

5. Explain underflow and overflow in a bounded stack.

6. Trace the top pointer for a capacity4 stack using the last-occupied-index convention.

7. Explain why a list-backed push may have a different cost when full.

8. Compare memory considerations of fixed-array and linked stacks.

9. Explain why a stack is suitable for undo, including one memory limitation.

10. Explain why the parentheses algorithm rejects ")(".

11. Explain why a stack is unsuitable for strict first-come, first-served printing.

12. Describe tests for a stack implementation.

EXPLAIN IT | BACKTRACKING ROBOT

A robot explores a maze and records states needed to return from its most recent choice. Explain why a stack can suit this backtracking order. State what each entry must contain, how push and pop are used, one empty-stack response and a memory limitation. Distinguish this from returning to the oldest pending task.

Reveal an answer outline

Push sufficient return-state or choice information before exploring. Pop the newest unresolved state when backtracking, so nested choices are reversed in LIFO order. Define what happens when no previous state remains. Stored states can be large and exploration can increase depth, so capacity and resource limits matter. Oldest-pending-first would require a different access rule.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.2.3 Stacks and LIFO is coming soon. Complete the matching task and written questions in your exercise book.