キュー（Queue）の基本概念

キューは先入先出（FIFO: First In, First Out）の原則に従う線形データ構造です。データの追加（エンキュー）は末尾でのみ行われ、データの削除（デキュー）は先頭でのみ行われます。PHPの組み込み関数を使用する場合、array_push() または配列の代入で末尾に要素を追加し、array_shift() で先頭の要素を削除することでキューの動作を再現できます。

配列を用いたキューの実装

PHPの配列は動的にサイズが変更されるため、キューの実装に非常に適しています。以下のコードは、配列を利用したキューのクラス実装です。型宣言と例外処理を用いて、より堅牢な設計にしています。

<?php

class ArrayQueue {
    private array $items = [];

    public function size(): int {
        return count($this->items);
    }

    public function isEmpty(): bool {
        return $this->size() === 0;
    }

    public function enqueue(mixed $value): void {
        $this->items[] = $value;
    }

    public function dequeue(): mixed {
        if ($this->isEmpty()) {
            throw new UnderflowException("キューが空です");
        }
        return array_shift($this->items);
    }
    
    public function peek(): mixed {
        if ($this->isEmpty()) {
            throw new UnderflowException("キューが空です");
        }
        return $this->items[0];
    }
}

連結リストを用いたキューの実装

連結リストを用いることで、メモリを動的に確保するキューを構築できます。効率的な操作のため、先頭（ヘッド）と末尾（テール）の両方のポインタを維持し、エンキューとデキューをO(1)の計算量で実行できるように設計します。

<?php

class QueueNode {
    public function __construct(
        public mixed $value,
        public ?QueueNode $next = null
    ) {}
}

class LinkedQueue {
    private ?QueueNode $head = null;
    private ?QueueNode $tail = null;
    private int $count = 0;

    public function isEmpty(): bool {
        return $this->count === 0;
    }

    public function enqueue(mixed $value): void {
        $newNode = new QueueNode($value);
        if ($this->tail === null) {
            $this->head = $this->tail = $newNode;
        } else {
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
        $this->count++;
    }

    public function dequeue(): mixed {
        if ($this->isEmpty()) {
            throw new UnderflowException("キューが空です");
        }
        $value = $this->head->value;
        $this->head = $this->head->next;
        if ($this->head === null) {
            $this->tail = null;
        }
        $this->count--;
        return $value;
    }
}

スタック（Stack）の基本概念

スタックは後入先出（LIFO: Last In, First Out）の原則に従うデータ構造です。データの追加（プッシュ）と削除（ポップ）は、常に同じ端（スタックのトップ）で行われます。PHPでは、array_push() で要素を追加し、array_pop() で末尾の要素を削除することでスタックを実現できます。

配列を用いたスタックの実装

配列を用いたスタックは、PHPの動的配列の特性を活かしてシンプルかつ効率的に実装できます。

<?php

class ArrayStack {
    private array $elements = [];

    public function size(): int {
        return count($this->elements);
    }

    public function isEmpty(): bool {
        return $this->size() === 0;
    }

    public function push(mixed $value): void {
        $this->elements[] = $value;
    }

    public function pop(): mixed {
        if ($this->isEmpty()) {
            throw new UnderflowException("スタックが空です");
        }
        return array_pop($this->elements);
    }

    public function peek(): mixed {
        if ($this->isEmpty()) {
            throw new UnderflowException("スタックが空です");
        }
        return $this->elements[$this->size() - 1];
    }
}

連結リストを用いたスタックの実装

連結リストでスタックを実装する場合、リストの先頭をスタックのトップとして扱います。これにより、ノードの走査を不要にし、プッシュとポップの操作をO(1)の計算量で完了させることができます。

<?php

class StackNode {
    public function __construct(
        public mixed $value,
        public ?StackNode $next = null
    ) {}
}

class LinkedStack {
    private ?StackNode $top = null;
    private int $count = 0;

    public function isEmpty(): bool {
        return $this->count === 0;
    }

    public function push(mixed $value): void {
        $newNode = new StackNode($value, $this->top);
        $this->top = $newNode;
        $this->count++;
    }

    public function pop(): mixed {
        if ($this->isEmpty()) {
            throw new UnderflowException("スタックが空です");
        }
        $value = $this->top->value;
        $this->top = $this->top->next;
        $this->count--;
        return $value;
    }
}