samedi 18 juin 2016

Circular Queue Structure ( array-backed)

I need some help in writing a python program that will implement a circular queue data structure (array-backed). I've completed a few of the methods already but I'm a bit stumped when it comes to adding and taking things away from the queue, as well as checking the values within it. I believe this is of the first-in-first-out structure. Here's what I have for the body so far

class Queue:
    ''' Constructor '''
    def __init__(self, limit):
        self.limit = limit
        self.data = [None] * limit
        self.queue = []
        self.head = -1
        self.tail = -1
        self.count = 0


    def dequeue(self):
        if self.count == 0:
            raise RuntimeError
        else:
            self.head = 0
            x = self.queue.pop(0)
            if self.head == self.tail:
                self.head = -1
                self.tail = -1
            else:
                self.tail -= 1
            self.count -= 1
            #self.head += 1
            return x

    def enqueue(self, item):
        if self.count == self.limit:
            raise RuntimeError
        else:
            self.count += 1
            self.queue.append(item)
            self.tail += 1

    def __str__(self):
        return " ".join([str(v) for v in self.queue])


    def resize(self, new_limit):
        new_q = [None]*self.limit
        old_q = self.queue
        for i in range(len(old_q)):
            new_q[i] = old_q[i]
        self.limit = new_limit
        self.queue = new_q


    def empty(self):
        return 0 == self.count

    def iter(self):
        listt = []
        for v in self.queue:
            listt.append(v)
        return listt

What I 've written thus far makes the most sense to me but if I were to test this with the following code block I'd get an error saying 10 != 4. This code will fail the 9th line of the test, tc.assertEqual(q.data.count(None), 4) I'm unsure why my code is producing the value 10 at this time. What would allow for this class to pass the given test?

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)

Aucun commentaire:

Enregistrer un commentaire