stack
A collection where the last item added is the first one removed, like a pile of plates.
In more detail
A stack supports push, to add on top, and pop, to remove from the top, both O(1). A Python list is an ideal stack: use append and pop at the end. Stacks power undo history, bracket matching, expression evaluation, depth-first search and the call stack itself.
Related terms
- LIFO — Last in, first out: the ordering rule of a stack, where the newest item is always the next to leave.
- push and pop — The two basic stack operations: push adds an item to the top and pop removes and returns the item on top.
- queue — A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
- call stack — The region of memory where a running program keeps one frame for each function call that has started but not yet returned.
- balanced brackets — The classic stack exercise of checking that every opening bracket in a string has a matching closing bracket in the right order.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers