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

#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: