Implementing a queue in Python - using deque
Introduction
There are a number of in-built methods we could use to implement a queue structure. Lists have append and pop functions which we could use, for example. If you add an item to the end of a queue, these functions will be fast. If you remove an item from the front, however, they will be slow (in computing terms) because not only do you have to remove the item, you have to shift all of the other items along as well. In Big O terms, using lists in this way is rated as an O(n) operation. A much better approach would be to use a library with a specific object designed for fast queue manipulation. Python comes with a library called collections, and in there, is 'deque'. This is pronounced 'deck' (not 'de-queue') and will allow us to create an efficient queue data structure. Using Big O notation, it improves our operations in our queue to a 0(1) from the list's O(n) efficiency. Deques could also be used for implementing stacks, although we used a different approach (writing our own functions and class) when we looked at that.
Collections deque
Deque comes with a wide range of in-built functions, including append, popleft, clear and count. You can set the queue to be an umlimited size, or make it a fixed size. We can also use other functions such as len and in. You can find a summary of all of the functions by searching for Python Collections deque.
Copy and paste this code into Python:
#deque is pronounced 'deck' and is short for
#'double-ended queue'. Import deque from the
#collections library.
from collections import deque
#Create a queue of unlimited size. The front of the queue
#is on the left. The back of the queue is on the right.
queue = deque(['Arsenal', 'Barnet', 'Coventry City'])
print('The items in the queue:',queue)
queue.append('Newcastle United') #Add Newcastle United
print('Added Newcastle United:',queue)
queue.append('Southampton') #Add Southampton
print('Added Southampton:',queue)
queue.popleft() #Remove Arsenal
print('Removed Arsenal:',queue)
temp = queue.popleft() #Remove Barnet
print('Removed Barnet:',queue)
print('The last item removed was',temp)
queue.append('Coventry City')
queue.append('Coventry City')
print('Add Coventry City twice ....')
print('The items in the queue:',queue)
print('Count the instances of Coventry City',queue.count('Coventry City'))
queue.clear() #Empty the queue
print('Empty the queue')
print('The items in the queue:',queue)
print('')
#The following queue can hold a maximum of three items.
#If items are added when the list is full, a corresponding
# number of items from the opposite end are removed.
queue = deque(['Arsenal', 'Barnet', 'Coventry City'],3)
print('The items in the queue:',queue)
print('The length of the queue is',len(queue))
queue.append("Newcastle United")
print('Added Newcastle United:',queue)
print('The length of the queue is still',len(queue))
print('Remove Barnet ....')
temp = queue.popleft() #Remove Barnet
print('The items in the queue:',queue)
print('The last item removed was',temp)
print('The length of the queue is',len(queue))
As you can see, we have imported deque from collections. We then tried out some of the available functions in deque, carefully printing out the results after each experiment and checking that the queue worked in the way we expected it to. We should note that when using this deque object to implement a stack or a queue, the data structures are not strictly enforced; it is possible to do operations on the data in the stack or queue in a way that is inconsistent with how they should work (as a FIFO data structure for queues or a LIFO data structure for stacks, for example). It is up to the programmer to use the range of functions in a way consistent with the data structure being created and used. This could be a source of programming bugs, however, so care must be taken!
Creating our own queue structure
If we want to enforce a strict queue structure, we would need to create our own set of functions or a class in exactly the same way that we did when we looked at stacks. In the following implementation, we will assume that the back of the queue is at position 0 in the list.
Copy and paste this code into Python:
class Deque:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def add_rear(self, item):
self.items.insert(0,item)
def remove_front(self):
return self.items.pop()
def size(self):
return len(self.items)
clubs = Deque()
print(clubs.is_empty())
clubs.add_rear('Arsenal')
clubs.add_rear('Birmingham')
clubs.add_rear('Cardiff')
clubs.add_rear('Derby')
print('The size of the deque is',clubs.size())
print('The back of the queue is',clubs.items[0])
print('The front of the queue is',clubs.items[-1])
print('Remove one item from the front of the queue (Arsenal)')
clubs.remove_front()
print('The front of the queue is now',clubs.items[-1])
print('Add one item to the rear of the queue (Everton)')
clubs.add_rear('Everton')
print('The back of the queue is',clubs.items[0])
As you can see, we have only provided a method to add an item to the back of the queue and remove one from the front, in addition to some methods to check if the queue is empty and to get its size. This would be fine for a FIFO queue, but we should note that there are other types of queues - we could easily add extra methods to our class if we needed to. For example, we could add a method to add an item to the front of the queue as well as the back, or one that can remove an item from the back of the queue as well as the front. We could also add a method to print out the contents of the whole queue.
Tasks
Q1. Add extra methods to the class to add an item to the front of the queue as well as the back, and one that can remove an item from the back of the queue as well as the front.
Q2. Add a method to print out the contents of the queue.
Q3. Write a program that uses a stack to reverse the items in a queue.