Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

We have chosen to implement the cinema queue as a singly linked list of nodes. Note: this is not an indication of whether singly linked

We have chosen to implement the cinema queue as a singly linked list of nodes. Note: this is not an indication of whether singly linked lists were the correct or incorrect solution to part (a).

A node includes a customer and their priority value. You can see our (partial) implementation here:

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 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 value """ pass 

Remember that the application implements an unbounded min-priority queue. The highest priority has priority value 1 and the lowest priority has priority value 4.

Sketch an algorithm (not Python code) to implement the insert function.

You need to consider the following cases:

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

Write your answer here

(c) (10 marks)

Edit the insert function in the code below to convert your algorithm into Python code. You must observe the coding style guidance in Chapter 5.3 and Chapter 10.3.

In [ ]:

 
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*
                        

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Records And Database Management

Authors: Jeffrey R Stewart Ed D, Judith S Greene, Judith A Hickey

4th Edition

0070614741, 9780070614741

Students also viewed these Databases questions