Queue data structure

A queue is a sequence of people or objects waiting to be attended to. Some examples include a queue of people waiting at a counter, a queue of swimmers that are ready to dive in to a pool, and a queue of songs in a playlist:

Figure 10

Just like in a stack, there are two types of operations—one for inserting items into a queue, and one for removing items from a queue. When a person joins a queue, he or she must stand behind the last person. The operation of adding an item to a queue is called enqueue. The first person to be attended to in a queue is the person standing in the front. The operation to remove an item from a queue is called dequeue. Queue operations can be seen in the following diagram:

Figure 11

Since the first object inserted is the first one to be removed, this data structure is called first in first out (FIFO). In Python, we can use the deque class to create queue objects. The deque class provides two methods—one method, append, for inserting items, and a...