Last Updated on December 14, 2022 by Prepbytes
The queue is a linear data structure that works on the principle of First in First out (FIFO). In the queue, the element which is added at least recently is removed first from it. For example, a queue of consumers for a resource or service where the consumer who comes first will be served first.
Given below are the operations of the queue:
Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).
Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).
Front: This function returns the front element of the queue. The time complexity of this function is O(1).
Rear: This function returns the last element of the queue. The time complexity of this function is O(1).
Implementation of Queue in Python
There are many ways to implement a queue in python. Given below are the different ways to implement a queue in python:
- list
- collections.deque
- queue.Queue
Implementation using list
The list is a built-in data structure in python that can be used as a queue. In place of enqueue() and dequeue(), there are append() and pop() functions. However, using the list in the implementation is a quite slow process, as inserting or deleting an item from the beginning requires shifting all of the other elements by one which is having O(N) time complexity.
Code Implementation
queue = []
queue.append(1)
queue.append(2)
queue.append(3)
print("Initial queue")
print(queue)
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("\nQueue after removing elements")
print(queue)
Output:
Initial queue
[1, 2, 3]
Elements dequeued from queue
1
2
3
Queue after removing elements
[]
Implementation using collections.deque
Deque class from the collections module can also be used for implementing the queue. As deque quicker append and pop operations from both ends of the queue, so it is preferred more than list in python. In place of enque and deque, there are append() and popleft() functions. In deque append and pop operations have the time complexity of O(1).
Code Implementation
from collections import deque
q = deque()
q.append(1)
q.append(2)
q.append(3)
print("Initial queue")
print(q)
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())
print("\nQueue after removing elements")
print(q)
Output:
Initial queue
deque([1, 2, 3])
Elements dequeued from the queue
1
2
3
Queue after removing elements
deque([])
Implementation using queue.Queue
There is a built-in module in Python for implementing queues. Syntax for implementing a queue in a variable is Queue(maxsize) where maxsize is the maximum number of elements that can be inserted in the queue. For making an infinite queue set the value of maxsize = 0. This queue always follows the FIFO principle.
Functions available in this module are:
maxsize – Number of elements allowed to insert in the queue.
empty() – Return True if the queue has no element present in it, else return False.
full() – Return True if the number of elements present in the queue is equal to the maxsize. If maxsize value is equal to 0 i.e. the queue will be an infinite queue and for this case full() function will never return True.
get() – Remove and return the element from the front of the queue. If the queue is empty, wait until an element is available.
get_nowait() – Return the element from the front end of the queue which is available, else it will raise QueueEmpty.
put(ele) – This function will put an element in the queue. If the queue is full, then it waits until a free slot is available before adding an element.
put_nowait(ele) – This function will put an element in the queue without blocking. If there is no empty slot in the queue, then it will raise QueueFull.
qsize() – This function will return the number of elements present in the queue.
Code Implementation
from queue import Queue
q = Queue(maxsize = 3)
print(q.qsize())
q.put(1)
q.put(2)
q.put(3)
print("\nFull: ", q.full())
print("\nElements dequeued from the queue")
print(q.get())
print(q.get())
print(q.get())
print("\nEmpty: ", q.empty())
q.put(1)
print("\nEmpty: ", q.empty())
print("Full: ", q.full())
Output:
0
Full: True
Elements dequeued from the queue
1
2
3
Empty: True
Empty: False
Full: False
This article tried to discuss the Implementation of Queues in Python. Hope this blog helps you understand the implementation. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes