Stacks: Last In, First Out
A collection where the only value within reach is the one added most recently. Push puts a value on top, pop takes it off, and that single restriction is what makes undo, back buttons and bracket checking straightforward.
What a learner can do afterwards
- Trace the contents of a stack through a run of pushes and pops
- Implement push and pop over a list and say what a pop from an empty stack should do
- Match a task such as undo history or bracket matching to the last-in-first-out rule
1 · Read
A stack is a pile you only touch from the top. Push adds an item on top and pop removes the top item, so the last thing added is always the first thing out. That is the whole rule: last in, first out. Everything else about stacks is just this rule applied carefully.
To trace a stack, draw the pile after every single step and never skip one. Push writes the value on top, pop crosses the top value out and hands it back. Try it: push 4, push 7, pop, push 9 leaves 9 on top with 4 beneath. Popping an empty stack is an error, so decide upfront what your program does there: raise an error, return a sentinel, or refuse the operation.
In Python a plain list works as a stack with append as push and pop as pop. Appending puts the value at the end and popping takes it back off, which mirrors the pile exactly. Indexing from the end with minus one lets you peek at the top item without removing it. Peek, compare, and only pop when they match: that rhythm keeps bracket checking honest.
Real programs lean on stacks wherever history must unwind in reverse. An editor undo stack pushes each change and pops it when you press undo, so the newest change vanishes first. A bracket checker pushes opening brackets and pops one for each closing bracket, and any mismatch or leftover means the nesting is broken. When a task says most recent first, reach for a stack.
Last in, first out: push on top, pop from top.
More to read
3.1 Introduction to Data Structures and Algorithms
A stack is a pile you only touch from the top. Push adds an item on top and pop removes the top item, so the last thing added is always the first thing out. That is the whole rule: last in, first out. Everything else about stacks is just this rule applied carefully.
To trace a stack, draw the pile after every single step and never skip one. Push writes the value on top, pop crosses the top value out and hands it back. Popping an empty stack is an error, so decide upfront what your program does there: raise an error, return a sentinel, or refuse the operation.
3.4 List basics
In Python a plain list works as a stack with append as push and pop as pop. Appending puts the value at the end and popping takes it back off, which mirrors the pile exactly. Indexing from the end with minus one lets you peek at the top item without removing it.
Peeking matters when the algorithm must look before it leaps, like checking a closing bracket against the opening one on top. Peek, compare, and only pop when they match. That three step rhythm keeps the stack honest and makes traces easy to check line by line.
9.1 Modifying and iterating lists
Real programs lean on stacks wherever history must unwind in reverse. An editor undo stack pushes each change and pops it when you press undo, so the newest change vanishes first. A bracket checker pushes opening brackets and pops one for each closing bracket, and any mismatch or leftover means the nesting is broken.
Both jobs fail without the last in first out rule. Undo would erase your oldest work first and bracket matching would pair closers with the wrong openers. When a task says most recent first, reach for a stack and trace pushes and pops one step at a time.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Nothing; this is a starting point.
Optional connections
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.