Intro
A Queue is a linear AbstractDataType that’s a collection of elements that maintains Sequence. Meaning elements are ordered. In a Queue, elements are added to the end, this is known as an enqueue operation. Whereas elements are removed from the other end, and this is called dequeue.
Since queues are abstract, they can be implemented using arrays or singly linked lists.
Queues famously follow a FIFO insertion and removal model. Elements are grabbed/removed from the head of the queue and others are added to the end. Just like a real world queue or line-up.
// BFS is commonly implemented using Queues!
Time complexity
| Operation | Big-O | Note |
|---|---|---|
| Enqueue/Offer | O(1) | |
| Dequeue/Poll | O(1) | |
| Front | O(1) | |
| Back | O(1) | |
| isEmpty | O(1) |
Edge cases
- Empty queue
- Queue with one item
- Queue with two items