Programming technique · B2.2.3
Stacks
A stack restricts access to one end, called the top. The most recently pushed item is therefore the first item available to inspect or remove.
The four required operations
push
Add one item at the top.
pop
Remove and return the top item.
peek
Return the top item without removing it.
isEmpty
Check whether a top item exists.
Using Java's supplied stack operations
Java can represent a stack with a Deque backed by ArrayDeque. The collection is supplied; students do not need to implement the internal structure.
Using a Python list as a stack
A Python list supplies the required end operations: append() pushes, pop() removes the top, stack[-1] peeks and len(stack) == 0 checks whether it is empty.
| Abstract operation | Java call | Returned value | Stack after operation, top first | Stored count |
|---|---|---|---|---|
push("Draw circle") | history.push(...) | — | Draw circle | 1 |
push("Add colour") | history.push(...) | — | Add colour, Draw circle | 2 |
peek() | history.peek() | Add colour | Add colour, Draw circle | 2 |
pop() | history.pop() | Add colour | Draw circle | 1 |
isEmpty() | history.isEmpty() | false | Draw circle | 1 |
| Abstract operation | Python call | Returned value | Stack after operation, top first | Stored count |
|---|---|---|---|---|
push("Draw circle") | history.append(...) | — | Draw circle | 1 |
push("Add colour") | history.append(...) | — | Add colour, Draw circle | 2 |
peek() | history[-1] | Add colour | Add colour, Draw circle | 2 |
pop() | history.pop() | Add colour | Draw circle | 1 |
isEmpty() | len(history) == 0 | False | Draw circle | 1 |
Performance and memory, explained qualitatively
Direct top access
The stack abstraction works only at the top. It does not search for or remove an arbitrary middle item.
Stored memory changes
push stores one more item and pop stores one fewer. peek and isEmpty do not change the stored count.
Check before removal
An empty stack has no top item. Check isEmpty before calling pop or relying on peek.
Check before removal
An empty list has no final item. Check the length before calling pop() or reading stack[-1].
Challenges Choose one
Choose a challenge that feels appropriate for you. Code heat is only a rough estimate, not a fixed level.
Stack Operation Trace
SelectedCollect the stack tracing sheet from the front of the class. Before running the supplied Java program, trace every operation by hand. Record the returned value, stack state from top to bottom and stored-item count after each step. Hand the completed tracing sheet to your teacher, then run the program and correct any mistakes in a different colour. Explain why peek leaves the stack unchanged. Do not implement a custom stack.
Undo History
SelectedUse a Deque as a stack of action names. Provide options to add an action, view the next action that would be undone, undo the latest action and report when no actions remain. Keep stack operations in clear methods and add a short explanation of why last in, first out matches undo behaviour. Do not build your own stack class.
Bracket Checker
SelectedUse a Deque<Character> as a stack to decide whether round, square and curly brackets are balanced. Push opening brackets, compare each closing bracket with the top item and reject an unmatched or incorrectly ordered pair. Test nested, adjacent, missing and extra brackets. Explain why a stack is suitable.
Selected challenge
This choice is shared with the portfolio setup page.
Create your challenge folder
Run this command before starting. It creates the correct empty folder inside your portfolio.
Complete the challenge
Write and test your own solution in the folder created above.
Optional scaffolded support
Use only as much support as you need. The templates organise the program but leave the important algorithm unfinished.
Submit for review
Run this when your program is complete. It creates the README, commits the folder and pushes it.