- 1.Stacks are a last-in-first-out data structure, typically implemented with arrays
- 2.The stack concept is useful for tracking ordered data that we may need to reverse, e.g. text edits
Brief introduction to stack concepts, methods and applications
A stack (think stack of plates) is an array-like data structure that supports adding and removing only from the end, aka "top" of the stack. In practice we will use arrays to represent stacks, but what's important is the pattern of only adding and removing from the end of an array to model and solve certain types of problems.
The stack concept powers many features we use daily, including:
- 1.Undo and redo in text editors (adding new edits to top of stack and removing them on undo)
- 2.Parentheses-matching in code editors (adding new opening parens to top of stack, removing them on closing paren and highlighting the pair with the same colour)
- 3.Browser history (new pages get added to a stack, clicking back button pops them off the stack)
Because we only ever add or remove from the end of the stack, all stack operations run in
After attempting each problem, find solutions in the Leaderboard tab (HackerRank, may be on left side of page) or Solution or Discuss tabs (LeetCode) on that problem's page. If you get stuck for more than 15 minutes, review and understand the solutions and move on. Come back and re-attempt the problem after a few days.
- 2.Daily Temperatures (LeetCode)
- 1.Hint: Store temperatures and their array indexes in a stack as we iterate through the input array, and pop those temperatures off the stack and populate "num days until warmer temperature" in answer array when we see a warmer temperature.