A lesson from the data structures and algorithms bootcamp. About a 11 minute read.
A stack is last in, first out. You only touch the top, and that single restriction is the whole point: it is exactly the right memory for anything nested. It is also not just a data structure you might reach for. It is the thing your language uses to run a function call, which means every recursive tree traversal you write is a stack whether you can see it or not.
A stack is a sequence where you push onto the top and pop off the top, and there is no operation for reaching into the middle. That sounds like a limitation and it is. It is also why the structure is useful: a stack is not a worse list, it is a list with a rule attached, and the rule happens to be the exact shape of nesting. The last thing you opened is the first thing that has to close. That is true of brackets, of HTML tags, of function calls, of undo history, and of the path from a tree's root down to wherever you currently are. When a structure's constraint matches a problem's constraint, the code stops needing to check anything.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles