What is a Queue?

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are commonly used in scenarios where order needs to be preserved, such as in scheduling tasks, managing requests in web servers, and handling asynchronous data.

Key Characteristics of Queues:

FIFO Order: The first element added is the first one to be removed.
Two Main Operations:
- Enqueue: Adding an element to the end of the queue.
- Dequeue: Removing an element from the front of the queue.
Front and Rear: The front is the first element in the queue, and the rear is the last element.

Real-World Examples of Queues

Customer Service: Customers are served in the order they arrive.
Print Queue: Documents are printed in the order they are sent to the printer.
Task Scheduling: Tasks are executed in the order they are scheduled.

Basic Operations on Queues

Enqueue Operation

The enqueue operation adds an element to the end of the queue.

Dequeue Operation

The dequeue operation removes an element from the front of the queue.

Peek Operation

The peek operation returns the element at the front of the queue without removing it.

IsEmpty Operation

The isEmpty operation checks if the queue is empty.

IsFull Operation

The isFull operation checks if the queue is full (in the case of a bounded queue).

Queue Implementation

Queues can be implemented using arrays or linked lists. Below, we will explore both implementations.

Array-Based Implementation

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

    def isFull(self):
        return self.size == self.capacity

    def isEmpty(self):
        return self.size == 0

    def enqueue(self, item):
        if self.isFull():
            print("Queue is full")
            return
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1
        print(f"Enqueued {item}")

    def dequeue(self):
        if self.isEmpty():
            print("Queue is empty")
            return
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        print(f"Dequeued {item}")
        return item

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

# Example usage
q = Queue(5)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.dequeue()
print(f"Front item is {q.peek()}")

Linked List-Based Implementation

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

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

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

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear is None:
            self.front = self.rear = new_node
            print(f"Enqueued {item}")
            return
        self.rear.next = new_node
        self.rear = new_node
        print(f"Enqueued {item}")

    def dequeue(self):
        if self.isEmpty():
            print("Queue is empty")
            return
        temp = self.front
        self.front = temp.next
        if self.front is None:
            self.rear = None
        print(f"Dequeued {temp.data}")
        return temp.data

    def peek(self):
        if self.isEmpty():
            print("Queue is empty")
            return
        return self.front.data

# Example usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.dequeue()
print(f"Front item is {q.peek()}")

Summary

In this section, we introduced the concept of queues, a fundamental data structure that operates on the FIFO principle. We discussed the key characteristics and real-world examples of queues, and we explored the basic operations such as enqueue, dequeue, peek, isEmpty, and isFull. Additionally, we provided implementations of queues using both arrays and linked lists.

In the next section, we will delve into the basic operations with queues, providing more detailed explanations and examples.

Introduction to Queues

What is a Queue?

Key Characteristics of Queues:

Real-World Examples of Queues

Basic Operations on Queues

Enqueue Operation

Dequeue Operation

Peek Operation

IsEmpty Operation

IsFull Operation

Queue Implementation

Array-Based Implementation

Linked List-Based Implementation

Summary

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources