Queue Data Type#

Have you ever waited in line?[1]

A line-up of people waiting

The line-up is formally a “queue”. The first person to arrive is at the beginning. As more arrive, they enter behind, in the order of arrival. People in the line-up receive service in the order of arrival, with the person at the start of the line always being the next to be served.

This is the essence of the data type called Queue. The first item that enters a Queue is the first item that gets taken out of the Queue. That is: queues are First In First Out (FIFO) data structures. Sometimes queues are also called Last In Last Out (LILO).

As with stacks, queues are homogeneous. Access to a Queue is at the beginning or front for removing an item and at the end or back for adding an item. These are the common operations:

  • see the item at the beginning (peek)

  • place a new item at the end (add or enqueue)

  • remove an item from the beginning (remove or dequeue)

  • see whether the queue is empty (empty).

Java Queue Library#

Java does not contain a pure Queue library. Rather, Java provides us with a Queue interface that other libraries implement. The programmer needs to decide what background implementation can be handled, and pick an appropriate Queue.