DSA Queues

Welcome to TheCodingCollege.com! In this post, we’ll explore queues, a fundamental data structure in Data Structures and Algorithms (DSA). Queues are simple yet powerful tools used in numerous real-world applications and algorithms.

What is a Queue?

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. This means the first element added to the queue is the first to be removed, similar to a line of people waiting at a counter.

Key Operations of a Queue

  1. Enqueue: Add an element to the rear of the queue.
  2. Dequeue: Remove an element from the front of the queue.
  3. Front (Peek): Retrieve the front element without removing it.
  4. IsEmpty: Check if the queue is empty.
  5. IsFull: (For fixed-size queues) Check if the queue is full.

Applications of Queues

Queues are used in a variety of scenarios, such as:

  • CPU scheduling and disk scheduling.
  • Breadth-First Search (BFS) in graphs.
  • Data buffering (e.g., in printers, IO operations).
  • Handling requests in web servers.
  • Simulating real-world queues (e.g., supermarket checkout).

Types of Queues

  1. Simple Queue: Operates on FIFO; elements are enqueued at the rear and dequeued from the front.
  2. Circular Queue: A queue that connects the rear to the front to use storage efficiently.
  3. Priority Queue: Elements are dequeued based on priority rather than the order of insertion.
  4. Double-Ended Queue (Deque): Allows insertion and deletion from both ends.

Implementation of Queues

Queues can be implemented using:

  1. Arrays
  2. Linked Lists

1. Queue Implementation Using Arrays

class Queue:
    def __init__(self, size):
        self.queue = [None] * size
        self.size = size
        self.front = 0
        self.rear = -1
        self.count = 0

    def enqueue(self, data):
        if self.is_full():
            print("Queue Overflow!")
            return
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = data
        self.count += 1

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow!")
            return
        data = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return data

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

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.size

# Example Usage
q = Queue(5)
q.enqueue(10)
q.enqueue(20)
print(q.peek())  # Output: 10
q.dequeue()
print(q.peek())  # Output: 20

2. Queue Implementation Using Linked Lists

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow!")
            return
        data = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return data

    def peek(self):
        if not self.is_empty():
            return self.front.data
        print("Queue is Empty!")

    def is_empty(self):
        return self.front is None

# Example Usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.peek())  # Output: 10
q.dequeue()
print(q.peek())  # Output: 20

Advantages of Queues

  1. Efficient for sequential data processing.
  2. Simple to implement and use in various applications.
  3. Handles resource sharing effectively (e.g., CPU tasks).

Disadvantages of Queues

  1. Fixed size in array-based queues (queue overflow is possible).
  2. Circular queues require additional logic for efficient implementation.

Time Complexity of Queue Operations

OperationTime Complexity
EnqueueO(1)
DequeueO(1)
PeekO(1)
IsEmptyO(1)

Common Problems and Use Cases

1. Generate Binary Numbers Using a Queue

from queue import Queue

def generate_binary_numbers(n):
    q = Queue()
    q.put("1")
    for _ in range(n):
        num = q.get()
        print(num, end=" ")
        q.put(num + "0")
        q.put(num + "1")

# Example Usage
generate_binary_numbers(10)
# Output: 1 10 11 100 101 110 111 1000 1001 1010

2. Reverse the First K Elements of a Queue

from queue import Queue

def reverse_k_elements(q, k):
    stack = []
    for _ in range(k):
        stack.append(q.get())
    while stack:
        q.put(stack.pop())
    for _ in range(q.qsize() - k):
        q.put(q.get())
    return q

# Example Usage
q = Queue()
for i in range(1, 6):
    q.put(i)
q = reverse_k_elements(q, 3)
while not q.empty():
    print(q.get(), end=" ")  # Output: 3 2 1 4 5

Conclusion

Queues are a crucial part of data structures, offering efficient solutions for managing sequential data and tasks. Mastering queues will enhance your ability to solve problems in DSA and beyond.

For more tutorials, coding tips, and in-depth guides, visit TheCodingCollege.com and elevate your programming journey!

Leave a Comment