Abstract
- Linear
- Aka Array/Linked List with limitations
- Can be used in an online ordering system
Complexity
Space
Time
- O(1) to offer() - push in an element
- O(1) to poll() - pop out an element
- O(1) to peek() - read the element that is the first to be pop out
Implementation
- Visual
- push() at the rear index
- pop() & peek() at the head index
- Visual
- push() from tail node
- pop() & peek() from the head node
- The difference in the 2 implementation is similar to Stack implementation comparison
Variant
Monotonic Queue
- Implemented with Deque, I am not sure if it can be implemented with Queue (FIFO)
- Finding the biggest element in a sliding window