Question

3. Circular, array-backed queue In the following class, which you are to complete, the backing array will be created and populated with Nones in the __init__ method, and the head and tail indexes set to sentinel values (you shouldn't need to modify __init__). Enqueuing and Dequeuing items will take place at the tail and head, with tail and head tracking the position of the most recently enqueued item and that of the next item to dequeue, respectively. To simplify testing, your implementation should make sure that when dequeuing an item its slot in the array is reset to None, and when the queue is emptied its head and tail attributes should be set to -1.

Answer 1

Answer:

#Implementation of Queue class

class Queue

   #Implementation of _init_

   def _init_(self, limit=10):

       #calculate the self.data

       self.data = [None] * limit

       self.head = -1

       self.tail = -1

   #Implementation of enqueue function

   def enqueue(self, val):

       #check self.head - self.tail is equal to 1

       if self.head - self.tail == 1:

           raise NotImplementedError

       #check len(self.data) - 1 is equal to elf.tail

       if len(self.data) - 1 == self.tail and self.head == 0:

           raise NotImplementedError

       #check self.head is equal to -1

       if self.head == -1 and self.tail == -1:

           self.data[0] = val

           self.head = 0

           self.tail = 0

       else:

           #check len(self.data) - 1 is equal to self.tail

           if len(self.data) - 1 == self.tail and self.head != 0:

               self.tail = -1

           self.data[self.tail + 1] = val

           #increment the self.tail value

           self.tail = self.tail + 1

   #Implementation of dequeue method

   def dequeue(self):

       #check self.head is equal to self.tail

       if self.head == self.tail:

           temp = self.head

           self.head = -1

           self.tail = -1

           return self.data[temp]

   

       #check self.head is equal to -1

       if self.head == -1 and self.tail == -1:

           #raise NotImplementedError

          raise NotImplementedError

       #check self.head is not equal to len(self.data)

       if self.head != len(self.data):

           result = self.data[self.head]

           self.data[self.head] = None

           self.head = self.head + 1

       else:

          # resetting head value

           self.head = 0

           result = self.data[self.head]

           self.data[self.head] = None

           self.head = self.head + 1

       return result

   #Implementation of resize method

   def resize(self, newsize):

       #check len(self.data) is less than newsize

       assert (len(self.data) < newsize)

       newdata = [None] * newsize

       head = self.head

       current = self.data[head]

       countValue = 0

       #Iterate the loop

       while current != None:

           newdata[countValue] = current

           countValue += 1

           #check countValue is not equal to 0

           if countValue != 0 and head == self.tail:

               break

           #check head is not equal to

           #len(self.data) - 1

           if head != len(self.data) - 1:

               head = head + 1

               current = self.data[head]

           else:

               head = 0

               current = self.data[head]

     self.data = newdata

       self.head = 0

       self.tail = countValue - 1

   #Implementation of empty method

   def empty(self):

       #check self.head is equal to -1

       # and self.tail is equal to -1

       if self.head == -1 and self.tail == -1:

           return True

       return False

   #Implementation of _bool_() method

   def _bool_(self):            

       return not self.empty()

   #Implementation of _str_() method        

   def _str_(self):

       if not (self):

           return ''

       return ', '.join(str(x) for x in self)

   #Implementation of _repr_ method

   def _repr_(self):

       return str(self)

   #Implementation of _iter_ method

   def _iter_(self):

       head = self.head

       current = self.data[head]

       countValue = 0

       #Iterate the loop

       while current != None:

           yield current

           countValue += 1

           #check countValue is not equal to zero

           #check head is equal to self.tail

           if countValue != 0 and head == self.tail:

               break

           #check head is not equal to len(self.data) - 1

           if head != len(self.data) - 1:

               head = head + 1

               current = self.data[head]

           else:

               head = 0

               current = self.data[head

Explanation:-

Output: