Queue Implementation using Linked List 🎯

Welcome to the exciting world of Data Structures and Algorithms! Today, we're going to dive deep into understanding Queue Implementation using Linked List. By the end of this lesson, you'll be able to create your own queue using a linked list, and you'll understand why this is a practical and powerful approach for handling real-world problems.

What is a Queue? 📝

A queue is a linear data structure that follows a specific order: First-In-First-Out (FIFO). This means that the first element to enter the queue is the first one to leave it. Queues are useful in various scenarios like managing waiting lines, printing documents, and more.

Why Linked List? 💡

A linked list is a collection of data elements, called nodes, which contain a data field and a reference (link) to the next node in the sequence. Linked lists are dynamic and flexible, making them ideal for implementing queues.

Creating a Queue Node 🎯

Let's start by creating a Node class that will represent a queue element:

python

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

In this code, we define a Node class with an __init__ method that accepts a data parameter and initializes a next attribute as None. This next attribute points to the next node in the sequence.

Implementing the Queue 🎯

Now, we'll create our Queue class and implement enqueue, dequeue, and is_empty methods:

python

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = self.tail.next

    def dequeue(self):
        if not self.head:
            return None
        result = self.head.data
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return result

    def is_empty(self):
        return not self.head

In this code, we define a Queue class with an __init__ method that initializes head and tail as None. We also implement the enqueue, dequeue, and is_empty methods to manipulate the queue.

Practical Examples 🎯

Now that we've created our queue, let's see it in action:

python

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
queue.enqueue(4)
print(queue.dequeue())  # Output: 2
print(queue.dequeue())  # Output: 3
print(queue.dequeue())  # Output: 4
print(queue.is_empty())  # Output: True

In this example, we create a queue, enqueue some numbers, and then dequeue them one by one.

Quiz Time 🎯

Now, let's test your understanding with a small quiz:

That's it for today! You now have a good understanding of how to implement a queue using a linked list. In the next lessons, we'll delve deeper into data structures and algorithms, and you'll continue to upskill and enhance your programming abilities. Happy coding! 🎉