In diesem Artikel geht es um die Implementierungsmethode von Warteschlangen in Python (Codebeispiele). Ich hoffe, dass er für Sie hilfreich ist.
Für Python ist es sehr einfach, eine Warteschlangenklasse basierend auf vorhandenen Methoden zu implementieren. Da die Warteschlange an einem Ende eingefügt und am anderen Ende gelöscht werden muss. Offensichtlich verfügt Python über diese beiden Tools, um das Ende der Warteschlange zu löschen, und um den Kopf einzufügen, können Sie append verwenden. In dieser Hinsicht ist es wirklich einfach, aber man muss immer die optimale Lösung finden, oder? Daher verwenden wir nicht die Pop-Methode, da die Komplexität dieser Methode für die interne Implementierung von Python O(n) ist. Wenn wir das erste Element der Liste löschen, werden alle Elemente in der Liste nach vorne verschoben. Aus diesem Grund möchte Python die Integrität der Liste aufrechterhalten.
Zur Implementierung verwenden wir eine kreisförmige Sequenztabelle die Warteschlange.
Die konkrete Idee ist wie folgt:
Wenn wir mit dem Löschen am Anfang der Liste beginnen, folgt der Kopfzeiger dem Startpunkt des Elementbereichs, dh der Kopfzeiger ändert sich beim Löschen weiter nach hinten, sodass der vordere Knoten leer ist. Wenn der Endzeiger die letzte Position der Liste mit dem hinzugefügten Element erreicht, bewegt sich der Endzeiger zum ersten Knoten der Liste (leerer Knoten). Zum Stoppen, wenn unser Kopfzeiger und Endzeiger konvergieren, bedeutet dies, dass die gesamte feste Liste aufgebraucht ist. Hier definieren wir auch eine Methode zum Erweitern des Speicherplatzes der Warteschlange, die intern aufgerufen wird Ist voll, rufen wir diese interne Methode automatisch auf.
Implementierung:
Analyse, wir können wissen, dass
einen Kopfzeiger definieren kann, um den Startindex des Elementbereichs self anzugeben ;
Definieren Sie eine Variable zum Speichern der Länge des Elementbereichs, self._num
Eine Variable zum Speichern der Länge der gesamten Liste , self._len
und natürlich die Listenvariable, in der sich die Warteschlange befindet, self._list
Schauen wir uns die Definition an mehrere Variablen Mehrere Urteile:
Wenn self._num = self._len, bedeutet dies, dass die Warteschlange zu diesem Zeitpunkt voll ist
Wenn self. _num = 0 Wenn die Warteschlange leer ist
Eine Warteschlange unterstützt mehrere Vorgänge:
Eine leere Warteschlange erstellen
Bestimmen Sie, ob die Warteschlange leer ist
Den Wert am Anfang der Warteschlange abrufen
Vorgang aus der Warteschlange entfernen
Enqueue-Vorgang
Wir definieren auch eine interne Methode, um die Länge der Liste zu erhöhen
Die spezifische Implementierung lautet wie folgt:
# _*_ coding: utf-8 _*_
class OverFlowError(ValueError):
pass
class Queue:
def __init__(self, init_len=0):
self._len = init_len
self._list = [0] * init_len
self._num = 0 # 计数元素
self._head = 0 # 头指针
def is_empty(self):
return self._num == 0
def peek(self):
if self._num == 0:
raise OverFlowError("取队列首位值，但队列为空")
return self._list[self._head]
def enqueue(self, elem):
if self._num = self._len:
self._extend()
self._list[(self._head + self._num) % self._len] = elem
self._num += 1
def dequeue(self):
if self._num == 0:
raise OverFlowError("队列首位出队列，但队列为空")
e = self._list[self._head]
self._head = (self._head + 1) % self._len
self._num -= 1
return e
def _extend(self):
new_len = self._len * 2
new_list = [0] * new_len
i = 0
p = self._head
while not p == (self._head + self._num) % self._len:
new_list[i] = self._list[p]
i += 1
self._len = new_len
self._list = new_list
self._head = 0Die Idee ist sehr wichtig, aber wie man sie umsetzt, ist nicht so wichtig. Es ist besser, wenn Sie sie zuerst umsetzen und dann meine Ergebnisse sehen!
Das obige ist der detaillierte Inhalt vonImplementierungsmethode der Warteschlange in Python (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
