How to implement a queue in Python

By: Rajesh P.S.

Queues in Python can be implemented using the built-in Queue module. This module provides various classes for implementing different types of queues, such as a simple queue, a priority queue, and a LIFO queue. Each of these classes provides a set of methods for performing common queue operations, such as adding elements to the queue, removing elements from the queue, and checking the size of the queue.

Following is an example of how to use the Queue module in Python:

import queue # Create an empty queue q = queue.Queue() # Add elements to the queue q.put('red') q.put('green') q.put('blue') # Check if the queue is empty if q.empty(): print('Queue is empty') else: print('Queue is not empty') # Get the size of the queue print('Queue size:', q.qsize()) # Remove elements from the queue print('Removing', q.get()) print('Removing', q.get()) print('Removing', q.get()) # Check if the queue is empty again if q.empty(): print('Queue is empty') else: print('Queue is not empty')

Continue Reading...

#Output: Queue is not empty Queue size: 3 Removing red Removing green Removing blue Queue is empty

In the above example, first create an empty queue using the Queue class from the queue module. Then add three elements to the queue using the put method. Check if the queue is empty using the empty method and print the size of the queue using the qsize method. Next, remove the elements from the queue using the get method and print them to the console. Finally, check if the queue is empty again using the empty method.

Python Queue

A Python queue is a data structure that is used to store and manage a collection of elements in a first-in, first-out (FIFO) manner. In other words, the elements that are added first to the queue are the first ones to be removed. A Python queue can be thought of as a container that holds a sequence of items, much like a stack or a list, but with a different set of operations.

Python queues are commonly used in applications that involve processing large amounts of data or tasks in parallel, where each task or data item is added to a queue, and a set of worker threads or processes are responsible for removing items from the queue and processing them. Queues can also be used for implementing data pipelines and for coordinating communication between different parts of a system.

One of the main benefits of using a Python queue is that it provides a simple and efficient way to manage a large number of elements in a thread-safe manner. Python queues are designed to be thread-safe, meaning that they can be accessed and modified by multiple threads or processes simultaneously without causing errors or inconsistencies in the data. This makes queues a powerful tool for building concurrent and parallel applications in Python.

Different types of Queues in Python

There are several different types of queues that you can use depending on your use case. Following are some of the most common types:

Queue:

The Queue module in Python provides a FIFO implementation of the queue data structure. This means that the first item added to the queue will be the first one to be removed. This module provides a simple and efficient way to manage work items.

To create a simple queue, you can use the Queue class from the Queue module.

import queue # create a simple queue q = queue.Queue()

This creates an empty queue that can hold an unlimited number of items.

LifoQueue:

The LifoQueue module provides a LIFO (last-in, first-out) implementation of the queue data structure. This means that the last item added to the queue will be the first one to be removed. This can be useful for implementing tasks such as undo-redo functionality.

To create a LIFO (Last-In-First-Out) queue, you can use the LifoQueue class from the Queue module.

import queue # Create an empty LifoQueue q = queue.LifoQueue() # Add elements to the LifoQueue q.put('Item 1') q.put('Item 2') q.put('Item 3') # Access elements in the LifoQueue print(q.get()) # Remove and return the last item added to the queue (i.e., 'Item 3') print(q.get()) # Remove and return the second-to-last item added to the queue (i.e., 'Item 2') print(q.get()) # Remove and return the first item added to the queue (i.e., 'Item 1') # Check if the LifoQueue is empty print(q.empty()) # Returns True if the queue is empty, False otherwise

#Output: Item 3 Item 2 Item 1 True

This will create a LifoQueue q and add some elements to it using the put() method. You can access elements in the LifoQueue using the get() method, which will remove and return the last item added to the queue (i.e., the item that was added most recently). You can also check if the LifoQueue is empty using the empty() method, which returns True if the queue is empty and False otherwise.

PriorityQueue:

The PriorityQueue module provides a way to prioritize items in the queue based on their importance. Each item is assigned a priority value, and the queue ensures that higher priority items are removed first. This can be useful for managing tasks that have different levels of importance.

To create a priority queue, you can use the PriorityQueue class from the Queue module.

import queue # Create an empty priority queue q = queue.PriorityQueue() # Add elements to the priority queue q.put((3, 'Priority 3')) q.put((1, 'Priority 1')) q.put((2, 'Priority 2')) # Access elements in the priority queue print(q.get()) # Remove and return the element with the highest priority print(q.get()) print(q.get()) # Check if the priority queue is empty print(q.empty()) # Returns True if the queue is empty, False otherwise

#Output: (1, 'Priority 1') (2, 'Priority 2') (3, 'Priority 3') True

Above program create a PriorityQueue q and add some elements to it using the put() method. Each element added to the queue is a tuple, where the first element is the priority (an integer), and the second element is the value. You can access elements in the priority queue using the get() method, which will remove and return the element with the highest priority. If two elements have the same priority, they will be returned in the order in which they were added to the queue. You can check if the priority queue is empty using the empty() method, which returns True if the queue is empty and False otherwise.

deque:

The deque module is a double-ended queue that allows you to add and remove items from both ends. This can be useful for implementing certain data structures such as a stack or a queue.

from collections import deque # Create an empty deque d = deque() # Add elements to the deque d.append(1) # Add an element to the right end d.appendleft(2) # Add an element to the left end d.extend([3, 4]) # Add multiple elements to the right end d.extendleft([5, 6]) # Add multiple elements to the left end # Access elements in the deque print(d[0]) # Access the element at index 0 print(d[-1]) # Access the element at index -1 (i.e., the last element) # Remove elements from the deque d.pop() # Remove and return the rightmost element d.popleft() # Remove and return the leftmost element

#Output: 6 4

Above program create a deque d and add some elements to it using the append(), appendleft(), extend(), and extendleft() methods. You can access elements in the deque using indexing, and you can remove elements from the deque using the pop() and popleft() methods.

Implement a circular queue in Python

Following is an example of how to implement a circular queue in Python:

class CircularQueue: def __init__(self, capacity): self.capacity = capacity self.front = -1 self.rear = -1 self.queue = [None] * capacity def is_empty(self): return self.front == -1 def is_full(self): return (self.rear + 1) % self.capacity == self.front def enqueue(self, item): if self.is_full(): print('Queue is full') return if self.is_empty(): self.front = 0 self.rear = (self.rear + 1) % self.capacity self.queue[self.rear] = item def dequeue(self): if self.is_empty(): print('Queue is empty') return if self.front == self.rear: self.front = -1 self.rear = -1 else: self.front = (self.front + 1) % self.capacity def peek(self): if self.is_empty(): print('Queue is empty') return return self.queue[self.front] def display(self): if self.is_empty(): print('Queue is empty') return items = [] i = self.front while i != self.rear: items.append(self.queue[i]) i = (i + 1) % self.capacity items.append(self.queue[i]) print('Queue:', items) #Following is an example of how to use the CircularQueue class: # Create a circular queue with capacity 3 q = CircularQueue(3) # Add some items to the queue q.enqueue('red') q.enqueue('green') q.enqueue('blue') # Display the queue q.display() # Output: Queue: ['red', 'green', 'blue'] # Remove an item from the queue q.dequeue() # Display the queue again q.display() # Output: Queue: ['green', 'blue'] # Add another item to the queue q.enqueue('yellow') # Display the queue again q.display() # Output: Queue: ['green', 'blue', 'yellow'] # Try to add another item to the queue (should print "Queue is full") q.enqueue('brown')

#Output: Queue: ['red', 'green', 'blue'] Queue: ['green', 'blue'] Queue: ['green', 'blue', 'yellow'] Queue is full

In the above example, define a CircularQueue class that takes a capacity parameter in its constructor. The class has several methods to perform various operations on the queue:

is_empty returns a boolean value indicating if the queue is empty or not.
is_full returns a boolean value indicating if the queue is full or not.
enqueue adds an item to the rear of the queue.
dequeue removes an item from the front of the queue.
peek returns the item at the front of the queue without removing it.
display prints the items in the queue from front to rear.

The enqueue and dequeue methods use modulo arithmetic to implement the circular behavior of the queue. The display method iterates over the items in the queue from front to rear using the modulo operator to wrap around the end of the queue if necessary.

Sort a queue in Python

To sort a queue in Python, you can follow these steps:

Convert the queue to a list using a loop that removes each element from the queue and appends it to the list.
Sort the list using Python's built-in sorted function.
Create a new queue and add the sorted elements from the list back to the queue.

Following is an example implementation:

import queue # Create a queue with some unsorted elements q = queue.Queue() q.put(5) q.put(1) q.put(3) q.put(2) q.put(4) # Convert the queue to a list elements = [] while not q.empty(): elements.append(q.get()) # Sort the list sorted_elements = sorted(elements) # Add the sorted elements back to a new queue sorted_q = queue.Queue() for elem in sorted_elements: sorted_q.put(elem) # Print the sorted queue while not sorted_q.empty(): print(sorted_q.get())

#Output: 1 2 3 4 5

Note that this implementation assumes that the elements in the queue are comparable and can be sorted using Python's default comparison operator. If the elements have a more complex structure, you may need to provide a custom comparison function to the sorted function.

Iterate over a queue in Python

You can iterate over a queue in Python using a loop that continues while the queue is not empty.

import queue # Create a queue with some elements q = queue.Queue() q.put(1) q.put(2) q.put(3) q.put(4) q.put(5) # Iterate over the queue while not q.empty(): print(q.get())

#Output: 1 2 3 4 5

In the above example, first create a queue with some elements using the Queue class from the queue module. Then use a loop that continues while the queue is not empty. Inside the loop, remove an element from the queue using the get method and print it to the console.

Note that removing elements from the queue using the get method empties the queue. If you need to iterate over the queue without removing its elements, you can use a loop that copies the elements to a list first:

import queue # Create a queue with some elements q = queue.Queue() q.put(1) q.put(2) q.put(3) q.put(4) q.put(5) # Copy the queue elements to a list elements = list(q.queue) # Iterate over the list of elements for elem in elements: print(elem)

#Output: 1 2 3 4 5

In the above example, first create a queue with some elements using the Queue class from the queue module. Then copy the queue elements to a list using the queue attribute of the queue object. Finally, use a loop to iterate over the list of elements and print each element to the console.

Conclusion

A queue is a linear data structure that adheres to the First-In-First-Out (FIFO) principle. It enables elements to be added at the rear and removed from the front, making it useful for tasks such as managing task scheduling, implementing breadth-first search, and handling asynchronous data processing.

Next > Deque in Python

Related Topics

More Related Topics.....