AlgorithmsCodingDataStructures A stack is a linear data structure that is based on LIFO (last-in first-out) ordering. It can be implemented using a linked list.
Complexity:
Add: O(1)
Remove: O(1)
Access: O(n)
A stack is useful in the following situations:
- Backtracking in recursion: place temporary data on stack and remove as you backtrack
- Implement recursive algorithm iteratively (recursion is implemented with function stack)
- Depth-first search