Linked Queue

 

Linked Queue A Linked Queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. It consists of nodes, where each node contains a value and a reference to the next node in the queue. The front of the queue is where the removal or dequeuing happens, and the rear is where the insertion or enqueueing takes place.

The operations supported by a Linked Queue are:

  • enqueue(value): Inserts an element at the rear of the queue.
  • dequeue(): Removes and returns the element at the front of the queue.
  • is_empty(): Checks if the queue is empty.
  • size(): Returns the number of elements in the queue.
  • front(): Returns the value of the element at the front of the queue without removing it.

Here's an example implementation of a Linked Queue in Python with proper comments explaining each step:


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


class LinkedQueue:
    def __init__(self):
        self.front = None  # Points to the front of the queue
        self.rear = None   # Points to the rear of the queue
        self.size = 0      # Keeps track of the number of elements in the queue

    def enqueue(self, value):
        new_node = Node(value)

        if self.is_empty():
            self.front = new_node
        else:
            self.rear.next = new_node

        self.rear = new_node
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")

        value = self.front.value
        self.front = self.front.next
        self.size -= 1

        if self.is_empty():
            self.rear = None

        return value

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

    def size(self):
        return self.size

    def front(self):
        if self.is_empty():
            raise Exception("Queue is empty")

        return self.front.value

Now, let's solve a question from LeetCode using the Linked Queue concept.

Question: Implement Stack using Queues Implement a stack using queues. The stack should support the following operations: push(), pop(), top(), and empty().


class MyStack:
    def __init__(self):
        self.queue = LinkedQueue()

    def push(self, x):
        # Enqueue the new element
        self.queue.enqueue(x)

        # Rotate the elements to bring the new element to the front
        for _ in range(self.queue.size - 1):
            self.queue.enqueue(self.queue.dequeue())

    def pop(self):
        if self.empty():
            raise Exception("Stack is empty")

        # Dequeue and return the front element
        return self.queue.dequeue()

    def top(self):
        if self.empty():
            raise Exception("Stack is empty")

        # Return the front element without dequeuing it
        return self.queue.front()

    def empty(self):
        return self.queue.is_empty()

In this solution, we use a Linked Queue to implement a Stack. The push operation is implemented by enqueuing the new element and rotating the existing elements to bring the new element to the front. The pop operation dequeues and returns the front element. The top operation returns the front element without dequeuing it. The empty operation checks if the stack is empty.

The time complexity of push, pop, top, and empty operations is O(n) in the worst case, where n is the number of elements in the stack. The worst case occurs when the new element is pushed and all existing elements are rotated. The space complexity is O(n) to store the elements in the Linked Queue.

 Let's solve the question "Binary Tree Level Order Traversal" using the Linked Queue concept.

Question: Binary Tree Level Order Traversal Given a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example:


Input: [3,9,20,null,null,15,7]
   3
  / \
 9  20
   /  \
  15   7

Output: [[3],[9,20],[15,7]]

To solve this problem, we can use a Linked Queue to perform a breadth-first traversal of the binary tree. We will enqueue each level's nodes and process them level by level.

Here's the Python code to solve the problem: 


class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right


def level_order_traversal(root):
    if not root:
        return []

    result = []
    queue = LinkedQueue()
    queue.enqueue(root)

    while not queue.is_empty():
        level = []
        level_size = queue.size

        for _ in range(level_size):
            node = queue.dequeue()
            level.append(node.val)

            if node.left:
                queue.enqueue(node.left)

            if node.right:
                queue.enqueue(node.right)

        result.append(level)

    return result


# Test the code with the given example
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(level_order_traversal(root))  # Output: [[3], [9, 20], [15, 7]]

The level_order_traversal function takes the root of a binary tree as input and performs a level order traversal using a Linked Queue. It initializes an empty result list and a queue. The root is enqueued, and then a loop iterates until the queue is empty. In each iteration, the nodes at the current level are dequeued, and their values are added to the level list. If the dequeued node has left and right children, they are enqueued. The level list is then appended to the result list. Finally, the result list containing the level order traversal is returned.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. We need to visit each node once. The space complexity is also O(n) since, in the worst case, the Linked Queue can hold all the nodes at the maximum level, which is n/2 in a complete binary tree.

 

 

 

 

Next Post Previous Post