Queue in Python

Board Infinity -

Introduction

Similar to a stack, a queue is a linear data structure that uses FIFO (First In, First Out) ordering to store items. A queue removes the least recently added item first. Any line of customers waiting to access a sale where the customer who arrived first can access first is a good example of a queue.

Operations on Deque

  • Enqueue: Adds an element to the queue. Overflow conditions are described as the queue being full. Time Complexity: O (1)
  • Dequeue: Remove an element from the queue. In the same order that they are pushed, the items are popped. It's called an underflow condition if the queue is empty. Time Complexity: O (1)
  • Front: Get the first item in the queue; Time Complexity: O (1)
  • Rear: Obtain the last item in the queue. Time Complexity: O (1)

Implementation

A queue can be implemented in Python in a number of different ways. This blog describes how to implement a queue using Python library modules and data structures.

The following methods can be used to implement queue in Python:

  • list
  • collections.deque
  • queue.Queue

Examples

Now we know what is Queue in Python, so lets see how to implement it using different approaches:

Example 1

Implementation using list

List is a data structure that comes with Python and can be used as a queue. Append() and pop() functions are used in place of the enqueue() and dequeue() functions. Lists, however, take a long time to perform this operation because adding or removing an element from the beginning requires shifting every other element by one, which takes O(n) time.

# Initializing a queue
queue = []

# Pushing elements to the queue
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

print("Starting queue")
print(queue)

# Removing elements from the queue
print("\n3 Elements are being Removed from the Queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")
print(queue)

Output:

Starting queue
[1, 2, 3, 4]

3 Elements are being Removed from the Queue
1
2
3

Queue after removing elements
[4]

write your code here: Coding Playground

Example 2

Implementation using collections.deque

Deque or Doubly Ended Queue in Python is implemented using “collections” module. By using Deque, we can do push and pop operations in O(1) time complexity from both the ends of the collection. So, in some cases Deque is preferred over the list as they are faster as compared to the list.

# Initializing a deque

from collections import deque
 
# Initializing a queue
q = deque()

# Pushing elements to the queue
q.append(1)
q.append(2)
q.append(3)
q.append(4)

print("Starting deque")
print(q)

# Removing elements from the queue
print("\n3 Elements are being Removed from the deque")
print(q.popleft())
print(q.popleft())
print(q.popleft())

print("\nDeque after removing elements")
print(q)

Output:

Starting deque
deque([1, 2, 3, 4])

3 Elements are being Removed from the deque
1
2
3

Deque after removing elements
deque([4])

write your code here: Coding Playground

Example 3

Implementation using queue.Queue

Python's built-in module Queue is used to implement queues. queue. Queue(maxsize) sets a variable's initial value to maxsize, its maximum size. An infinite queue is indicated by a maxsize of zero "0." The FIFO rule is used in this queue.

from queue import Queue

q = Queue(maxsize = 4)

print(q.qsize())

# Adding of element to queue
q.put(1)
q.put(2)
q.put(3)
q.put(4)

print("\nQueue is Full?: ", q.full())

print("\n3 Elements are being Removed from the queue")
print(q.get())
print(q.get())
print(q.get())

print("\nEmpty Queue?: ", q.empty())

print("Full Queue?: ", q.full())

Output:

0

Queue is Full?:  True

3 Elements are being Removed from the queue
1
2
3

Empty Queue?:  False
Full Queue?:  False

write your code here: Coding Playground