Queues in Python
A Queue
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
Queue Class Description
A queue has certain standard methods and attributes, which are expected, (we'll use the normal names for them):
- Queue() this will call the constructor to create a new empty queue object and return it.
- enqueue(item) this will add a new item to the rear of the queue.
- dequeue() remove the front item from the queue and return its' value. The queue is changed as a result.
- is_empty() check if the queue is empty. Return True if it is, False otherwise.
- size() returns the number of items in the queue.
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.
Exercise
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.
- enqueue(item) insert the item into the list at position 0.
- dequeue() use pop to remove the last item from the list.
- is_empty() check if the list is empty and return True or False accordingly (there are various ways to do this).
- size() return the length of the list.
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.