Using Queues in Python
In Programming and software development, data structures are used to store and arrange a set of values. There are various types of data structures for different use cases. They include stacks, queues, lists, etc. This article focuses on queues and basic operations that could be carried out on them.
What is the Queue Data Structure?
A Queue data structure works like queues in real life such as at shopping malls, payment counters, and airplane onboarding.
What are the applications of Queues?
- Printer queues
- Customer service hotlines
- CPU Scheduling
The FIFO Concept
FIFO is an abbreviation for First In, First Out which explains the order by which actions carried out on queue work. The first object to come on the queue is the first object that goes out.
Hence, the addition of new elements happens from the end of the queue while the removal of elements happens at the beginning of the queue, just as queues in shopping malls.
This is in contrast to the stack data structure which addition(push) and removal(pop) of elements happen at the end of the queue. This is described as Last In, Last Out, LIFO You can learn more about Stack in this article, Stacks in Python.
Major Queue Operations
- enqueue(): this entails adding new elements to the end of the queue
- dequeue(): this involves removing members of the queue from the front of the queue.
Coding a Queue Class in Python
Classes are modular elements of computer programs in the object-oriented programming concept, OOP. Having a basic understanding of how classes work in OOP is essential to be able to use classes. You can study object-oriented programming in Python through this tutorial, Python — Object Oriented.
Going forward, we shall import the deque() datatype because using the list data type like in a Stack class is only efficient when we want to add or remove from the end of the list.
It is difficult and slow to try to remove an element of a list from the beginning of the list. However, we need to remove a queue element from the beginning.
Therefore, we shall import the deque() datatype which is inbuilt in Python.
from collections import dequeThen, let us declare our Queue class.
from collections import deque
#new addition
class Queue:
def __init__(self):
self.items = deque()We have declared the Queue class and added the __init__() constructor which enables us to be able to use objects of the Queue class.
The items is a list that we would use to hold the elements of our queue.
enqueue()
We shall now add the enqueue() function which adds a new element to the queue from the rear.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
#new addition
def enqueue(self, item):
self.items.append(item)dequeue()
The dequeue() function will be used to remove the element at the front of the queue. We shall use the popleft() functionality to remove an item from the left.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
#new addition
def dequeue(self):
return self.items.popleft()peek()
Now, we shall add the peek() function to return the foremost data item in the queue without removing it.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
#new addition
def peek(self):
return self.items[0]is_empty()
Let us add an is_empty() function that tells us if the Queue is empty. The len() functionality returns the number of elements in a list. Therefore, we will use len() to check when the length of our queue is 0.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
def peek(self):
return self.items[0]
#new addition
def is_empty(self):
return len(self.items) == 0size()
We can also use the len() functionality to check the number of items in our queue. Let us, therefore, create a function which we can call size() to return the size of our queue
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
def peek(self):
return self.items[0]
def is_empty(self):
return len(self.items) == 0
#new addition
def size(self):
return len(self.items)The above functions are some of the common operations that could be done on queues.
Let us, now, add the __str__() to in order to use print statements in our program
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
def peek(self):
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
#new addition
def __str__(self):
return str(self.items)We can test the above code with print statements as below. Before using the print statements, we need to add a conditional statement, if "__name__" = "__main__" to check if the current file is the main file. This only helps us to be able to import our Queue class in other Python files so the class could be used there.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft()
def peek(self):
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
def __str__(self):
return str(self.items)
#new addition
if "__name__" = "__main__":
q = Queue()
print(q)
print(q.is_empty())
q.enqueue("1")
q.enqueue("2")
q.enqueue("3")
q.dequeue()
q.enqueue("4")
q.enqueue("5")
q.enqueue("6")
q.dequeue()
print(q)
print("size of the queue: ", q.size())
print("foremost item in the queue:", q.peek())
print(q)For each of the print statements in the code above, we have the following outputs:
deque([])
True
deque(['3', '4', '5', '6'])
size of the queue: 4
foremost item in the queue: 3
deque(['3', '4', '5', '6'])Conclusion
We have briefly discussed the queue data structure and the major operations performed on queues. Queue operations happen in the FIFO order, First In, First Out. Queues are very useful when implementing algorithms in computer science such as the Breadth-First Search algorithm used in flight reservation systems.
Thank you for your patience and for taking out time to read my post. I write here on Medium. You can reach out to me with questions, and ideas via Twitter @jkayLight
