Design and implement aMinQueuedata structure that can store comparable elements and supports the queue operationsadd(x),remove(), andsize(), as well as themin() operation, which returns the minimum value currently stored in the data structure. All operations should run in constant amortized time
Exercise 3.15.Design and implement aMinQueuedata structure that can store comparable elements and supports the queue operationsadd(x),remove(), andsize(), as well as themin() operation, which returns the minimum value currently stored in the data structure. All operations should run in constant amortized time
class MinQueue:
# this is the list to store the data
queue = []
min_val = 999999
max_val = -1
# add an element to min queue
def qadd(self, x):
if not self.queue or x <= self.min_val:
self.min_val = min(self.min_val, x)
self.queue = [x] + self.queue
elif x >= self.max_val:
self.max_val = max(self.max_val, x)
self.queue.append(x)
else:
for i in range(len(self.queue)):
if self.queue[i] <= x and self.queue[i+1] >= x:
self.queue = self.queue[:i+1] + [x] + self.queue[i+1:]
break
# this is refers to revome an element from the queue
def qremove(self):
if self.queue:
self.queue.pop(0)
if self.queue:
self.min_val = self.queue[0]
else:
self.min_val = 999999
self.max_val = -1
# It will return the size of the queue
def qsize(self):
return len(self.queue)
# It will return the minimum value, -1 if no element is present
def qmin(self):
return self.min_val
#It is driver code
q = MinQueue()
q.qadd(7)
q.qadd(5)
q.qadd(4)
q.qremove()
q.qadd(9)
q.qadd(15)
q.qadd(6)
q.qadd(10)
print(q.qsize())
print(q.qmin())
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
