- First in, First out (FIFO) e.g. people on a queue.
- Enqueue to add element to the back of the queue.
- Dequeue to remove element from the front of the queue.
- Add at one end, remove from the other end.
Current applications:
- Job queues (printers).
- Processing requests (web servers).
- CPU and disk scheduling.
- Process synchronization.
- Call centers.
How you can use them:
- Breadth-first search.
- Maintaining order.
- Concurrent programming.
- Simple Queue.
- Circular Queue.
- Priority Queue.
- Double Ended Queue (Deque).
- Last in, First out (LIFO) e.g. stack of books or plates.
- Push to add element to the top of the stack.
- Pop to remove element from the top of the stack.
- Add and remove from one end.
Current applications:
- Back button in browsers.
- Function call stack.
How you can use them:
- Depth-first search.
- Replace recursion.
- String parsing.
- Reversing.
- Evaluating expressions.
- Space complexity; most times it is O(n).
- Time complexity; deletion and insertion O(1), visiting all elements O(n).
- How they are implemented, try implementing one with a list.
- How common operations work.
- Adding an element.
- Removing an element.
- Checking if it is empty.
- Checking if it full.
- Peek - looking at the top or front element without removing.
https://leetcode.com/problems/min-stack/
https://leetcode.com/problems/valid-parentheses/
https://leetcode.com/problems/implement-stack-using-queues/
https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/
https://leetcode.com/problems/basic-calculator-ii/
https://leetcode.com/problems/reveal-cards-in-increasing-order/
https://leetcode.com/problems/simplify-path/
https://leetcode.com/problems/remove-duplicate-letters/
https://leetcode.com/problems/find-the-winner-of-the-circular-game/
- https://www.programiz.com/dsa/stack
- https://www.programiz.com/dsa/queue
- Stacks and Queues (cmu.edu)
- https://www.educative.io/blog/data-structures-stack-queue-java-tutorial
- https://introcs.cs.princeton.edu/java/43stack/
- https://leetcode.com/explore/learn/card/queue-stack/
- https://www.interviewcake.com/concept/python/stack
- https://www.interviewcake.com/concept/python/queue
- video on stacks & queues by Gayle Laakmann McDowell