Using Python

Q2 Implement the Bounded Queue and Circular Queue ADT as seen in class. The python implementations of these data structures are in the lecture slides. Make sure you raise exceptions when peek()/dequeue() if the queue is empty. enqueue() if the queue is full .

Compare the runtime of dequeue() methods in Bounded Queue and Circular Queue. In bounded queue, once you dequeue an item, the remaining items in the list will be shifted left. This happen because we are using the pop(index) method in the list class to dequeue. Therefore, the dequeue in Bounded Queue is O(n). However in Circular Queue, the front most item is accessed in the list by using the subscription operator and the head is incremented by 1. Therefore, the dequeue in a Circular Queue is O(1).

So in theory, dequeue in Circular Queue should be much faster than the dequeue in a Bounded Queue. Write your code to justify whether this hypothesis is true or false.

Here are the steps for this experiment:

1. Create a Circular Queue object and enqueue 100000 items in it.

2. Create a Bounded Queue object and enqueue 100000 items in it

3. Compute the time required to dequeue all items from the Circular Queue.

4. Compute the time required to dequeue all items from the Bounded Queue.

Here is how to use the time module :

import time

start = time.time()

# The statement(s) that you want to test

end = time.time()

time_interval = end - start

5. Print the dequeue() runtime for each queue

Please note : We need to enqueue many items in the Circular and Bounded Queue in order to get a reasonable run time for both queues.

Here is the sample output:

For Bounded Queue, the total runtime of dequeing 100000 is:

2.2983570098876953

For Circular Queue, the total runtime of dequeing 100000 is:

0.11895871162414551

For this question here is the code I have so far, but it doesnt match the run time for the sample output?

class BQueue: def __init__(self, capacity): assert isinstance(capacity, int), ('Error: Type error: %s' % (type(capacity))) assert capacity >0, ('Error: Illegal capacity: %d' % (capacity)) self.__items = [] self.__capacity = capacity def enqueue(self, item): if len(self.__items) == self.__capacity: raise Exception('Error: Queue is full') self.__items.append(item) def dequeue(self): if len(self.__items) == 0: raise Exception('Error: Queue is empty') return self.__items.pop(0) def peek(self): if len(self.__items) == 0: raise Exception('Error: Queue is empty') return self.__items[0] def isEmpty(self): return len(self.__items) == 0 def isFull(self): return len(self.__items) == self.__capacity def size(self): return len(self.__items) def capacity(self): return self.__capacity def clear(self): self.__items = [] def __str__(self): str_exp = "" for item in self.__items: str_exp += (str(item) + " ") return str_exp

def __repr__(self): return str(self.items) + " Max=" + str(self.__capacity) class CQueue: def __init__(self, capacity): if type(capacity) != int or capacity<=0: raise Exception ("Capacity Error") self.__items = [] self.__capacity = capacity self.__count=0 self.__head=0 self.__tail=0 def enqueue(self, item): if self.__count== self.__capacity: raise Exception('Error: Queue is full') if len(self.__items) < self.__capacity: self.__items.append(item) else: self.__items[self.__tail]=item self.__count +=1 self.__tail=(self.__tail +1) % self.__capacity def dequeue(self): if self.__count == 0: raise Exception('Error: Queue is empty') item = self.__items[self.__head] self.__items[self.__head]=None self.__count -=1 self.__head=(self.__head+1) % self.__capacity return item def peek(self): if self.__count == 0: raise Exception('Error: Queue is empty') return self.__items[self.__head] def isEmpty(self): return self.__count == 0 def isFull(self): return self.__count == self.__capacity def size(self): return self.__count def capacity(self): return self.__capacity def clear(self): self.__items = [] self.__count=0 self.__head=0 self.__tail=0 def __str__(self): str_exp = "]" i=self.__head for j in range(self.__count): str_exp += str(self.__items[i]) + " " i=(i+1) % self.__capacity return str_exp + "]" def __repr__(self): return str(self.__items) + ' Head=' + str(self.__head) + ' Tail='+str(self.__tail) + ' ('+str(self.__count)+'/'+str(self.__capacity)+')'