Circular Queue Structure (Array-Backed)

Question

Ich brauche Hilfe beim Schreiben eines Python-Programms, das eine zirkuläre Warteschlangen-Datenstruktur implementiert (Array-Backed). Ich habe bereits ein paar der Methoden abgeschlossen, aber ich bin etwas ratlos, wenn es darum geht, Dinge aus der Warteschlange hinzuzufügen und zu entfernen, sowie die darin enthaltenen Werte zu überprüfen. Ich glaube, das ist von der First-in-first-out-Struktur. Hier ist, was ich für den Körper so weit

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 

Was habe ich geschrieben bisher am meisten Sinn macht für mich aber, wenn ich dies mit dem folgenden Code-Block zu testen wäre, würde ich einen Fehler sagen 10! = 4. Dieser Code wird die 9. Zeile des Tests fehlschlagen, tc.assertEqual(q.data.count(None), 4) Ich bin mir nicht sicher, warum mein Code den Wert 10 zu diesem Zeitpunkt produziert. Was würde dieser Klasse erlauben, den gegebenen Test zu bestehen?

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) 

Answer 1

Ich würde einen Fehler erhalten, dass die Queue-Klasse nicht über ein Datenattribut

Ich habe den Fehler nicht erwähnen Sie, wenn Ihr Test auf Ihrem Code ausgeführt wird.

Answer 2

Ich bin mir ziemlich sicher, dass der gesamte Code mit self.queue falsch ist. Dieses Attribut wird überhaupt nicht benötigt. Der ganze Punkt des Attributs data besteht darin, es zum Speichern der Werte zu verwenden. Verwenden Sie die Indizes head und tail um herauszufinden, wo in data Sachen zu setzen (und wo sie nehmen von):

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

    def dequeue(self): 
     if self.count == 0: 
      raise RuntimeError 
     else: 
      x = self.data[self.head] 
      self.head = (self.head + 1) % self.limit 
      self.count -= 1 
      return x 

    def enqueue(self, item): 
     if self.count == self.limit: 
      raise RuntimeError 
     else: 
      self.count += 1 
      self.tail = (self.tail + 1) % self.limit 
      self.data[self.tail] = item 

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

    def resize(self, new_limit): 
     if new_limit < self.count: 
      raise RuntimeError 
     new_data = [None]*new_limit 
     for i, item in enumerate(self): 
      new_data[i] = item 
     self.data = new_data 
     self.head = 0 
     self.tail = self.count - 1 

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

    def __bool__(self): # this is better than empty() 
     return self.count != 0 

    def __iter__(self): # renamed from iter so you can use it in a for loop 
     for i in range(self.count): 
      return self.data[(self.head + i) % self.limit] 

Sie sollten wahrscheinlich auch eine __len__ Methode haben.