Um mehr über Open Source zu erfahren, besuchen Sie bitte:
51CTO Open Source Basic Software Community
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:
Viele Anwendungen im Internet nutzen Stacks, wie zum Beispiel:
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:
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 列表 list
list , es kann die Stapelfunktion durch einige integrierte Methoden realisieren: Implementieren Sie die Funktion size() über die Funktion len(). 
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:
rrreeObwohl 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
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 listVielleicht 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.
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。
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!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
