Python Queue Implementation

Python Queue Implementation

  1. Use the Operations to Implement Queue in Python
  2. Use a List to Implement a Queue in Python
  3. Use the collections.dequeue to Implement a Queue in Python
  4. Use the queue.Queue to Implement a Queue in Python

A queue is one of the various linear data structures available in Python and is utilized to store data while following the First In, First Out (FIFO) terminology.

It can be a simple queue, a circular queue, a priority queue, or a double-ended queue.

Use the Operations to Implement Queue in Python

A queue has a couple of operations associated with it, which are:

  • Enqueue: An element is inserted at the rear end of the queue with this operation.
  • Dequeue: An element is removed from the front end of the queue with this operation.
  • isEmpty: It is utilized to figure out whether the queue is vacant or not.
  • peek: The element at the front end is returned while its position remains intact in the queue.
  • size: The quantity of elements present in the given queue is returned with this operation.

All methods are implemented by utilizing Python’s data structures and various libraries.

The three ways to implement Queues in Python:

  • Use a list to implement a Queue in Python.
  • Use collections.dequeue to implement a Queue in Python.
  • Use queue.Queue to implement a Queue in Python.

Use a List to Implement a Queue in Python

Lists are one of the four in-built data structures provided by Python. A list can be utilized to implement a queue in Python.

Lists utilize the append() and pop() functions instead of the generic enqueue() and dequeue() functions respectively.

q1 = [] 
q1.append('x')
q1.append('y')
q1.append('z') 
q1.append('a') 
print("Queue after enqueue operation")
print(q1)
q1.pop(0)
q1.pop(0)
q1.pop(0)
q1.pop(0)
print("\nQueue after dequeue operation")
print(q1)

Output:

Queue after enqueue operation
['x', 'y', 'z', 'a']

Queue after dequeue operation
[]

Using lists to implement a queue is a really slow speed. The time complexity of shifting each element is O(n), which is taxing and comparatively slow compared to the other methods.

Use the collections.dequeue to Implement a Queue in Python

The collections library provides a dequeue class to implement a Queue in Python.

This method makes use of the append() and popleft() functions instead of the generic enqueue() and dequeue() functions respectively.

Dequeue is generally a faster approach than using lists when there is a need to have fast pop and append operations from both sides of the given queue.

from collections import deque
q1 = deque()
q1.append('x')
q1.append('y')
q1.append('z')
q1.append('a')
print("Queue after enqueue operation")
print(q1)
q1.popleft()
q1.popleft()
q1.popleft()
q1.popleft()
print("\nQueue after dequeue operation")
print(q1)

Output:

Queue after enqueue operation
deque(['x', 'y', 'z', 'a'])

Queue after dequeue operation
deque([])

All append and pop operations in Dequeue have a time complexity of O(1), far superior to the time complexity O(n) taken by lists for each operation to implement a Queue in Python.

Use the queue.Queue to Implement a Queue in Python

Python provides an in-built module named queue that can implement a Queue. This method utilizes the queue.Queue(maxsize) function to implement a Queue.

This function contains a lot of parameters which are:

  • maxsize: It specifies the maximum number of items that a Queue can hold.
  • empty(): It returns a true value if the queue is empty, and a false value if it isn’t.
  • full(): Checks whether the queue is full. A true value is returned if maxsize items are contained within the queue.
  • get(): It takes out an element from the queue and returns it. It waits by default until an element is available if the given queue is vacant.
  • get_nowait(): Behaves the same way as the get() parameter, with the only difference being that it does not wait if the queue is vacant and raises QueueEmpty.
  • put(item): It is utilized to add an element into the queue. It waits by default if no free slots are available in the queue.
  • put_nowait(item): Behaves pretty much the same way as the put() parameter, with the only difference being that it does not wait if the queue is full and raises Queuefull.
  • qsize(): The number of elements contained within the queue is returned through this parameter.
from queue import Queue
q1 = Queue(maxsize = 4)
# Now adding elements to queue
q1.put('x')
q1.put('y')
q1.put('z')
q1.put('a')
print("Is the queue empty?", q1.empty())
#Now removing elements from queue
q1.get()
q1.get()
q1.get()
q1.get()
print("Is the queue empty now?", q1.empty())

Output:

Is the queue empty? False
Is the queue empty now? True