FIFO queues are used for implementing the first come, first served strategy. For example, let's consider a queue for booking movie tickets (for now we'll pretend that there is no such thing as an online ticket booking system).
The person who comes first and joins the queue gets serviced before the person after him (who joined the queue a bit later). This enforces an order, which is also known as first come, first served or FIFO. According to this, the person who comes earlier is serviced first and moves out of the queue.
A new element queues up at the head and is removed/serviced at the tail, as shown in the following figure:
In the imperative world, it is pretty easy to see how we would implement a FIFO queue. We could maintain the FIFO queue as a singly linked list with two pointers: one at the head and another at the tail.
We will remove the tail node (pop the element off the queue)-an O(n) operation-as we need to traverse the entire list to reach the last element...