Mehrere Möglichkeiten zur Implementierung von Stacks in Python und ihre Vor- und Nachteile

​​Um mehr über Open Source zu erfahren, besuchen Sie bitte:​​

​​51CTO Open Source Basic Software Community​​

​​https://ost.51cto.com​ ​

1. Das Konzept des Stapels

Ein Stapel ist eine durch eine Reihe von Objekten organisierte Sammlung. Die Hinzufügungs- und Löschvorgänge dieser Objekte folgen einem „Last In First Out“ (LIFO)-Prinzip.

Es kann immer nur ein Objekt in den Stapel eingefügt werden, das Erfassen oder Löschen kann jedoch nur an der Spitze des Stapels erfolgen. Beispielsweise ist in einem Stapel aus Büchern nur das Buch oben sichtbar, dessen Einband frei liegt. Um an andere Bücher zu gelangen, kann nur das oberste Buch entfernt werden, wie im Bild gezeigt:

Praktische Anwendung des Stacks

Viele Anwendungen im Internet nutzen Stacks, wie zum Beispiel:

1. Webbrowser speichern kürzlich besuchte URLs in einem Stack. Immer wenn ein Benutzer eine neue Website besucht, wird die URL der neuen Website an die Spitze des Stapels verschoben. Auf diese Weise kann jedes Mal, wenn wir im Browser auf die Schaltfläche „Zurück“ klicken (oder die Tastenkombination STRG+Z drücken, die meisten Rückgängig-Tastenkombinationen), die zuletzt besuchte URL angezeigt werden, um zur zuvor besuchten Suche zurückzukehren. Zustand.
2. Texteditoren bieten oft einen „Rückgängig“-Mechanismus, um den letzten Bearbeitungsvorgang abzubrechen und zum vorherigen Zustand zurückzukehren. Dieser Rückgängig-Vorgang wird auch dadurch erreicht, dass der geänderte Status des Texts in einem Stapel gespeichert wird.
3. Speicherverwaltung einiger Hochsprachen, JVM-Stack, Python-Stack werden auch für die Speicherverwaltung, Laufzeitumgebung verschachtelter Sprachfunktionen usw. verwendet.
4. Backtracking (Spiele spielen, Pfade finden, umfassende Suche)
5. Wird in Algorithmen verwendet B. der Turm von Hanoi, Baumdurchquerung, Histogrammprobleme und auch in Diagrammalgorithmen wie der topologischen Sortierung verwendet
6. Syntaxverarbeitung:

• Der Platz für Parameter und lokale Variablen wird intern mithilfe eines Stapels erstellt.
• Die Syntaxprüfung des Compilers für den Klammerabgleich
• Unterstützung für Rekursion
• Ausdrücke wie Suffixe oder Präfixe im Compiler

2. Der abstrakte Datentyp des Stapels

Jede Datenstruktur ist untrennbar miteinander verbunden. So speichern und erhalten Sie Daten. Wie oben erwähnt, ist ein Stapel eine geordnete Sammlung von Elementen, die alle an der Spitze des Stapels (oben im Stapel) erfolgen. Dann umfassen seine abstrakten Datentypen:

• Stack(): Erstellt ein leerer Stapel, benötigt keine Parameter und gibt einen leeren Stapel zurück.
• push(e): Fügt ein Element e oben im Stapel S hinzu. Es erfordert einen Parameter e und hat keinen Rückgabewert.
• pop(): Entfernen Sie das Element oben im Stapel. Es sind keine Parameter erforderlich, es wird jedoch das oberste Element zurückgegeben und der Inhalt des Stapels geändert.
• top(): Gibt das Element oben im Stapel zurück, entfernt jedoch nicht das Element oben im Stapel. Wenn der Stapel leer ist, wird dieser Vorgang ausgeführt.
• is_empty(): Wenn der Stapel keine Elemente enthält, wird der boolesche Wert „True“ zurückgegeben.
• size(): Gibt die Daten der Elemente im Stapel zurück. Es erfordert keine Parameter und gibt eine Ganzzahl zurück. In Python kann dies mit der speziellen Methode __len__ erreicht werden.

Die Größe des Python-Stacks ist möglicherweise festgelegt, oder es gibt eine dynamische Implementierung, die eine Änderung der Größe zulässt. Bei einem Stapel fester Größe führt der Versuch, einem bereits vollen Stapel ein Element hinzuzufügen, zu einer Stapelüberlaufausnahme. Ebenso führt der Versuch, ein Element aus einem bereits leeren Stapel zu entfernen, zu ​pop()​​ Diese Situation wird als Unterlauf bezeichnet. ​pop()​​ 操作这种情况被称为下溢。

三、用 Python 的列表实现栈

在学习 Python 的时候，一定学过 Python 列表 ​​list​

3. Verwenden Sie Python-Listen, um Stapel zu implementieren

• Wenn Sie Python lernen, müssen Sie Python-Listen gelernt haben ​​list​​ , es kann die Stapelfunktion durch einige integrierte Methoden realisieren:
• Verwenden Sie die Append-Methode, um a hinzuzufügen Elemente am Ende der Liste hinzufügen, kann diese Methode die push()-Operation simulieren.
• Die Methode pop() wird zum Simulieren von Pop-Operationen verwendet.
• Simulieren Sie die top()-Operation über L[-1].
• Simulieren Sie die Operation isEmpty(), indem Sie len(L)==0 beurteilen.

Implementieren Sie die Funktion size() über die Funktion len().

🎜🎜Der Code lautet wie folgt: 🎜

class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.append(e)

def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop()
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[-1]# the last item in the list
arrayStack = ArrayStack()
arrayStack.push("Python")
arrayStack.push("Learning")
arrayStack.push("Hello")
print("Stack top element: ", arrayStack.top())
print("Stack length: ", arrayStack.size())
print("Stack popped item: %s" % arrayStack.pop())
print("Stack is empty?", arrayStack.is_empty())
arrayStack.pop()
arrayStack.pop()
print("Stack is empty?", arrayStack.is_empty())
# arrayStack.pop()

Führen Sie dieses Programm aus. Das Ergebnis ist:

Stack top element:Hello
Stack length:3
Stack popped item: Hello
Stack is empty? False
Stack is empty? True

Sie können nicht nur das Ende der Liste als obersten Punkt des Stapels verwenden, sondern auch den Kopf der Liste als obersten Punkt des Stapels. Allerdings können Sie in diesem Fall die Methoden pop() und append() nicht direkt verwenden, sondern über die Methoden pop() und insert() explizit auf das Element mit Index 0 zugreifen, das das erste Element der Liste ist . Der Code lautet wie folgt:

rrree

Obwohl wir die Implementierung des abstrakten Datentyps geändert haben, haben wir seine logischen Eigenschaften beibehalten. Diese Fähigkeit verkörpert abstrakte Ideen. Obwohl beide Methoden Stapel implementieren, unterscheiden sich ihre Leistungsmethoden: Die zeitliche Komplexität der Methoden

• append()​ und pop() sind beide *O(1), *Operationen auf konstanter Ebene
• Die Leistung der zweiten Die Implementierung ist durch die Anzahl der Elemente im Stapel begrenzt. Dies liegt daran, dass die Zeitkomplexität von insert(0)​ und pop(0) O(n) ist und es umso langsamer ist, je mehr Elemente vorhanden sind. ​

4. Verwenden Siecollections.deque, um den Stack zu implementieren.

In Python verfügt das Collections-Modul über eine doppelendige Warteschlangendatenstruktur. Diese Datenstruktur implementiert auch die Methoden append() und pop():

class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.insert(0, e) 
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop(0)
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[0]# the last item in the list

Warum braucht List immer noch Deque?

Vielleicht können Sie sehen, dass Deque und Liste auf die gleiche Weise auf Elemente einwirken. Warum fügt Python Listen eine Deque-Datenstruktur hinzu?

Das liegt daran, dass Listen in Python in zusammenhängenden Speicherblöcken aufgebaut sind, was bedeutet, dass die Elemente der Liste direkt nebeneinander gespeichert werden.

Dies funktioniert hervorragend für einige Vorgänge, wie zum Beispiel das Indizieren einer Liste. Das Abrufen von myList[3] geht schnell, da Python genau weiß, wo es im Speicher suchen muss. Dieses Speicherlayout ermöglicht auch eine gute Slicing-Funktion bei Listen.

Beim zusammenhängenden Speicherlayout der Liste kann es länger dauern, bis .append() einige Objekte enthält. Wenn der fortlaufende Speicherblock voll ist, muss zuerst ein weiterer Speicherblock abgerufen und der gesamte Speicherblock kopiert werden. Diese Aktion kann länger dauern als der normale .append()-Vorgang.

Die doppelendige Warteschlangen-Deque basiert auf einer doppelt verknüpften Liste. In einer verknüpften Listenstruktur wird jeder Eintrag in einem eigenen Speicherblock gespeichert und verfügt über einen Verweis auf den nächsten Eintrag in der Liste.

Das Gleiche gilt für eine doppelt verknüpfte Liste, mit der Ausnahme, dass jeder Eintrag einen Verweis auf den vorherigen und nächsten Eintrag in der Liste hat. Dies erleichtert das Hinzufügen von Knoten an beiden Enden der Liste.

Um einen neuen Eintrag in einer verknüpften Listenstruktur hinzuzufügen, legen Sie einfach die Referenz des neuen Eintrags so fest, dass sie auf die Oberseite des aktuellen Stapels zeigt, und zeigen Sie dann mit der Oberseite des Stapels auf den neuen Eintrag.

Diese Zeit des ständigen Hinzufügens und Entfernens von Einträgen auf dem Stapel ist jedoch mit Kosten verbunden. Das Abrufen von myDeque[3] ist langsamer als das Abrufen einer Liste, da Python jeden Knoten der Liste durchlaufen muss, um das dritte Element abzurufen.

Glücklicherweise möchten Sie selten Elemente auf dem Stapel zufällig indizieren oder Listen-Slicing-Vorgänge durchführen. Die meisten Operationen auf dem Stapel sind Push oder Pop.

Wenn Ihr Code keine Threads verwendet, machen die zeitkonstanten .append()- und .pop()-Operationen deque zu einer besseren Wahl für die Implementierung des Python-Stacks.

5. Verwenden Sie queue.LifoQueue, um den Stack zu implementieren. Python-Stack ist auch in Multithread-Programmen sehr nützlich. Wir haben bereits die beiden Methoden list und deque gelernt. Für jede Datenstruktur, auf die mehrere Threads zugreifen können, sollten wir in der Multithread-Programmierung keine Liste verwenden, da Listen nicht threadsicher sind. Die Methoden .append() und .pop() von deque sind atomar, was bedeutet, dass sie nicht von verschiedenen Threads gestört werden.

Während die Verwendung von deque einen threadsicheren Python-Stack erstellen kann, sind Sie dadurch anfällig für künftigen Missbrauch und schaffen Rennbedingungen.

Okay, wenn Sie Multithread-Programmierung betreiben, können Sie list nicht als Stapel verwenden, und Sie möchten wahrscheinlich auch nicht deque als Stapel verwenden. Wie erstellt man also einen Python-Stack für ein Thread-Programm?

Die Antwort liegt im Warteschlangenmodul: queue.LifoQueue. Erinnern Sie sich, wie Sie erfahren haben, dass der Stack nach dem Last-In-First-Out-Prinzip (LIFO) arbeitet? Nun, genau das repräsentiert der „Lifo“-Teil von LifoQueue.

Obwohl die Schnittstellen von list und deque ähnlich sind, verwendet LifoQueue .put() und .get(), um Daten zum Stapel hinzuzufügen und daraus zu entfernen.

>>> from queue import LifoQueue
>>> stack = LifoQueue()
>>> stack.put('H')
>>> stack.put('E')
>>> stack.put('L')
>>> stack.put('L')
>>> stack.put('O')
>>> stack
<queue.LifoQueue object at 0x00000123159F7310>
>>> 
>>> stack.get()
'O'
>>> stack.get()
'L'
>>> stack.empty()
False
>>> stack.qsize()
3
>>> stack.get()
'L'
>>> stack.get()
'E'
>>> stack.qsize()
1
>>> stack.get()
'H'
>>> stack.get_nowait()
Traceback (most recent call last):
File "<pyshell#31>", line 1, in <module>
stack.get_nowait()
_queue.Empty
>>> 

>>> stack.put('Apple')
>>> stack.get_nowait()
'Apple'

与 deque 不同，LifoQueue 被设计为完全线程安全的。它的所有方法都可以在线程环境中安全使用。它还为其操作添加了可选的超时功能，这在线程程序中经常是一个必须的功能。

然而，这种完全的线程安全是有代价的。为了实现这种线程安全，LifoQueue 必须在每个操作上做一些额外的工作，这意味着它将花费更长的时间。

通常情况下，这种轻微的减速对你的整体程序速度并不重要，但如果你已经测量了你的性能，并发现你的堆栈操作是瓶颈，那么小心地切换到 deque 可能是值得做的。

六、选择哪一种实现作为栈

一般来说，如果你不使用多线程，你应该使用 deque。如果你使用多线程，那么你应该使用 LifoQueue，除非你已经测量了你的性能，发现 push 和 pop 的速度的小幅提升会带来足够的差异，以保证维护风险。

你可以对列表可能很熟悉，但需要谨慎使用它，因为它有可能存在内存重新分配的问题。deque 和 list 的接口是相同的，而且 deque 没有线程不安全问题。

七、总结

本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中如何使用它的情况。在文章的中，介绍了 Python 中实现栈的三种不同方式，知道了 deque 对于非多线程程序是一个更好的选择，如果你要在多线程编程环境中使用栈的话，可以使用 LifoQueue。

​​想了解更多关于开源的内容，请访问：​​

​​51CTO 开源基础软件社区​​

​​https://ost.51cto.com​​。

Das obige ist der detaillierte Inhalt vonMehrere Möglichkeiten zur Implementierung von Stacks in Python und ihre Vor- und Nachteile. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!