A queue is a data structure similar to a list. However, the functionality is of a limited nature, because a queue is characterized by the fact that the FIFO principle (First In, First Out) applies here. This means that the first item added to a queue is the first item removed. Adding data is called enqueue, removing it is called dequeue. The classic example of the queue is the printer queue, in which the print jobs are processed one after the other in the order in which they are received. — The figure below shows how a queue works:
Using a list
A queue can be implemented in Python in different ways. One way is to use another data structure available in Python — the list. The code for this looks like this:
# Create a new empty list
queue = list()
# Add items to the queue
queue.append(5)
queue.append(13)
queue.append(22)
queue.append(7)
queue.append(45)
print(queue) # -> [5, 13, 22, 7, 45]
# Remove an item
queue.pop(0)
print(queue) # -> [13, 22, 7, 45]The first number that was added is 5. Following the FIFO principle, this number is the first to be removed, which is implemented here using the pop() method. Index 0 is specified as a parameter (first element of the list or queue).
The following should be noted about this example: The implementation shown does not correspond to the figure above. Because here a new element is always appended to the end of the list with the method append(), and the elements are removed from the beginning of the list with pop(0). This is irrelevant, however, because it is crucial that the FIFO principle is maintained, and that is the case. The following figure comes closer to the implementation as a list:
Using a list is a very simple implementation, but it is not recommended in practice because it has one major disadvantage: by removing the element at index 0, all remaining elements have to be shifted to the left, which is time-consuming. The documentation on data structures in Python states:
However, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).
Using collections.deque
For this reason, the Python library provides collections.deque. Here, a queue is implemented using a linked list. In other words, collections.deque is an implementation of a linked list. The following code example shows the use of collections.deque:
from collections import deque
queue = deque()
# Add items
queue.append(5)
queue.append(13)
queue.append(22)
queue.append(7)
queue.append(45)
print(queue) # -> [5, 13, 22, 7, 45]
# Remove an item
queue.popleft()
print(queue) # -> [13, 22, 7, 45]This is a modification of an example from the official Python documentation, which states the following:
To implement a queue, use
collections.dequewhich was designed to have fast appends and pops from both ends.
As with the list example, an element is always inserted at the end, and an element at the beginning is removed (with queue.popleft()). The element that was added first is therefore the first element to be removed (first in, first out).
Apart from these two examples, there are other ways to implement a queue. For the start I would like to leave it at these two examples. The next article on data structures will then deal with stacks.