PHP-Arrays als Speicher

Stapel und Warteschlangen mit PHP-Arrays

Die Theorie der Daten-Speicher unterscheidet die beiden Typen "Stapel" (stack, first in - last out) und "Warteschlange" (queue, first in - first out) Alle modernen Programmiersprachen bieten die Möglichkeit, solche Speicher mit Array-Funktionen zu realisieren.
PHP PHP Hypertext Processor, PHP-Arrays
Datenspeicher Verwendung von Arrays als Stapel oder Warteschlangen
Stapel Stack-Speicher: first in - last out
Warteschlange Queue-Speicher: first in - first out (FIFO)
Schieberegister Warteschlange fixer Länge (Förderband)
Sonderfall Funktion array_unshift()
Verwandte Themen Array @ Datenspeicher in Javascript, Perl

Arrays als Datenspeicher

Stapel ↓ (Stack)

Ein Stapel-Speicher wird aus Elementen aufgeschichtet. Man kann immer nur das zuletzt aufgeschichtete Element herunternehmen, das erste (unterste) Element kann als letztes wieder entnommen werden. Ein Stack arbeitet nach dem Prinzip 'first in - last out' und umgekehrt.
● Ein bekanntes Beispiel ist das Spiel Turm von Hanoi: Dabei werden Scheiben zwischen 3 verschiedenen Stapeln umgeschichtet.
Ein Array dient als Stapel-Speicher. Die Funktion array_push() dient zum Aufschichten eines Elements, die Funktion array_pop() zum Herunternehmen.
• Ein typisches Merkmal ist die ständig wechselnde Länge des Arrays (Höhe des Stapels)

Warteschlange ↓ (Queue)

Eine Warteschlange (Förderband, Queue, Shift Register) gibt die darauf enthaltenen Elemente in der gleichen Reihenfolge zurück, in welcher sie gespeichert wurden. Es arbeitet nach dem Prinzip 'first in - first out'.
● Ein bekanntes Beispiel ist eine Haltestelle: Die ankommenden Fahrgäste stellen sich an und bilden eine anwachsende Reihe. Wenn ein Bus kommt, dann steigen die Passagiere in der gleichen Reihenfolge ihres Eintreffens ein - zumindest in der Theorie... 		Ein Array dient als Warteschlangen-Speicher. Die Funktion array_push() dient zum Anreihen eines Elements, die Funktion array_shift() zum Entfernen.
• Typisches Merkmal: Die Änderung der Länge (Zunahme, Abnahme) erfolgt durch unterschiedliche, voneinander unabhängige Prozesse.

Schieberegister (Shift Register)

Ein Sonderfall ist eine Warteschlange fixer Länge (↓ Schieberegister).
● Anschauliches Beispiel Förderband: Mit jedem Schritt wird gleich viel Fördergut auf- und abgeladen. Jedes Fördergut braucht gleich lang, um das Förderband zu passieren. 		Mit jedem Arbeitsschritt wird genau 1 Array-Element am Ende angefügt (array_push() ) und 1 Element am Anfang entnommen (array_shift() ).
• Jedes Element braucht gleich viele Schritte, um das gesamte Array (Schieberegister, Förderband) zu durchlaufen.
♣ Tipp: Verwenden sie für die hier vorgestellten Funktionen nach Möglichkeit nur numerische Schlüssel: Ganze Zahlen, beginnend mit 0 ! Die Funktionen arbeiten zwar auch mit String-Schlüsseln, die Verwaltung ist in diesem Fall jedoch wesentlich komplizierter und gegen Fehler anfällig.

Array als Stapel (Stack)
Neue Elemente werden 'oben' auf den Stapel gelegt, d.h. am Ende des Arrays. Die Entnahme von Elementen erfolgt stets von 'oben', d.h. vom Ende des Arrays. Aufschichten (PUSH) und Abschichten (POP) erfolgen in umgekehrter Reihenfolge (First in, last out).

Aufschichten eines Stapels (PUSH)

• Wenn man einen Stapel aufschichtet, dann erhält das erste (unterste) Element den arithmetischen Schlüssel 0
• Darüber werden alle weiteren Elemente mit den Schlüsseln 1,2,3,... geschichtet.
• Die Funktion array_push() muss als 1.Argument das Stack-Array erhalten. Danach können beliebig viele weitere Argumente folgen, die alle als Array-Elemente auf den Stapel geschichtet werden.
• Die Funktion array_push() gibt die Anzahl der Array-Elemente nach dem Push zurück (hier an die Variable $c ). Meist wird jedoch auf diese Zuweisung verzichtet.
$sa = array();
array_push($sa,'v');
array_push($sa,'w');
$c = array_push($sa,'x','y');
// ergibt $c=4;
print_r($sa);
Ausgabe:
Array([0]=>v [1]=>w [2]=>x [3]=>y );
Die gleiche Wirkung erzielt man durch Zuweisung von Array-Elementen ohne Angabe des Schlüssels (leere [] Klammern). Diese Variante wird meist verwendet, um lange Werte-Listen automatisch in ein Array einzugeben.
$sa[] = 'z';
print_r($sa);
Ausgabe:
Array([0]=>v [1]=>w [2]=>x [3]=>y [4]=>z );

Abschichten eines Stapels

• Mit Funktion array_pop() wird jeweils das letzte (oberste) Element entnommen und das Stapel-Array um 1 Element kleiner.
• Das abgeschichtete Element ist jeweils das zuletzt aufgeschichtete.
• Die Elemente werden beim Abschichten in der umgekehrten Reihenfolge wie beim Aufschichten zurückgewonnen.
• Die Schlüssel der restlichen Array-Elemente bleiben beim Abbau unverändert.
• Wenn der Stapel leer ist, dann gibt die Funktion array_pop() den Wert NULL zurück.
• Die aktuelle Höhe des Stapels kann man bei Bedarf mit Funktion count() ermitteln (gibt die Anzahl der Array-Elemente zurück).
$v = array_pop($sa);
// ergibt $v='z';
$z = count($sa);
// ergibt $z=2;
Weiteres Abschichten ergibt:
$v = array_pop($sa); // 'y'
$v = array_pop($sa); // 'x'
$v = array_pop($sa); // 'w'
$v = array_pop($sa); // 'v'
$v = array_pop($sa); // NULL

Abschichten in einer Schleife

Das Beispiel rechts zeigt, wie man einen Stack beliebiger Länge in einer einfachen while-Schleife komplett abschichten kann. Nach dem Ende der Schleife ist das Stapel-Array $sa leer.
Es ist typisch für die Verwendung eines Stacks, dass dieser am Ende seiner Verwendung zur Gänze geleert wird.
$sa = array('x','y','z');
while(count($sa)) {
$v = array_pop($sa);
print $v;
}
Sonderfälle
• Das 1. Beispiel zeigt, wie auf einen Stapel $xa Elemente unterschiedlicher Typen aufgeschichtet werden: Eine Zahl, ein String und ein Array.
• Das 2.Beispiel zeigt, wie man ein Element mit einem String-Schlüssel aufschichten kann. Das ist allerdings selten, weil es die Verwaltung des Arrays unnötig kompliziert. Die numerischen Schlüssel werden in diesem Fall unabhängig weitergezählt, d.h. für das Element mit dem String-Schlüssel wird kein numerischer Schlüssel ausgelassen.
Array-Elemente unterschiedlicher Typen:
array_push($xa,123,'xyz',array('a','b'));

Array-Elemente mit String-Schlüssel:
$xa['abc'] = 123;

Arrays als Warteschlange (Queue, FIFO)
Neue Elemente werden immer am Ende des Arrays angereiht. Die Entnahme von Elemente erfolgt stets vom Anfang des Arrays. Die Elemente verlassen den Speicher in der Reihenfolge ihrer Eingabe (First in, first out - FIFO).

Aufbau einer Warteschlange

• Zum Aufbau ('Anstellen') verwendet man mit array_push() die gleiche Funktion wie für einen Stapel.
• Alternativ kann man neue Array-Elemente ohne Angabe des Schlüssels zuweisen.
$qa = array();
$c = array_push($qa,'x','y');
$qa[] = 'z';
print_r($qa);
Ausgabe:
Array([0]=>x [1]=>y [2]=>z)

Abbau einer Warteschlange

• Mit Funktion array_shift() wird jeweils das erste Element entnommen und die Warteschlange um 1 Element kleiner.
• Das entnommene Element ist jeweils das zuerst angefügte.
• Die Elemente werden beim Abbau in der gleichen Reihenfolge wie beim Aufbau zurückgewonnen.
• Die arithmetischen Schlüssel der restlichen Array-Elemente werden neu nummeriert !   String-Schlüssel bleiben unverändert.
• Wenn die Warteschlange leer ist, dann gibt die Funktion array_shift() den Wert NULL zurück.
• Die aktuelle Länge der Warteschlange kann man bei Bedarf mit Funktion count() ermitteln (gibt die Anzahl der Array-Elemente zurück).
$v = array_shift($qa);
print_r($qa);
ergibt $v='x' und die Ausgabe
Array([0]=>y [1]=>z)
Weiterer Abbau ergibt
$v = array_shift(); // 'y'
$v = array_shift(); // 'z'
$v = array_shift(); // 'NULL
Ein häufig verwendeter Spezialfall ist ein ↓ Schieberegister (Warteschlange fixer Länge)

Schieberegister (Warteschlange fixer Länge)
Ein Schieberegister ist ein Warteschlangen-Speicher ↑ (Queue) fixer Länge: Die einzelnen Elemente verlassen den Speicher in der gleichen Reihenfolge wie bei ihrer Eingabe.
• Ein Förderband ist ein anschauliches Modell für ein Schieberegister. 		In jedem Arbeits-Schritt wird genau 1 Element aufgeladen und 1 Element abgeladen.
Jedes Element braucht daher zum Durchlaufen des Speichers die gleiche vorgegebene Anzahl von Schritten.

Erzeugung

Die Länge eines Schieberegisters (Anzahl der Array-Elemente) wird vorgegeben und während seiner Verwendung nicht geändert. Daher wird vor Beginn der Arbeit ein leeres Register der gewünschten Länge erzeugt.
• Funktion array_fill() erzeugt ein Array mit mehreren Elementen von gleichen Werten: Das 1.Argument bestimmt den ersten (numerischen) Schlüssel (normalerweise 0), das 2.Argument die Anzahl der Elemente, das 3.Argument den Wert der erzeugten Elemente.
Erzeugung eines leeren Förderbandes:
// 3 leere Elemente:
$qa = array(NULL,NULL,NULL);
// 100 leere Elemente:
$qa = array_fill(0,100,NULL);
Arbeitsschritt
Beim Weiterrücken eines Förderbandes wird in jedem Schritt ein neues Element (hier $qin ) angefügt und ein Element (hier $qout ) entnommen.
Die Länge des Förderband-Arrays bleibt dabei stets konstant.
Man kann mit dem Wert NULL auch leere Elemente anfügen bzw. mit Funktion is_null() prüfen, ob der Wert einer Variablen NULL ist.
Weiter-Rücken eines Förderbandes:
$qin = 'neu';
array_push($qa,$qin);
$qout = array_shift($qa);
print "qin=$qin, qout=$qout <br />\n";

Leeren

Zum Leeren eines Förderbandes fügt man so viele beliebige oder NULL-Elemente an, wie das Förderband lang ist. Dadurch werden alle noch enthaltenen Elemente abgeladen. 		Leeren eines Förderbandes:
for($i=0;$i<count($qa);$i++) {
array_push($qa,NULL);
$qout = array_shift($qa);
}

Sonderfall unshift()
Die Funktion array_unshift() ergänzt die Datenspeicher-Funktionen, wird jedoch in der Praxis kaum verwendet:
• Sie fügt Elemente am Anfang eines Arrays ein und verschiebt dabei alle vorhandenen Elemente um eine Position 'nach hinten'.
• Alle Argumente nach dem ersten werden als neue Elemente in das Array eingefügt.
• Vorhandene Text-(String)-Schlüssel werden nicht verändert.
Der Schlüssel des neuen Werts wird auf die Zahl0 gesetzt, alle anderen ganzzahligen Schlüssel werden neu nummeriert.
• Die Funktion gibt die Länge des Arrays nach dem Einfügen der neuen Elemente zurück.
$xa = array('r','s');
// ergibt Array([0]=>r [1]=>s)
$c = array_unshift($xa,'a');
// Array([0]=>a [1]=>r [2]=>s)

Zum Inhaltsverzeichnis Homepage von PS-Trainer   >   Entwicklung   >   PHP   >   Array   >   Speicher