What is a Queue?
Queue is a linear, or sequential, collection of items that is very similar to Stack but with few differences. As it is clear from its name, it functions as a real queue. The items added the earliest are removed first — FIFO (First In, First Out) and items added the latest are removed last — LILO (Last In, Last out).
Queue provides two main operations — enqueue() and dequeue(). Enqueue and dequeue are the same operations as adding new items and removing operations respectively with a small limitation. As an additional operation, we can add — peek(). It allows to find out what is the first item in the queue.
Since Queue is a sequentially structured, its inner storage is usually implemented using Arrays, Dynamic Array, or LinkedList. Taking into account the efficacy of add() and remove() operations provided by LinkedList, it is the best to use LinkedList as the inner storage of Queue.
Time complexity of operations provided by Queue are as follows:
Enqueue — O(1)
Dequeue — O(1)
Peek — O(1)
Let’s discuss all the operations one by one.
Enqueue is a similar operation to adding a new item. However, there is a small limitation. Items are added strictly into one position, that is the end of the inner-storage. The right order of the items are kept, the earliest added items are always at the beginning of the queue, see the above illustration)))) Here FIFO (First In, First Out) takes its origin, since the first added item is removed firstly.
Dequeue is a similar operation to removing an item with a small difference. The earliest added items have higher priority and are removed firstly — First In, First Out. See the above illustration for more clarity.
Peek is an additional handy operation that allows to find out what is the first item in the queue. However, peek() is not a fundamental operation that implements the concept of Queue.
The concept of Queue is pretty straightforward but has come essential in graph-related algorithms. Checkout breadth-first-search algorithm for queue usage)))
Next topic awaiting topic is Dequeue — a data structure that combines features of both Stack and Queue.
If you are curious to dive deeper and play around with the Queue, I recommend to implement the discussed operations by yourself and test.
The following are the links for: