<jupyter_start><jupyter_text>Lab 08: Circular, Array-backed Queue  OverviewFor this assignment you will implement a circular, array-backed queue data structure.In the following class, which you are to complete, the backing array will be created and populated with `None`s in the `__init__` method, and the `head` and `tail` indexes set to sentinel values (you shouldn't need to modify `__init__`). Enqueueing and Dequeueing 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`.Because of the fixed size backing array, the `enqueue` operation is defined to raise a `RuntimeError` when the queue is full — the same exception should be raised when `dequeue` is called on an empty queue.Finally, the `resize` method will allow the array underlying the queue to be increased in size. It is up to you how to implement this (you can either leave the elements in their current positions, though this may require "unwrapping" elements, or you can simply move all elements towards the front of the array). You may assume that `resize` will only be called with a value greater than the current length of the underlying array.<jupyter_code>class Queue:
    def __init__(self, limit=10):
        self.data = [None] * limit
        self.head = -1
        self.tail = -1
        
    def check_idx (self, idx):
        return (idx + 1) % len(self.data)

    def enqueue(self, val):
        if self.head < 0:
            self.head = self.tail = 0
            self.data[0] = val
        elif self.check_idx(self.tail) == self.head:
            raise RuntimeError
        else:
            self.tail = self.check_idx(self.tail)
            self.data[self.tail] = val
        
    def dequeue(self):
        if self.head < 0:
            raise RuntimeError
        i = self.data[self.head]
        self.data[self.head] = None
        if self.head == self.tail:
            self.head = self.tail = -1
        else:
            self.head = self.check_idx(self.head)
        return i
    
    def resize(self, newsize):
        assert(len(self.data) < newsize)
        newdata = list(self)
        if self.head > 0:
            self.head = 0
            self.tail = len(self.data) - 1
        newdata.extend( [ None ] * ( newsize - len(newdata) ) )
        self.data = newdata
    
    def empty(self):
        return self.head < 0
    
    def __bool__(self):
        return not self.empty()
    
    def __str__(self):
        if not(self):
            return ''
        return ', '.join(str(x) for x in self)
    
    def __repr__(self):
        return str(self)
    
    def __iter__(self):
        if self.head < 0:
            return
        i = self.head
        while True:
            yield self.data[i]
            if i == self.tail:
                break
            i = self.check_idx(i)
        
# (5 points)

from unittest import TestCase
tc = TestCase()

q = Queue(5)
tc.assertEqual(q.data, [None] * 5)

for i in range(5):
    q.enqueue(i)
    
with tc.assertRaises(RuntimeError):
    q.enqueue(5)

for i in range(5):
    tc.assertEqual(q.dequeue(), i)
    
tc.assertTrue(q.empty())
# (5 points)

from unittest import TestCase
tc = TestCase()

q = Queue(10)

for i in range(6):
    q.enqueue(i)
    
tc.assertEqual(q.data.count(None), 4)

for i in range(5):
    q.dequeue()
    
tc.assertFalse(q.empty())
tc.assertEqual(q.data.count(None), 9)
tc.assertEqual(q.head, q.tail)
tc.assertEqual(q.head, 5)

for i in range(9):
    q.enqueue(i)

with tc.assertRaises(RuntimeError):
    q.enqueue(10)

for x, y in zip(q, [5] + list(range(9))):
    tc.assertEqual(x, y)
    
tc.assertEqual(q.dequeue(), 5)
for i in range(9):
    tc.assertEqual(q.dequeue(), i)

tc.assertTrue(q.empty())
# (5 points)

from unittest import TestCase
tc = TestCase()

q = Queue(5)
for i in range(5):
    q.enqueue(i)
for i in range(4):
    q.dequeue()
for i in range(5, 9):
    q.enqueue(i)
    
with tc.assertRaises(RuntimeError):
    q.enqueue(10)

q.resize(10)

for x, y in zip(q, range(4, 9)):
    tc.assertEqual(x, y)
    
for i in range(9, 14):
    q.enqueue(i)

for i in range(4, 14):
    tc.assertEqual(q.dequeue(), i)
    
tc.assertTrue(q.empty())
tc.assertEqual(q.head, -1)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1090667257814232, 'fraction_numerical': 0.012857459543338506, 'mean_word_length': 2.514018691588785, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '256605', 'license': 'Apache-2.0', 'n_tokens_mistral': 1487, 'n_tokens_neox': 1450, 'n_words': 500, 'path': 'CS331/Lab08.ipynb', 'repo_name': 'Quananhle/Python', 'size': '4511'}