data-structures Intro to Queue


The queue is a FIFO (first-in, first-out) data-structure, i.e. the first element added to the queue will be the first element removed ("first out").

Let us consider the example of customers waiting to be helped. Alice, Bob, and Dan are all at the supermarket. Alice is ready to pay, so she approaches the cashier. Alice is now in the queue. She is the only person in the queue, so she is both at the front and at the back.

Now, the queue looks like this:

              | Alice | cashier
                ▲   ▲
back of queue ──┘   └── front of queue

Now Bob and then Dan approach the cashier. They are added to the queue. Alice is still at the front, and Dan is at the back:

              |  Dan  ||  Bob  || Alice | cashier
                ▲                     ▲
back of queue ──┘                     └── front of queue

Adding a person to the queue is the enqueue operation. Alice, Bob, and Dan have been enqueued. As the cashier helps each customer, they will be removed from the queue. This is the dequeue operation. Customers, which represent the data elements in our queue, are dequeued from the front of the queue. This means that the first customer that approached up to the cashier was the first customer to be helped (FIFO).