At a base level, a stack is simply a list data structure
with a constrained set of methods that make it uniquely suited for some
programming tasks. These methods are
push, which adds an item to the head of
the list and
pop which removes and returns the item in the head position. The
most common analogy is a stack of plates. You place a plate on top of the stack,
and you must retrieve the last plate placed on the stack before you can access
plates below it. In software parlance, a stack is known as a Last-in-First-Out
data structure because the last item pushed on the stack is the first one out
Typically, a Linked List is used when implementing a stack. However, an Array is also a viable option. The reader is encouraged to examine the accompanying code to get a better understanding of how stacks work.
- Memory Management: Operating systems use a stack for managing memory.
- Backtracking: Keep track of tasks so they can be undone if necessary. Think of
what happens when you press
ctrl+zwhile using MS Word, or
uwhen using VIM.
- Graph Depth First Search
- Push: $O(1)$
- Pop: $O(1)$
push: Adds an item to the head of the list pop: Remove item from the head the list and returns it peek: Return item from the head without removing it from the list
Click here for build and run instructions