Data Structure: Queues

Prerequisites:

• Basic knowledge of Python

A data structure is a way to organize and store data. A queue is a linear data structure that handles data sequentially. It uses a first-in-first-out (FIFO) approach, meaning elements are processed and removed in the order they were added. A real-life example of a Queue is the line or queue in a banking hall, where the person in front of the cashier is served before others.

The process of removing an element in a queue is called dequeue while adding a new element is called enqueue. Insertion occurs in the rear while deletion is from the front.

Queues are practically used in a variety of domains and scenarios, for example, the instruction set of an operating system and e-commerce. Let's explore these examples:

1. Operating Systems: Queues play a crucial role in managing and scheduling tasks in operating systems. Tasks or instructions can be organized in queues based on priority or other scheduling algorithms. Then the operating system executes these tasks in the order they were inserted.

2. E-commerce: During peak periods, like sales or promotional events, simultaneous requests can overwhelm the system. To address this, a queue manages incoming requests, processing them in the order of arrival. By placing requests in a queue, the system avoids overload and ensures all requests are eventually handled. While customers may experience a short wait in the queue, it helps maintain system stability and reliability during high-traffic periods.

Here is a simple implementation of a queue:

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

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    def getFirstElement(self):
        return self.queue[0]

    def size(self):
        return len(self.queue)

However, this implementation can be inefficient in certain cases. For instance, when we want to handle a certain number of requests at a time due to multiple requests.

Enter the circular queue.

By employing a circular queue, it is possible to achieve simultaneous processing of limited requests during periods of high traffic. This allows for improved performance and throughput.

A circular queue utilizes a fixed-sized array, two pointers to indicate the start and end positions, and the last position is connected back to the first position to make a circle.

Here is an implementation of a circular queue:

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [None] * k
        self.start = -1
        self.rear = -1
        self.maxSize = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty():
            self.start = 0
        self.rear = (self.rear + 1) % self.maxSize
        self.queue[self.rear] = value
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        if self.start == self.rear:
            self.start = -1
            self.rear = -1
            return True
        else:
            self.start = (self.start + 1) % self.maxSize
            return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.start]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.rear]

    def isEmpty(self) -> bool:
        return self.rear == -1

    def isFull(self) -> bool:
        return (self.rear + 1) % self.maxSize == self.start

In conclusion, queues are essential data structures for managing and processing data sequentially. They find practical applications in various domains, including e-commerce and operating systems. By utilizing queues, e-commerce platforms can efficiently manage order processing, handle high traffic situations, and ensure a smooth customer experience.