Ds\Deque — Klasse · PHP-Referenz

Signatur

class Ds\Deque implements Ds\Sequence

Beschreibung

Ds\Deque ist eine Datenstruktur aus der php-ds-Erweiterung, die Elemente in einem kontinuierlichen Puffer speichert und schnellen Zugriff an beiden Enden (Anfang und Ende) erlaubt. Im Gegensatz zu einem normalen Array sind push()-, pop()-, shift()- und unshift()-Operationen alle in O(1) möglich, ohne dabei teures Re-Indizieren zu benötigen.

Wann sinnvoll? Immer dann, wenn Elemente häufig an beiden Enden einer Liste eingefügt oder entfernt werden müssen – etwa bei Aufgaben-Pipelines, Sliding-Window-Algorithmen oder BFS-Traversierungen. Gegenüber SplDoublyLinkedList bietet Ds\Deque durch die zusammenhängende Speicherablage eine bessere Cache-Lokalität.

Ds\Deque implementiert das Interface Ds\Sequence, das wiederum Ds\Collection, Countable, IteratorAggregate und ArrayAccess umfasst. Indexbasierter Zugriff ($deque[0]) ist daher möglich und läuft in O(1).

Speicherverwaltung: Die interne Kapazität wächst automatisch auf das Doppelte, sobald der Puffer voll ist, und schrumpft, wenn nur noch ein Viertel belegt ist – analog zu Ds\Vector. Die Mindestkapazität beträgt 8 Elemente.

Parameter

Name	Typ	Default	Beschreibung
$values	iterable	[]	Optionaler iterierbarer Startwert (Array oder `Traversable`), mit dem die Deque initialisiert wird.

Beispiele

Grundlegende Deque-Operationen an beiden Enden

<?php
require 'vendor/autoload.php'; // oder ds-Extension direkt laden

$deque = new Ds\Deque([2, 3, 4]);

$deque->unshift(1);   // Am Anfang einfügen
$deque->push(5);      // Am Ende einfügen

echo $deque->first(); // 1
echo PHP_EOL;
echo $deque->last();  // 5
echo PHP_EOL;

$deque->shift();      // Erstes Element entfernen
$deque->pop();        // Letztes Element entfernen

print_r($deque->toArray());

1 5 Array ( [0] => 2 [1] => 3 [2] => 4 )

BFS-Traversierung mit Ds\Deque

<?php
require 'vendor/autoload.php';

// Einfacher Baum als verschachteltes Array
$tree = [
    'value' => 'A',
    'children' => [
        ['value' => 'B', 'children' => [['value' => 'D', 'children' => []]]],
        ['value' => 'C', 'children' => [['value' => 'E', 'children' => []]]],
    ],
];

$queue = new Ds\Deque([$tree]);
$visited = [];

while (!$queue->isEmpty()) {
    $node = $queue->shift();
    $visited[] = $node['value'];
    foreach ($node['children'] as $child) {
        $queue->push($child);
    }
}

echo implode(' -> ', $visited);

A -> B -> C -> D -> E

Kapazität und Speicher explizit steuern

<?php
require 'vendor/autoload.php';

$deque = new Ds\Deque();
$deque->allocate(100); // Mindest-Kapazität reservieren

for ($i = 0; $i < 50; $i++) {
    $deque->push($i);
}

echo 'Kapazität: ' . $deque->capacity() . PHP_EOL;
echo 'Anzahl:    ' . count($deque) . PHP_EOL;

$deque->trim(); // Kapazität auf tatsächliche Größe reduzieren
echo 'Kapazität nach trim: ' . $deque->capacity() . PHP_EOL;

Kapazität: 100 Anzahl: 50 Kapazität nach trim: 64

// Wichtig · Fallstricke

Erweiterung erforderlich: Ds\Deque ist Teil der PECL-Erweiterung ds (alternativ via Composer: composer require php-ds/php-ds). Sie ist nicht im PHP-Standard-Kern enthalten.

Unterschied zu Ds\Vector: Während Ds\Vector nur am Ende effizient ist (unshift() kostet O(n)), sind bei Ds\Deque beide Enden in O(1) bedienbar – dafür ist der indexbasierte Zugriff intern minimal aufwändiger (Modulo-Arithmetik).

Nicht serialisierbar: Ds\Deque unterstützt serialize()/unserialize() nicht nativ; für Persistenz sollte toArray() genutzt werden.

Siehe auch

Ds\Vector Ds\Sequence Ds\Queue Ds\Stack SplDoublyLinkedList SplQueue