This program demonstrates the implementation of a queue data structure using a linked list. Queues are a type of data structure with First In First Out (FIFO) access policy. The operations demonstrated in this queue are:

• Enqueue: Add an item to the end of the queue.
• Dequeue: Remove the item from the front of the queue.
• Peek: Get the item at the front of the queue without removing it.
• is_empty: Check if the queue is empty.

Code Explanation

The queue functionality is encapsulated within a class Queue. This class uses an inner class Node, which represents an element in the queue. Here’s a detailed breakdown of the methods within the Queue class:

1. Node class: A simple class for storing data and the link to the next node.
2. __init__: Initializes the queue.
3. enqueue: Adds a new element to the end of the queue.
4. dequeue: Removes the element from the front of the queue and returns it.
5. peek: Returns the front element without removing it.
6. is_empty: Returns True if the queue is empty, otherwise False.

Python Code

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

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

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

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        current_head = self.head
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return current_head.value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self.head.value

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

Usage

To use this queue, instantiate an object of the Queue class and use the enqueue, dequeue, and peek methods to manipulate it.