Queue in Python – Analytics Vidhya

Introduction

Think about you might be standing in entrance of a grocery store ready in your flip to purchase live performance tickets of your favorite artist. All go to the road formation and transfer from the road on the entrance of it. Laptop scientists name this orderliness a queue, which follows the First In, First Out (FIFO) coverage. Programmers discover queues as helpful as different Python information constructions and use them to handle duties, course of asynchronous information, and carry out many different capabilities. On this article we’ll focuses on utilizing queues in Python, the overall overview of the queues, and the significance of queues.

Studying Outcomes

• Perceive what a queue is and its significance in programming.
• Be taught alternative ways to implement queues in Python.
• ExploExplore numerous operations you’ll be able to carry out on queues.
• Uncover sensible functions of queues.
• Achieve insights into superior queue sorts and their use instances.

What’s a Queue?

A queue is a linear information construction that follows the First In First Out (FIFO) precept. It operates by inserting information on the rear finish and deleting information from the entrance finish. This course of ensures that the queue removes the primary inserted factor first, adhering to the FIFO precept.

Operations on Queues

Listed here are the operations which are sometimes related to a queue.

• Enqueue: This operation provides an merchandise to the tip of the queue. If the queue is full, it ends in an overflow situation. The time complexity for this operation is (O(1)).
• Dequeue: This operation removes an merchandise from the entrance of the queue. Objects observe the FIFO precept and are eliminated in the identical order they had been added. If the queue is empty, it ends in an underflow situation. The time complexity for this operation is (O(1)).
• Peek or Entrance: This operation retrieves the merchandise on the entrance of the queue with out eradicating it. The time complexity for this operation is (O(1)).
• Rear or Again: This operation retrieves the merchandise on the finish of the queue. The time complexity for this operation is (O(1)).
• IsEmpty: Checking if the queue is empty. Time complexity: O(1) – Fixed time operation.
• IsFull: Checking if the queue is full (if applied with a hard and fast dimension). Time complexity: O(1) – Fixed time operation.
• Measurement: Returns the variety of components within the queue. Time complexity: O(1) – Fixed time operation in most implementations.

Implementing Queues in Python

There are a number of methods to implement queues in Python:

Utilizing Lists

Python lists can be utilized to implement a queue. Nonetheless, utilizing lists for queues is just not environment friendly for giant datasets as a result of eradicating components from the entrance of a listing is an O(n) operation.

class ListQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, merchandise):
        self.queue.append(merchandise)
        print(f"Enqueued: {merchandise}")

    def dequeue(self):
        if self.is_empty():
            elevate IndexError("Dequeue from an empty queue")
        merchandise = self.queue.pop(0)
        print(f"Dequeued: {merchandise}")
        return merchandise

    def peek(self):
        if self.is_empty():
            elevate IndexError("Peek from an empty queue")
        print(f"Peek: {self.queue[0]}")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def dimension(self):
        print(f"Measurement: {len(self.queue)}")
        return len(self.queue)

    def clear(self):
        self.queue = []
        print("Queue cleared")

# Instance utilization
lq = ListQueue()
lq.enqueue(1)
lq.enqueue(2)
lq.peek()
lq.dequeue()
lq.dimension()
lq.clear()

Output:

Enqueued: 1
Enqueued: 2
Peek: 1
Dequeued: 1
Measurement: 1
Queue cleared

Utilizing collections.deque

The collections.deque class from the collections module supplies a extra environment friendly solution to implement a queue because it permits O(1) operations for appending and popping components from each ends.

from collections import deque

class DequeQueue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, merchandise):
        self.queue.append(merchandise)
        print(f"Enqueued: {merchandise}")

    def dequeue(self):
        if self.is_empty():
            elevate IndexError("Dequeue from an empty queue")
        merchandise = self.queue.popleft()
        print(f"Dequeued: {merchandise}")
        return merchandise

    def peek(self):
        if self.is_empty():
            elevate IndexError("Peek from an empty queue")
        print(f"Peek: {self.queue[0]}")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def dimension(self):
        print(f"Measurement: {len(self.queue)}")
        return len(self.queue)

    def clear(self):
        self.queue.clear()
        print("Queue cleared")

# Instance utilization
dq = DequeQueue()
dq.enqueue(1)
dq.enqueue(2)
dq.peek()
dq.dequeue()
dq.dimension()
dq.clear()

Output:

Enqueued: 1
Enqueued: 2
Peek: 1
Dequeued: 1
Measurement: 1
Queue cleared

Utilizing queue.Queue

The queue.Queue class from the queue module is designed particularly for multi-threaded programming. It supplies thread-safe queues and numerous synchronization primitives.

from queue import Queue, Empty

class ThreadSafeQueue:
    def __init__(self, maxsize=0):
        self.queue = Queue(maxsize=maxsize)

    def enqueue(self, merchandise):
        self.queue.put(merchandise)
        print(f"Enqueued: {merchandise}")

    def dequeue(self):
        strive:
            merchandise = self.queue.get(timeout=1)  # Look forward to as much as 1 second for an merchandise
            print(f"Dequeued: {merchandise}")
            return merchandise
        besides Empty:
            elevate IndexError("Dequeue from an empty queue")

    def peek(self):
        with self.queue.mutex:
            if self.queue.empty():
                elevate IndexError("Peek from an empty queue")
            print(f"Peek: {self.queue.queue[0]}")
            return self.queue.queue[0]

    def is_empty(self):
        return self.queue.empty()

    def dimension(self):
        print(f"Measurement: {self.queue.qsize()}")
        return self.queue.qsize()

    def clear(self):
        with self.queue.mutex:
            self.queue.queue.clear()
            print("Queue cleared")

# Instance utilization
tsq = ThreadSafeQueue()
tsq.enqueue(1)
tsq.enqueue(2)
tsq.peek()
tsq.dequeue()
tsq.dimension()
tsq.clear()

Output:

Enqueued: 1
Enqueued: 2
Peek: 1
Dequeued: 1
Measurement: 1
Queue cleared

Purposes of Queues

Queues are extensively utilized in numerous functions, together with:

• Process Scheduling: Laptop scientists suggest the queue as one of many primary summary information sorts, which many functions use to order components in keeping with a selected criterion.
• Breadth-First Search: One other traversal algorithm is the BFS algorithm which employs a queue information construction to traverse nodes in a graph stage by stage.
• Dealing with Asynchronous Information: It is because net servers deal with information move through the use of queues, processing requests within the order they obtain them.
• Buffering: Queues are simply as IO Buffers that relate information Interchange transactions as a solution to management information move between information producers and information shoppers.
• Print Spooling: Scheduling of print jobs in printers who accomplish print requests on a first-come, first-served foundation.
• Order Processing: Prospects orders’ administration within the context of each bodily and on-line shops.
• Useful resource Allocation: Handle shared assets like printers or CPU time (e.g., allocate assets primarily based on queue place).
• Batch Processing: Deal with jobs in batches, processing them sequentially (e.g., picture processing, information evaluation).
• Networking: Handle community site visitors, routing information packets (e.g., routers use queues to buffer incoming packets).
• Working Methods: Handle interrupts, deal with system calls, and implement course of scheduling.
• Simulations: Mannequin real-world programs with ready traces (e.g., financial institution queues, site visitors lights).

Superior Queue Varieties

Allow us to now look into the superior queue sorts under:

Precedence Queue

A precedence queue assigns a precedence to every factor. Components with increased precedence are dequeued earlier than these with decrease precedence.

from queue import PriorityQueue

pq = PriorityQueue()

# Enqueue
pq.put((1, 'job 1'))  # (precedence, worth)
pq.put((3, 'job 3'))
pq.put((2, 'job 2'))

# Dequeue
print(pq.get())  # Output: (1, 'job 1')
print(pq.get())  # Output: (2, 'job 2')

Double-Ended Queue (Deque)

A deque permits components to be added or faraway from each ends, making it extra versatile.

from collections import deque

deque = deque()

# Enqueue
deque.append(1)        # Add to rear
deque.appendleft(2)    # Add to entrance

# Dequeue
print(deque.pop())     # Take away from rear, Output: 1
print(deque.popleft()) # Take away from entrance, Output: 2

Round Queue

Effectively makes use of array area by wrapping round to the start when the tip is reached.

class CircularQueue:
    def __init__(self, capability):
        self.queue = [None] * capability
        self.entrance = self.rear = -1
        self.capability = capability

    def is_empty(self):
        return self.entrance == -1

    def is_full(self):
        return (self.rear + 1) % self.capability == self.entrance

    def enqueue(self, merchandise):
        if self.is_full():
            print("Queue Overflow")
            return
        if self.entrance == -1:
            self.entrance = 0
        self.rear = (self.rear + 1) % self.capability
        self.queue[self.rear] = merchandise

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow")
            return
        merchandise = self.queue[self.front]
        if self.entrance == self.rear:
            self.entrance = self.rear = -1
        else:
            self.entrance = (self.entrance + 1) % self.capability
        return merchandise

    def peek(self):
        if self.is_empty():
            print("Queue is empty")
            return
        return self.queue[self.front]

    def dimension(self):
        if self.is_empty():
            return 0
        return (self.rear + 1 - self.entrance) % self.capability

# Instance utilization
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue())  # Output: 1
print(cq.peek())  # Output: 2

Blocking Queue

It synchronizes entry between threads. It blocks when the queue is full or empty till area is offered.

import queue

class BlockingQueue:
    def __init__(self, maxsize):
        self.queue = queue.Queue(maxsize)

    def put(self, merchandise):
        self.queue.put(merchandise)

    def get(self):
        return self.queue.get()

    def empty(self):
        return self.queue.empty()

    def full(self):
        return self.queue.full()

# Instance utilization
bq = BlockingQueue(5)
import threading

def producer():
    for i in vary(10):
        bq.put(i)

def client():
    whereas True:
        merchandise = bq.get()
        print(merchandise)
        bq.task_done()

producer_thread = threading.Thread(goal=producer)
consumer_thread = threading.Thread(goal=client)
producer_thread.begin()
consumer_thread.begin()

Benefits of Queues

• Order Upkeep: Queues keep the order of components, which is important for job scheduling and processing sequences.
• Concurrency Dealing with: Queues effectively handle concurrent information processing, particularly in multi-threaded functions.
• Simplicity and Flexibility: You may implement queues simply and adapt them for numerous functions, from easy job administration to advanced information processing pipelines.

Conclusion

Laptop scientists suggest the queue as one of many primary summary information sorts, which many functions use to order components in keeping with a selected criterion. Queues are of various sorts in python however under are the very best and generally used strategies to implement them. Studying the correct utilization of queues in addition to mastering their utility can play an in depth function in sprucing one’s programming abilities and make it doable to deal with quite a few points.

Continuously Requested Questions