PHP Master | Datenstrukturen für PHP -Entwickler: Stapel und Warteschlangen

Eine Datenstruktur oder abstrakte Datentyp (ADT) ist ein Modell, das durch eine Sammlung von Operationen definiert wird, die an sich selbst durchgeführt werden können und durch die Einschränkungen auf die Auswirkungen dieser Operationen begrenzt werden. Es schafft eine Wand zwischen dem, was den zugrunde liegenden Daten angetan werden kann und wie sie getan werden soll. Die meisten von uns sind mit Stapeln und Warteschlangen im normalen Alltag vertraut, aber was haben Supermarktwarteschlangen und Verkaufsautomaten mit Datenstrukturen zu tun? Lassen Sie uns herausfinden. In diesem Artikel stelle ich Ihnen zwei grundlegende abstrakte Datentypen vor - Stack und Warteschlange -, die ihren Ursprung in der täglichen Verwendung haben.

Key Takeaways

• abstrakte Datentypen (ADTs) sind Modelle, die durch eine Reihe von Operationen definiert werden, die darauf ausgeführt werden können. Stapel und Warteschlangen sind grundlegende ADTs mit Ursprung im täglichen Gebrauch. In der Informatik ist ein Stapel eine sequentielle Sammlung, in der das letzte platzierte Objekt das erste entfernt ist (LIFO), während eine Warteschlange mit First-in-Basis (FIFO) arbeitet.
• Ein Stapel kann mit Arrays implementiert werden, da er bereits Push- und Popoperationen bietet. Die grundlegenden Operationen, die einen Stapel definieren, umfassen Init (erstellen Sie den Stapel), drücken (ein Element nach oben), Pop (das zuletzt hinzugefügte Element entfernen), oben (schauen Sie sich den Element oben, ohne ihn zu entfernen) und isEmpty (Rückgabe ob der Stapel keine Elemente mehr enthält.
• Die SPL -Erweiterung in PHP liefert einen Satz von Standarddatenstrukturen, einschließlich der Splstack -Klasse. Die als doppelt verknüpfte Liste implementierte Splstack-Klasse bietet die Fähigkeit, einen durchlaufbaren Stack zu implementieren. Die als Splstack implementierte Leseliste kann den Stapel nach vorne (oben nach unten) und rückwärts (Bottom-up) durchqueren.
• Eine Warteschlange, ein weiterer abstrakter Datentyp, arbeitet als erstes, erstes Out-Basis (FIFO). Die grundlegenden Operationen, die eine Warteschlange definieren, umfassen Init (erstellen Sie die Warteschlange), Enqueue (ein Element zum Ende hinzufügen), dequeue (entfernen Sie ein Element von vorne) und Isempty (zurück, ob die Warteschlange mehr mehr Elemente enthält). Die Splqueue-Klasse in PHP, die auch mit einer doppelt verknüpften Liste implementiert ist, ermöglicht die Implementierung einer Warteschlange.

stapelt

Im allgemeinen Gebrauch ist ein Stapel ein Haufen Objekte, die normalerweise in Schichten angeordnet sind - zum Beispiel ein Stapel Bücher auf Ihrem Schreibtisch oder ein Stapel Tabletts in der Schulcafeteria. In Informatik -Sprachhäusern ist ein Stapel eine sequentielle Sammlung mit einer bestimmten Eigenschaft, in der das letzte Objekt, das auf dem Stapel platziert ist, das erste Objekt entfernt ist. Diese Eigenschaft wird allgemein als als zuerst in der ersten oder lifeo bezeichnet. Süßigkeiten-, Chip- und Zigarettenautomaten arbeiten nach demselben Prinzip; Der letzte im Rack geladene Artikel wird zuerst abgegeben. In abstrakter Begriffen ist ein Stapel eine lineare Liste von Elementen, bei denen alle Ergänzungen zu (ein „Push“) und Löschungen von (einem „Pop“) die Liste auf ein Ende beschränkt sind - definiert als „Top“ (des Stapel ). Die grundlegenden Operationen, die einen Stapel definieren, sind:

• init - Erstellen Sie den Stapel.
• drücken - fügen Sie einen Gegenstand an die Oberseite des Stapels hinzu.
• pop - Entfernen Sie das letzte Element, das oben am Stapel hinzugefügt wurde.
• oben - Sehen Sie sich den Artikel oben im Stapel an, ohne ihn zu entfernen.
• isempty - Rückgabe, ob der Stapel keine weiteren Elemente enthält.

Ein Stapel kann auch implementiert werden, um eine maximale Kapazität zu haben. Wenn der Stapel voll ist und nicht genügend Slots enthält, um neue Einheiten zu akzeptieren, wird es als Überlauf - daher der Ausdruck „Stapelüberlauf“ bezeichnet. Ebenso tritt ein Pop -Operation auf einen leeren Stapel ein, dann tritt ein „Stapelunterlauf“ auf. Da wir wissen, dass unser Stapel durch die LIFO -Eigenschaft und eine Reihe von Grundvorgängen definiert wird, insbesondere Push and Pop, können wir einen Stapel mit Arrays problemlos implementieren, da Arrays bereits Push- und Pop -Operationen bereitstellen. So sieht unser einfacher Stack aus:

<span><span><?php </span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span></span>

In diesem Beispiel habe ich Array_unshift () und Array_Shift () anstelle von array_push () und array_pop () verwendet, damit das erste Element des Stapels immer das obere ist. Sie können Array_push () und array_pop () verwenden, um die semantische Konsistenz aufrechtzuerhalten. In diesem Fall wird das nte Element des Stapels zum Oberteil. Es macht keinen Unterschied, da der gesamte Zweck eines abstrakten Datentyps darin besteht, die Manipulation der Daten aus seiner tatsächlichen Implementierung abstrahieren. Fügen wir dem Stapel einige Artikel hinzu:

<span><span><?php </span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span></span>

Um einige Gegenstände aus dem Stapel zu entfernen:

<span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span></span>

Mal sehen, was oben auf dem Stapel steht:

<span><span><?php </span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span></span>

Was ist, wenn wir es entfernen?

<span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Feast for Crows'</span></span></span>

Und wenn wir einen neuen Artikel hinzufügen?

<span><span><?php </span></span><span><span>$myBooks->push('The Armageddon Rag');
</span></span><span><span>echo $myBooks->pop(); // outputs 'The Armageddon Rag'</span></span></span>

Sie können sehen, dass der Stack in erster Ausgabe funktioniert. Was auch immer zum Stapel zuletzt hinzugefügt wird, ist der erste, der entfernt wird. Wenn Sie weiterhin Pop -Artikel bis zum leeren Stapel popieren, erhalten Sie eine Ausnahme von Stapel -Unterlauflaufzeiten.

PHP Fatal error:  Uncaught exception 'RuntimeException' with message 'Stack is empty!' in /home/ignatius/Data Structures/code/array_stack.php:33
Stack trace:
#0 /home/ignatius/Data Structures/code/example.php(31): ReadingList->pop()
#1 /home/ignatius/Data Structures/code/array_stack.php(54): include('/home/ignatius/...')
#2 {main}
  thrown in /home/ignatius/Data Structures/code/array_stack.php on line 33

Oh, hallo ... PHP hat freundlicherweise eine Stapelverfolgung zur Verfügung gestellt, die den Programmausführungsstapel vor und bis zur Ausnahme zeigt!

Der Splstack

Die SPL -Erweiterung bietet eine Reihe von Standarddatenstrukturen, einschließlich der Splstack -Klasse (PHP5> = 5.3.0). Wir können dasselbe Objekt implementieren, wenn auch viel schlauer, wenn wir einen Splast wie folgt verwenden:

<span><span><?php </span></span><span><span>class ReadingList extends SplStack
</span></span><span><span>{
</span></span><span><span>}</span></span></span>

Die Splstack -Klasse implementiert einige weitere Methoden als wir ursprünglich definiert haben. Dies liegt daran, dass Splstack als doppelt verknüpfte Liste implementiert wird, die die Fähigkeit zur Implementierung eines durchlaufbaren Stacks bietet. Eine verknüpfte Liste, ein weiterer abstrakter Datentyp selbst, ist eine lineare Sammlung von Objekten (Knoten), die zur Darstellung einer bestimmten Sequenz verwendet wird, wobei jeder Knoten in der Sammlung einen Zeiger auf den nächsten Knoten in der Sammlung beibehält. In seiner einfachsten Form sieht eine verknüpfte Liste ähnlich aus:

In einer doppelt verknüpften Liste hat jeder Knoten zwei Zeiger, die jeweils auf die nächsten und vorherigen Knoten in der Sammlung hinweisen. Diese Art von Datenstruktur ermöglicht das Durchlaufen in beide Richtungen.

Mit einem Kreuz (x) gekennzeichnete Knoten bezeichnen einen Null- oder Sentinel -Knoten - das das Ende des Traversalweges (d. H. Der Pfadanschluss) bezeichnet. Da die Leseliste als Splstack implementiert ist, können wir den Stapel nach vorne (Top-Down) und rückwärts (Bottom-up) durchqueren. Der Standard -Traversal -Modus für Splstack ist LIFO:

<span><span><?php </span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span></span>

Um den Stapel in umgekehrter Reihenfolge zu durchqueren, setzen wir einfach den Iteratormodus auf FIFO (zuerst in, zuerst heraus):

<span><span><?php </span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span></span>

Warteschlangen

Wenn Sie jemals an der Supermarktkasse in einer Reihe waren, wissen Sie, dass die erste Person in der Schlange zuerst serviert wird. In der Computerterminologie ist eine Warteschlange ein weiterer abstrakter Datentyp, der zuerst in der ersten Ausgabe von oder FIFO arbeitet. Das Bestand wird auch fifo verwaltet, insbesondere wenn solche Gegenstände verderblich sind. Die grundlegenden Operationen, die eine Warteschlange definieren, sind:

init - Erstellen Sie die Warteschlange.
Enqueue - Fügen Sie ein Element zum "Ende" (Schwanz) der Warteschlange hinzu.
dequeue - Entfernen Sie ein Element von der „Vorderseite“ (Kopf) der Warteschlange.
isempty - Rückgabe, ob die Warteschlange keine weiteren Elemente enthält.

Da Splqueue auch mit einer doppelt verknüpften Liste implementiert wird, werden in diesem Zusammenhang die semantische Bedeutung von Top und POP umgekehrt. Definieren wir unsere Leselistklasse als Warteschlange neu:

<span><span><?php </span></span><span><span>class ReadingList
</span></span><span><span>{
</span></span><span>    <span>protected $stack;
</span></span><span>    <span>protected $limit;
</span></span><span>    
</span><span>    <span>public function __construct($limit = 10) {
</span></span><span>        <span>// initialize the stack
</span></span><span>        <span>$this->stack = array();
</span></span><span>        <span>// stack can only contain this many items
</span></span><span>        <span>$this->limit = $limit;
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function push($item) {
</span></span><span>        <span>// trap for stack overflow
</span></span><span>        <span>if (count($this->stack) limit) {
</span></span><span>            <span>// prepend item to the start of the array
</span></span><span>            <span>array_unshift($this->stack, $item);
</span></span><span>        <span>} else {
</span></span><span>            <span>throw new RunTimeException('Stack is full!'); 
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function pop() {
</span></span><span>        <span>if ($this->isEmpty()) {
</span></span><span>            <span>// trap for stack underflow
</span></span><span>	      <span>throw new RunTimeException('Stack is empty!');
</span></span><span>	  <span>} else {
</span></span><span>            <span>// pop item from the start of the array
</span></span><span>            <span>return array_shift($this->stack);
</span></span><span>        <span>}
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function top() {
</span></span><span>        <span>return current($this->stack);
</span></span><span>    <span>}
</span></span><span>
</span><span>    <span>public function isEmpty() {
</span></span><span>        <span>return empty($this->stack);
</span></span><span>    <span>}
</span></span><span><span>}</span></span></span>

SpldoublyLinkedList Implementiert auch die ArrayAccess -Schnittstelle, sodass Sie als Array -Elemente auch Elemente sowohl zu Splqueue als auch zu Splstack hinzufügen können:

<span><span><?php </span></span><span><span>$myBooks = new ReadingList();
</span></span><span>
</span><span><span>$myBooks->push('A Dream of Spring');
</span></span><span><span>$myBooks->push('The Winds of Winter');
</span></span><span><span>$myBooks->push('A Dance with Dragons');
</span></span><span><span>$myBooks->push('A Feast for Crows');
</span></span><span><span>$myBooks->push('A Storm of Swords'); 
</span></span><span><span>$myBooks->push('A Clash of Kings');
</span></span><span><span>$myBooks->push('A Game of Thrones');</span></span></span>

Gegenstände von der Vorderseite der Warteschlange zu entfernen:

<span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings'
</span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span></span>

enqueue () ist ein Alias ​​für Push (), aber beachten Sie, dass dequeue () kein Alias ​​für Pop () ist; pop () hat eine andere Bedeutung und Funktion im Kontext einer Warteschlange. Wenn wir hier Pop () verwendet hätten, würde es das Element am Ende (Schwanz) der Warteschlange entfernen, die gegen die FIFO -Regel verstößt. In ähnlicher Weise müssen wir BOWS () anstelle von Top () verwenden, um zu sehen, was vorne (Kopf) der Warteschlange steht:

<span><span><?php </span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span></span>

Zusammenfassung

In diesem Artikel haben Sie gesehen, wie die abstrakten Datentypen von Stack und Warteschlangen bei der Programmierung verwendet werden. Diese Datenstrukturen sind abstrakt, da sie durch die Operationen definiert werden, die an sich selbst durchgeführt werden können, wodurch eine Wand zwischen der Implementierung und den zugrunde liegenden Daten erstellt wird. Diese Strukturen werden auch durch die Auswirkung solcher Vorgänge eingeschränkt: Sie können Elemente nur vom oberen Rand des Stapels hinzufügen oder entfernen und nur Elemente von der Vorderseite der Warteschlange entfernen oder Gegenstände in die hintere Warteschlange hinzufügen. Bild von Alexandre Dulaunoy über Flickr

häufig gestellte Fragen (FAQs) zu PHP -Datenstrukturen

Was sind die verschiedenen Arten von Datenstrukturen in PHP?

PHP unterstützt verschiedene Arten von Datenstrukturen, einschließlich Arrays, Objekten und Ressourcen. Arrays sind die häufigsten und vielseitigsten Datenstrukturen in PHP. Sie können alle Arten von Daten enthalten, einschließlich anderer Arrays, und können indiziert oder assoziativ werden. Objekte in PHP sind Instanzen von Klassen, die Eigenschaften und Methoden haben können. Ressourcen sind spezielle Variablen, die Verweise auf externe Ressourcen enthalten, z. B. Datenbankverbindungen.

Wie kann ich einen Stapel in PHP implementieren? Zuletzt, zum ersten Mal) Prinzip. In PHP können Sie die Splstack -Klasse verwenden, um einen Stapel zu implementieren. Sie können Elemente mit der PUSP () -Methode auf den Stapel schieben und mit der POP () -Methode Pop -Elemente vom Stapel aus dem Stapel. Arrays und Objekte in PHP sind beide Arten von Datenstrukturen, haben jedoch einige wichtige Unterschiede. Arrays sind einfache Wertelisten, während Objekte Instanzen von Klassen sind und Eigenschaften und Methoden haben können. Arrays können indiziert oder assoziativ werden, während Objekte immer String -Tasten verwenden. Arrays sind vielseitiger und einfacher zu bedienen, während Objekte mehr Struktur und Kapselung liefern.

Wie kann ich Datenstrukturen verwenden, um die Leistung meines PHP -Code zu verbessern? Wenn Sie beispielsweise eine große Anzahl von Elementen speichern und häufig nach bestimmten Elementen suchen müssen, kann die Verwendung einer Hash -Tabelle oder eines Satzes viel schneller sein als die Verwendung eines Arrays. Wenn Sie an beiden Enden häufig Elemente hinzufügen und entfernen müssen, kann die Verwendung eines Deque effizienter sein als die Verwendung eines Arrays. In PHP ist eine Datenstruktur, die eine doppelt verknüpfte Liste implementiert. Sie können in konstanter Zeit an beiden Enden der Liste auf Elemente an beiden Enden der Liste hinzufügen, entfernen und zugreifen. Es bietet auch Methoden zum Iterieren der Elemente in der Liste und zum Sortieren der Elemente.

Wie kann ich eine Warteschlange in PHP implementieren. Das FIFO -Prinzip (zuerst in, zuerst). In PHP können Sie die Splqueue -Klasse verwenden, um eine Warteschlange zu implementieren. Sie können Elemente mit der Enqueue () -Methode auf die Warteschlange und Dequeue -Elemente aus der Warteschlange mit der Methode dequeue (). 🎜> Ein Stapel und eine Warteschlange sind beide Arten von Datenstrukturen, haben jedoch einen wesentlichen Unterschied in der Hinzufügung und Entfernung von Elementen. Ein Stapel folgt dem LIFO -Prinzip (zuletzt, zuerst), was bedeutet, dass das letzte hinzugefügte Element das erste ist, das entfernt wird. Andererseits folgt eine Warteschlange dem FIFO -Prinzip (zuerst in, zuerst), was bedeutet, dass das erste hinzugefügte Element das erste ist, das entfernt wird.

Die Splheap -Klasse in PHP ist eine Datenstruktur, die einen Haufen implementiert. Ein Haufen ist eine Art binärer Baum, bei dem jeder übergeordnete Knoten weniger oder gleich seinen untergeordneten Knoten ist. Sie können mit der Klassenklasse einen Minimer oder einen Max-heap erstellen und Elemente im Haufen hinzufügen, entfernen und zugreifen. >

Die Verwendung von Datenstrukturen in PHP kann mehrere Vorteile bieten. Sie können Ihnen helfen, Ihre Daten effizienter und logischer zu organisieren, wodurch Ihr Code das Verständnis und die Wartung erleichtert wird. Sie können auch die Leistung Ihres Codes verbessern, insbesondere im Umgang mit großen Datenmengen oder komplexen Vorgängen. der Datenstruktur, bei der jeder Knoten zu den beiden zwei Kindern verfügt, die als linkes Kind und das rechte Kind bezeichnet werden. In PHP können Sie einen binären Baum mit einer Klasse mit Eigenschaften für den Wert des Knotens und der linken und rechten Kinder implementieren. Sie können dann Methoden verwenden, um Knoten im Baum hinzuzufügen, zu entfernen und zu suchen.

Das obige ist der detaillierte Inhalt vonPHP Master | Datenstrukturen für PHP -Entwickler: Stapel und Warteschlangen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!