PSEUDO CODE question. NOT Java or C, C++ a) Bill suggested that he can implement
ID: 3725690 • Letter: P
Question
PSEUDO CODE question. NOT Java or C, C++
a) Bill suggested that he can implement a queue ADT using a priority queue and a constant amount of additional space. Recall that a stack supports enqueue and dequeue operations, and a priority queue supports min(), removeMin and insert operations. Explain how Bill can achieve this by showing the necessary PSEUDO CODE for implementing the queue ADT.
b) Referring to a) above, what are the tight big-Oh time complexities of the push and pop operations of the newly designed stack given that the priority queue is implemented using a heap? Explain your answer.
Explanation / Answer
a)
Priority queue: The elements are popped or dequeued on the base of their priority. Assuming if the priority is represented as an integer, the minimum value corresponds to higher priority and vice versa.
The functions of the priority queue are as follows:
Queue ADT: The elements are inserted from the end and dequeued from the first position in First in First out (FIFO) order. Using the above-defined functions, Bill implements a queue ADT with the following approach:
The pseudocode for the above operations is as follows:
class node:
int data
int priority
node next
node(d, p):
data = d
priority = p
next = Null
class priority_queue:
queue = Null
head = Null
def isempty():
if head == Null:
return True
else:
return False
def insert(data, priority):
newnode = node(data, priority)
if isempty() == True:
queue = new node(newnode)
head = newnode
else:
if head.priority > priority:
head2 = head.next
head = newnode
head.next() = head2
else:
temp = head
while temp.next != Null:
if temp.priority > priority:
head2 = temp.next
temp.next = newnode
newnode.next = head2
break
else:
temp = temp.next
if temp.next == Null:
if temp.priority > priority:
head2 = temp.next
temp.next = newnode
newnode.next = head2
break
else:
temp.next = newnode
def min():
if isempty() == True:
return Null
else:
return head.data
def removeMin():
if isempty() == True:
return Null
else:
data = head.data
head = head.next
return data
class queueADT implements priority_queue:
priority = 0
def front():
if priority_queue.isempty == True:
return Null
else:
return priority_queue.min()
def enqueue(data):
priority_queue.insert(data, priority)
priority = priority + 1
def dequeue():
if priority_queue.isempty == True:
return Null
else:
return priority_queue.removeMin()
b)
Running time of the above algorithm:
If the priority queue is implemented using a binary heap, then the running time would be as follows:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.