A queue is another of the standard data structures that we find throughout Computer Science. Unlike the stack, the queue is a FIFO structure (First In First Out). The items which are placed in a queue are removed in the same order they were added. The structure of a queue works in a similar way to a train entering a tunnel, the first carriage into the tunnel is the first carriage to leave it, similarly, the second in is the second out, etc.
Source Wikimedia Commons
A queue has certain standard methods and attributes, which are expected, (we'll use the normal names for them):
We're going to use a list to hold the items in our queue, but we could use any other suitable data structure as long as it keeps the items in the order they were added.
Create a Queue class with each of the methods described above, but just insert the keyword pass as the contents of each method body for now.
For the body of the constructor method, create an empty list and assign it to an attribute of the class. This sounds complicated but actually, just means, do the following:
self.contents = []
Implement the methods listed above in a similar manner.
Once the queue is implemented, we need to test that it works by creating a queue, adding stuff to it, removing the item at the front of the queue, checking if it is empty, checking the size etc.
Queues are incredibly useful data structures with numerous uses throughout computer science. Streaming data services make extensive use of queues, events triggered by a player in a video game are often stored in a queue so that they can be processed in the order they were triggered and many algorithms make use of queues in order to retain the order in which things are processed.
There's a Python file here with example code for the Queue class: Dave's Queue
My name is Dave Ames. I've been a teacher for 25 years and for the last few of those I've been teaching both children and other adults, especially teachers to program in a variety of environments, but mostly Python.
This is the second a series of posts I'm going to be posting, on Data Structures in Python. This one is actually part of the content of a workshop I delivered to some teachers today.