A stack is an abstract linear data structure that serves a particular perfomance of operations. The principle operations are; push and pop LIFO - Last In First Out
The name "stack" for this type of structure comes from the analogy to a set of physical items stacked on top of each other.Stacks can be used with Arrays or Linked List
A stack is implemented using a dynamic array or a singly linked list
Arrays - allow cache locality, which make them technically fast when accessing items.
Linked List - have extra memory associated with them, because we have to hold on to the pointers
On the other hand, Linked List have more dynamic memory compared to Arrays.
- Empty stack. Popping from an empty
- Stack with one itme
- Stack with two items
| Lookup | pop | push | peek | isEmpty |
|---|---|---|---|---|
| O(n) | O(1) | O(1) | O(1) | O(1) |
- push - add element to the last item
- pop - remove the last element
- Peek/top - view the top most item
- Valid Parentheses
- Implement Queue using Stacks
- Generate Parentheses
- Min Stack
- Asteroid Collision
- Evaluate Reverse Polish Notation
- Basic Calculator
- Basic Calculator II
- Daily Temperatures
- Car Fleet
- Trapping Rain Water
- Largest Rectangle in Histogram
