Implementierungsmethode der Warteschlange in Python (Codebeispiel)

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:

1. Eine leere Warteschlange erstellen

2. Bestimmen Sie, ob die Warteschlange leer ist

3. Den Wert am Anfang der Warteschlange abrufen

4. Vorgang aus der Warteschlange entfernen

5. Enqueue-Vorgang

6. 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 = 0

Die 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!