Queue in Python

Like a stack, the queue is a linear data structure that stores items in a First In First Out (FIFO) manner. With a queue, the least recently added item is removed first. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
 

Operations associated with queue are: 

• Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity : O(1)
• Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity : O(1)
• Front: Get the front item from queue – Time Complexity : O(1)
• Rear: Get the last item from queue – Time Complexity : O(1)

Implement a Queue in Python

There are various ways to implement a queue in Python. This article covers the implementation of queue using data structures and modules from Python library. Python Queue can be implemented by the following ways:

• list
• collections.deque
• queue.Queue

Implementation using list

List is a Python’s built-in data structure that can be used as a queue. Instead of enqueue() and dequeue(), append() and pop() function is used. However, lists are quite slow for this purpose because inserting or deleting an element at the beginning requires shifting all of the other elements by one, requiring O(n) time.
The code simulates a queue using a Python list. It adds elements ‘a’, ‘b’, and ‘c’ to the queue and then dequeues them, resulting in an empty queue at the end. The output shows the initial queue, elements dequeued (‘a’, ‘b’, ‘c’), and the queue’s empty state.

queue = []
queue.append('a')
queue.append('b')
queue.append('c')
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
['a', 'b', 'c']
Elements dequeued from queue
a
b
c
Queue after removing elements
[]

Traceback (most recent call last):
  File "/home/ef51acf025182ccd69d906e58f17b6de.py", line 25, in 
    print(queue.pop(0))
IndexError: pop from empty list

Implementation using collections.deque

Queue in Python can be implemented using deque class from the collections module. Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. Instead of enqueue and deque, append() and popleft() functions are used.
The code uses a deque from the collections module to represent a queue. It appends ‘a’, ‘b’, and ‘c’ to the queue and dequeues them with q.popleft(), resulting in an empty queue. Uncommenting q.popleft() after the queue is empty would raise an IndexError. The code demonstrates queue operations and handles an empty queue scenario.

from collections import deque
q = deque()
q.append('a')
q.append('b')
q.append('c')
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(['a', 'b', 'c'])
Elements dequeued from the queue
a
b
c
Queue after removing elements
deque([])
 

Traceback (most recent call last):
  File "/home/b2fa8ce438c2a9f82d6c3e5da587490f.py", line 23, in 
    q.popleft()
IndexError: pop from an empty deque

Implementation using queue.Queue

Queue is built-in module of Python which is used to implement a queue. queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. A maxsize of zero ‘0’ means a infinite queue. This Queue follows FIFO rule. 
There are various functions available in this module: 

• maxsize – Number of items allowed in the queue.
• empty() – Return True if the queue is empty, False otherwise.
• full() – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
• get() – Remove and return an item from the queue. If queue is empty, wait until an item is available.
• get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
• put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
• put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
• qsize() – Return the number of items in the queue.

Example: This code utilizes the Queue class from the queue module. It starts with an empty queue and fills it with ‘a’, ‘b’, and ‘c’. After dequeuing, the queue becomes empty, and ‘1’ is added. Despite being empty earlier, it remains full, as the maximum size is set to 3. The code demonstrates queue operations, including checking for fullness and emptiness.

from queue import Queue
q = Queue(maxsize = 3)
print(q.qsize()) 
q.put('a')
q.put('b')
q.put('c')
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
a
b
c
Empty:  True
Empty:  False
Full:  False

Queue in Python – FAQs

What is a queue in Python? 

In Python, a queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It operates like a real-world queue or line at a ticket counter, where the first person to join the queue is the first to be served.

Is the queue FIFO or LIFO?

A queue in Python, as well as in most programming languages, is FIFO (First-In-First-Out). This means that the element that is added first is the first one to be removed.

What is front and rear queue in Python?

• Front: The front of the queue refers to the position where elements are removed (dequeued).
• Rear: The rear (or back) of the queue refers to the position where new elements are added (enqueued).

What is the difference between front and rear in queue?

The main difference between the front and rear of a queue lies in their roles:

• Front: This is where elements are dequeued or removed from the queue.
• Rear: This is where elements are enqueued or added to the queue.

Together, they define the boundaries of the queue structure, with elements flowing from the rear to the front.

What is the difference between queue and lock in Python?

• Queue: A queue in Python (like queue.Queue from the queue module) is a data structure used for managing elements in a FIFO manner, typically used for communication between threads or processes.
• Lock: A lock (like threading.Lock from the threading module) is a synchronization mechanism used to prevent multiple threads from simultaneously accessing shared resources. It ensures that only one thread can execute a critical section of code at a time.

What is the difference between queue and stack in Python?

A queue is FIFO (First-In-First-Out), while a stack is LIFO (Last-In-First-Out). Queues prioritize oldest elements for removal, whereas stacks prioritize newest.