Queue

Queue is a linear data structure that follows the First In First Out (FIFO) principle. It has two ends, front and rear. The elements are added from the rear end and removed from the front end. The first element to be added to the queue will be the first one to be removed. This is why it is called First In First Out (FIFO).

0	1	2	3	4	5	6	7	8	9
Head	_	_	_	_	_	_	_	_	Tail

The above diagram shows a queue with 10 elements. The head of the queue is at index 0 and the tail is at index 9. The head is the first element to be removed and the tail is the last element to be removed. The queue is empty when the head and tail are at the same index.

Enqueue

Enqueue is the process of adding an element to the queue. The element is added to the rear end of the queue

0	1	2	3	4	5	6	7	8	9	10
Head	_	_	_	_	_	_	_	_	_	New, Tail

Dequeue

Dequeuing is the process of removing an element from the queue. The element is removed from the front end of the queue.

0	1	2	3	4	5	6	7	8	9
New Head	_	_	_	_	_	_	_	_	Tail

Peek

Peek is the process of viewing the element at the front end of the queue without removing it.

LinkedList with Tail Pointer

graph LR
    Head --> A[Node]
    A --> B[Node]
    B --> C[Node]
    C --> D[Node]
    Tail --> D

Enqueue operation is O(1) because we have reference to the tail node. Dequeue operation is O(1) because we have reference to the head node.

However, there are some disadvantages of using a linked list:

Extra memory: Each node in the list requires extra space for the next pointer
Not cache friendly: Since the nodes are not stored in contiguous memory locations, the cache is not utilized efficiently

In practice, Queue is often implemented using: - Linkedlist of blocks of fixed size: each block is a fixed size array, when the array is full, a new block is allocated and linked to the previous block - Circular buffer array

# create circular array

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1
    
    def enqueue(self, data):
        if (self.rear + 1) % self.size == self.front:
            print("Queue is full")
        elif self.front == -1:
            self.front = 0
            self.rear = 0
            self.queue[self.rear] = data
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = data
    
    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
        elif self.front == self.rear:
            temp = self.queue[self.front]
            self.front = -1
            self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size
            return temp
    
    def display(self):
        if self.front == -1:
            print("Queue is empty")
        elif self.rear >= self.front:
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.front, self.size):
                print(self.queue[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
    
    def getFront(self):
        if self.front == -1:
            print("Queue is empty")
        else:
            print("Front element is", self.queue[self.front])
    
    def getRear(self):
        if self.rear == -1:
            print("Queue is empty")
        else:
            print("Rear element is", self.queue[self.rear])

q = CircularQueue(5)
q.enqueue(14)
q.enqueue(22)
print(q.dequeue())
print(q.dequeue())

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.display()

q.enqueue(5)
q.enqueue(6) # queue is full

14
22
1 2 3 4 
Queue is full

Complexity

Operation	Complexity
Enqueue	O(1)
Dequeue	O(1)
Peek	O(1)

Use Cases

Queue is used in many scalable systems. For example, a web server can use a queue to store the requests from clients. The requests are processed in the order they are received.

If you have ever heard about Redis, Kafka, RabbitMQ, Pubsuq, etc, they are all have queue as their data structure.

This describe various queue patterns

Work Queue

Source: RabbitMQ

email = {
    "id": 1,
    "title": "Welcome to our newsletter",
    "body": "Hello, welcome to our newsletter",
}

from queue import Queue
q = Queue()

q.put(email)

# Publisher to email provider A running in a separate thread/process
email = q.get()
EmailProviderA.send(email)

# Publisher to email provider B running in a separate thread/process
email = q.get()
EmailProviderB.send(email)

Pubsub

Source: RabbitMQ

campaign = {
    "id": 1,
    "title": "Welcome to our newsletter",
    "body": "Hello, welcome to our newsletter",
}

from queue import Queue
push_notification_queue = Queue()
email_queue = Queue()

push_notification_queue.put(campaign)
email_queue.put(campaign)

Buffer

Queue could also be used as a buffer. For example, a producer produces data at a faster rate than the consumer can consume. The producer can store the data in a queue and the consumer can consume the data at its own pace.

from queue import Queue
messages = [{
    "id": 1,
    "title": "Welcome to our newsletter",
    "body": "Hello, welcome to our newsletter",
}, {
    "id": 2,
    "title": "Welcome to our newsletter",
    "body": "Hello, welcome to our newsletter",
}]

q = Queue()
# publisher with high throughput
for message in messages:
    q.put(message)

# Consumer with low throughput
while True:
    message = q.get()
    EmailProvider.send(message) # assume synchronous call

Batch Insert

Queue can be used to batch insert data into a database. The data is first stored in a queue and then inserted into the database in batches.

Batch insert is generally faster than inserting one record at a time. This is because the database can perform the insert operation in bulk.

High Level Library

In Python, we can use:

Queue from queue module -> Thread safe
deque from collections module -> Not thread safe, but faster