Circular Queue Linked List

 

Circular Queue using Linked List: A circular queue is a data structure that follows the FIFO (First-In-First-Out) principle, where the elements are inserted at the rear and removed from the front. In a circular queue, the last element points back to the first element, creating a circular structure.

To implement a circular queue using a linked list, we can use a singly linked list where each node holds the element and a reference to the next node. The last node of the linked list will point back to the first node, forming a circular structure.

The circular queue using a linked list can have the following methods:

  • __init__(self, k): Initializes an empty circular queue with a maximum size of k.
  • enqueue(self, value): Inserts an element into the circular queue if it is not full.
  • dequeue(self): Deletes an element from the circular queue if it is not empty.
  • get_front(self): Gets the front element of the circular queue if it is not empty.
  • get_rear(self): Gets the last element of the circular queue if it is not empty.
  • is_empty(self): Checks if the circular queue is empty.
  • is_full(self): Checks if the circular queue is full.

Now, let's provide a complete code implementation of the circular queue using a linked list with proper comments and explain its time and space complexity. We'll also solve a question from LeetCode that involves using a circular queue.


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

class MyCircularQueue:
    def __init__(self, k: int):
        self.head = None
        self.tail = None
        self.size = 0
        self.max_size = k

    def enqueue(self, value: int) -> bool:
        if self.is_full():
            return False

        new_node = ListNode(value)

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

        self.size += 1
        return True

    def dequeue(self) -> bool:
        if self.is_empty():
            return False

        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next

        self.size -= 1
        return True

    def get_front(self) -> int:
        if self.is_empty():
            return -1

        return self.head.value

    def get_rear(self) -> int:
        if self.is_empty():
            return -1

        return self.tail.value

    def is_empty(self) -> bool:
        return self.size == 0

    def is_full(self) -> bool:
        return self.size == self.max_size

# Example usage:
cq = MyCircularQueue(3)
print(cq.enqueue(1))  # Output: True
print(cq.enqueue(2))  # Output: True
print(cq.enqueue(3))  # Output: True
print(cq.enqueue(4))  # Output: False (queue is full)

print(cq.get_front())  # Output: 1
print(cq.get_rear())  # Output: 3

print(cq.is_empty())  # Output: False
print(cq.is_full())  # Output: True

print(cq.dequeue())  # Output: True
print(cq.get_front())  # Output: 2

In this implementation, we have a ListNode class representing a node in the linked list. The MyCircularQueue class has various methods:

  • __init__: Initializes an empty circular queue with a maximum size of k.
  • enqueue: Inserts an element into the circular queue if it is not full.
  • dequeue: Deletes an element from the circular queue if it is not empty.
  • get_front: Gets the front element of the circular queue if it is not empty.
  • get_rear: Gets the last element of the circular queue if it is not empty.
  • is_empty: Checks if the circular queue is empty.
  • is_full: Checks if the circular queue is full.

Time and Space Complexity Analysis:

  • Enqueue, Dequeue, GetFront, IsEmpty, and IsFull methods all have a time complexity of O(1) since they involve constant-time operations like assigning values, updating references, and checking conditions.
  • The space complexity of the circular queue is O(k), where k is the maximum size of the circular queue. We store k elements in the linked list.

Let's solve a question from LeetCode that uses the circular queue implementation.

Question: "Design Circular Deque" Problem Description: Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

  • MyCircularDeque(k): Initializes the deque with a maximum size of k.
  • insertFront(): Adds an item at the front of the deque if it is not full.
  • insertLast(): Adds an item at the rear of the deque if it is not full.
  • deleteFront(): Deletes an item from the front of the deque if it is not empty.
  • deleteLast(): Deletes an item from the rear of the deque if it is not empty.
  • getFront(): Returns the front item from the deque if it is not empty.
  • getRear(): Returns the last item from the deque if it is not empty.
  • isEmpty(): Checks whether the circular deque is empty or not.
  • isFull(): Checks whether the circular deque is full or not.

Example:


# Create a MyCircularDeque object with maximum size 3
circularDeque = MyCircularDeque(3)

# Insert new elements at the front and rear
print(circularDeque.insertLast(1))  # Output: True
print(circularDeque.insertLast(2))  # Output: True
print(circularDeque.insertFront(3))  # Output: True
print(circularDeque.insertFront(4))  # Output: False (deque is full)

# Get the front and rear elements
print(circularDeque.getFront())  # Output: 3
print(circularDeque.getRear())  # Output: 2

# Delete elements from the front and rear
print(circularDeque.deleteFront())  # Output: True
print(circularDeque.deleteLast())  # Output: True

# Check if the deque is empty or full
print(circularDeque.isEmpty())  # Output: False
print(circularDeque.isFull())  # Output: False

In this example, we use the MyCircularDeque class to create a circular double-ended queue with a maximum size of 3. We insert elements at the front and rear, get the front and rear elements, delete elements from the front and rear, and check if the deque is empty or full.

The time and space complexity for each method in the MyCircularDeque class remains the same as explained earlier.

 

 

Next Post Previous Post