Home > Blockchain >  Implementing an Unbounded Min Priority Queue using a Singly Linked List in Python
Implementing an Unbounded Min Priority Queue using a Singly Linked List in Python

Time:12-13

I am doing a class project and I have to implement an unbounded singly linked list using python. I need to implement a given 'insert' that has to consider the following cases...

insert into an empty queue insert at the front of the queue insert after some existing node.

This is the class given in python and i need to implement the insert function given at the bottom. I am new to this so any help would be greatly appreciated!

class CinemaPriorityQueue:
    """A linked list implementation of an unbounded min-priority queue."""

    class Node:
        """A node in a linked list."""

        def __init__(self, item: object, priority_value: int) -> None:
            """Initialise the node with the given item and priority value."""
            self.item = item
            self.priority = priority_value
            self.next = None

    def __init__(self) -> None:
        """Initialise the queue to be empty."""
        self.head = None

    def is_empty(self) -> bool:
        """
        Preconditions: true
        Postconditions: the output is true if the queue is empty, false otherwise
        """
        return self.head == None

    def print(self) -> None:
        """Print out the queue"""
        if self.head == None:
            print('The queue is empty')
        else:
            current = self.head
            while current != None:
                print(current.item, current.priority)
                current = current.next



    def insert(self, item: object, priority_value: int) -> None:
        """Insert item according to priority.
        Preconditions: true
        Postconditions: post-self is the sequence
        pre-self with item inserted after
        the last item in self with the same priority
        """
        pass
        #*Write your code solution here*

CodePudding user response:

I can tell you the idea behind the solution. In the singly linked list, while adding a new element, compare it with the elements in the linked list and add it where it fits so that the linked list is sorted. This will give you a min priority queue.

CodePudding user response:

Dude, you can literally copy that from the handbook, start learning and don't use people good will. Page 228. Next time seriously start learning sooner than 2 days before cutoff

  • Related