実戦PHPデータ構造基盤のキュー
8333 ワード
キューとは
キューは、先進的な前提原則に従う別の線形データ構造です.キューには両端が操作可能で、一端がデキューされ、一端がデキューされます.この特徴はスタックとは異なり、スタックは一端だけで操作できます.入隊はいつも後端にあり、出隊は先端にある.
一般的な操作 enqueue->エンキュー dequeue->デキュー peek->戻りキューフロントエンド要素 isEmpty->空の PHP実現
まずQueInterfaceを定義します.
配列ベースのキュー実装を見ると
PHPの強力なarray構造のおかげで、キューの基本的な操作方法を簡単に書きました.やはり世界最高の言葉は名に恥じない.
機知に富んだ同級生はもう推測したかもしれませんが、私は前にキューインタフェースを定義しました.そのキューの実現はきっと上の1つだけではありません.チェーンテーブルベースの実装を見てみましょう.
中には以前のチェーンテーブルの実現に関連していて、詳細を知らない学生はここに行って見ることができます.
Splのキュー
強力なPHPにはキューインプリメンテーションが内蔵されており、上記の方法と同様に使用できます.
ゆうせんキュー
優先キューは特殊なキューであり、エンキューまたはデキューの順序は各ノードの重みに基づいています.
シーヶンスシーヶンス
優先キューは、秩序優先キューと無秩序優先キューに分けられます.順序優先キューには、逆順序または順序の2つのケースがあります.シーケンスでは,最大または最小の優先度のノードを迅速に見つけることができ,複雑度はO(1)である.ただし、各ノードの優先度をチェックして適切な位置に挿入するため、挿入にはより多くの時間がかかります.
無秩序シーケンス
無秩序シーケンスでは、新しいノードを挿入するときに、優先度に基づいて位置を決定する必要はありません.エンキュー時は通常のキューのように、キューの末尾に挿入します.しかし、最も優先度の高い要素を削除したい場合は、各ノードをスキャンして、最も優先度の高い要素を削除します.次に、チェーンテーブルに基づいて順序の優先キューを実装します.
リングキュー
ベクトル空間を十分に利用するために、「偽オーバーフロー」現象を克服する方法は、ベクトル空間を最初と最後に接する円環として想像し、このベクトルを循環ベクトルと呼ぶことである.格納されているキューをループキューと呼びます.リングキューも配列ですが、論理的に配列のヘッダとテールを接続し、ループキューを形成します.配列のテールがいっぱいになったとき、配列ヘッダが空であるかどうかを判断し、空ではなくデータを格納し続けます.
デュアルエンドキュー
これまで私たちが実現してきたキューは、チームの最後に入隊し、チームのリーダーが出てくる構造だ.特殊な場合、チームのリーダーでもチームの末尾でも入隊したり出隊したりすることを望んでいます.この構造を両端キューと呼びます.私たちが以前実現したチェーンテーブル構造に基づいて、私たちはこのような構造を簡単に実現することができます.
中には以前のチェーンテーブルの実現に関連していて、詳細を知らない学生はここに行って見ることができます.
まとめ
スタックとキューは私たちが最もよく使うデータ構造であり、他の複雑なデータ構造ではこの2つの抽象データ型の応用が見られます.次の章では,PHPデータ構造の再帰を引き続き学習するが,これは複雑な問題を単純化する一般的な考え方である.
特集シリーズ
PHP基礎データ構造特別テーマシリーズ目次アドレス:アドレスは主にPHP文法を用いて基礎データ構造とアルゴリズムを総括する.また、日常のPHP開発において無視しやすい基礎知識と現代のPHP開発における規範、配置、最適化に関するいくつかの実戦的な提案もあり、Javascript言語の特徴に対する深い研究もある.
キューは、先進的な前提原則に従う別の線形データ構造です.キューには両端が操作可能で、一端がデキューされ、一端がデキューされます.この特徴はスタックとは異なり、スタックは一端だけで操作できます.入隊はいつも後端にあり、出隊は先端にある.
一般的な操作
まずQueInterfaceを定義します.
interface QueueInterface
{
public function enqueue(string $item);
public function dequeue();
public function isEmpty();
public function peek();
}
配列ベースのキュー実装を見ると
class ArrQueue implements QueueInterface
{
private $queue;
private $limit;
public function __construct(int $limit = 0)
{
$this->limit = $limit;
$this->queue = [];
}
public function isEmpty()
{
return empty($this->queue);
}
public function dequeue()
{
if ($this->isEmpty()) {
throw new \UnderflowException('queue is empty');
} else {
array_shift($this->queue);
}
}
public function enqueue(string $item)
{
if (count($this->queue) >= $this->limit) {
throw new \OverflowException('queue is full');
} else {
array_unshift($this->queue, $item);
}
}
public function peek()
{
return current($this->queue);
}
}
PHPの強力なarray構造のおかげで、キューの基本的な操作方法を簡単に書きました.やはり世界最高の言葉は名に恥じない.
機知に富んだ同級生はもう推測したかもしれませんが、私は前にキューインタフェースを定義しました.そのキューの実現はきっと上の1つだけではありません.チェーンテーブルベースの実装を見てみましょう.
class LinkedListQueue implements QueueInterface
{
private $limit;
private $queue;
public function __construct(int $limit = 0)
{
$this->limit = $limit;
$this->queue = new LinkedList();
}
public function isEmpty()
{
return $this->queue->getSize() == 0;
}
public function peek()
{
return $this->queue->getNthNode(0)->data;
}
public function enqueue(string $item)
{
if ($this->queue->getSize() < $this->limit) {
$this->queue->insert($item);
} else {
throw new \OverflowException('queue is full');
}
}
public function dequeue()
{
if ($this->isEmpty()) {
throw new \UnderflowException('queue is empty');
} else {
$lastItem = $this->peek();
$this->queue->deleteFirst();
return $lastItem;
}
}
}
中には以前のチェーンテーブルの実現に関連していて、詳細を知らない学生はここに行って見ることができます.
Splのキュー
強力なPHPにはキューインプリメンテーションが内蔵されており、上記の方法と同様に使用できます.
class SqlQueue
{
private $splQueue;
public function __construct()
{
$this->splQueue = new \SplQueue();
}
public function enqueue(string $data = null)
{
$this->splQueue->enqueue($data);
}
public function dequeue()
{
return $this->splQueue->dequeue();
}
}
ゆうせんキュー
優先キューは特殊なキューであり、エンキューまたはデキューの順序は各ノードの重みに基づいています.
シーヶンスシーヶンス
優先キューは、秩序優先キューと無秩序優先キューに分けられます.順序優先キューには、逆順序または順序の2つのケースがあります.シーケンスでは,最大または最小の優先度のノードを迅速に見つけることができ,複雑度はO(1)である.ただし、各ノードの優先度をチェックして適切な位置に挿入するため、挿入にはより多くの時間がかかります.
無秩序シーケンス
無秩序シーケンスでは、新しいノードを挿入するときに、優先度に基づいて位置を決定する必要はありません.エンキュー時は通常のキューのように、キューの末尾に挿入します.しかし、最も優先度の高い要素を削除したい場合は、各ノードをスキャンして、最も優先度の高い要素を削除します.次に、チェーンテーブルに基づいて順序の優先キューを実装します.
class LinkedListPriorityQueue
{
private $limit;
private $queue;
public function __construct(int $limit = 0)
{
$this->limit = $limit;
$this->queue = new LinkedList();
}
public function enqueue(string $data = null, int $priority)
{
if ($this->queue->getSize() > $this->limit) {
throw new \OverflowException('Queue is full');
} else {
$this->queue->insert($data, $priority);
}
}
public function dequeue(): string
{
if ($this->isEmpty()) {
throw new \UnderflowException('Queue is empty');
} else {
$item = $this->peek();
$this->queue->deleteFirst();
return $item->data;
}
}
public function peek()
{
return $this->queue->getNthNode(0);
}
public function isEmpty()
{
return $this->queue->getSize() === 0;
}
}
リングキュー
ベクトル空間を十分に利用するために、「偽オーバーフロー」現象を克服する方法は、ベクトル空間を最初と最後に接する円環として想像し、このベクトルを循環ベクトルと呼ぶことである.格納されているキューをループキューと呼びます.リングキューも配列ですが、論理的に配列のヘッダとテールを接続し、ループキューを形成します.配列のテールがいっぱいになったとき、配列ヘッダが空であるかどうかを判断し、空ではなくデータを格納し続けます.
class CircularQueue implements QueueInterface
{
private $queue;
private $limit;
private $front = 0;
private $rear = 0;
public function __construct(int $limit = 0)
{
$this->limit = $limit;
$this->queue = [];
}
public function isEmpty()
{
return $this->front === $this->rear;
}
public function isFull()
{
$diff = $this->rear - $this->front;
if ($diff == -1 || $diff == ($this->limit - 1)) {
return true;
}
return false;
}
public function peek()
{
return $this->queue[$this->front];
}
public function dequeue()
{
if ($this->isEmpty()) {
throw new \UnderflowException('Queue is empty');
}
$item = $this->queue[$this->front];
$this->queue[$this->front] = null;
$this->front = ($this->front + 1) % $this->limit;
return $item;
}
public function enqueue(string $item)
{
if ($this->isFull()) {
throw new \OverflowException('Queue is full');
}
$this->queue[$this->rear] = $item;
$this->rear = ($this->rear + 1) % $this->limit;
}
}
デュアルエンドキュー
これまで私たちが実現してきたキューは、チームの最後に入隊し、チームのリーダーが出てくる構造だ.特殊な場合、チームのリーダーでもチームの末尾でも入隊したり出隊したりすることを望んでいます.この構造を両端キューと呼びます.私たちが以前実現したチェーンテーブル構造に基づいて、私たちはこのような構造を簡単に実現することができます.
class LinkedListDeQueue
{
private $limit = 0;
private $queue;
public function __construct(int $limit = 0)
{
$this->limit = $limit;
$this->queue = new \DataStructure\LinkedList\LinkedList();
}
public function dequeueFromFront(): string
{
if ($this->isEmpty()) {
throw new \UnderflowException('Queue is empty');
}
$item = $this->queue->getNthNode(0);
$this->queue->deleteFirst();
return $item->data;
}
public function dequeueFromBack(): string
{
if ($this->isEmpty()) {
throw new \UnderflowException('Queue is empty');
}
$item = $this->queue->getNthNode($this->queue->getSize() - 1);
$this->queue->deleteLast();
return $item->data;
}
public function isFull()
{
return $this->queue->getSize() >= $this->limit;
}
public function enqueueAtBack(string $data = null)
{
if ($this->isFull()) {
throw new \OverflowException('queue is full');
}
$this->queue->insert($data);
}
public function enqueueAtFront(string $data = null)
{
if ($this->isFull()) {
throw new \OverflowException('queue is full');
}
$this->queue->insertAtFirst($data);
}
public function isEmpty()
{
return $this->queue->getSize() === 0;
}
public function peekFront()
{
return $this->queue->getNthNode(0)->data;
}
public function peekBack()
{
return $this->queue->getNthNode($this->queue->getSize() - 1)->data;
}
}
中には以前のチェーンテーブルの実現に関連していて、詳細を知らない学生はここに行って見ることができます.
まとめ
スタックとキューは私たちが最もよく使うデータ構造であり、他の複雑なデータ構造ではこの2つの抽象データ型の応用が見られます.次の章では,PHPデータ構造の再帰を引き続き学習するが,これは複雑な問題を単純化する一般的な考え方である.
特集シリーズ
PHP基礎データ構造特別テーマシリーズ目次アドレス:アドレスは主にPHP文法を用いて基礎データ構造とアルゴリズムを総括する.また、日常のPHP開発において無視しやすい基礎知識と現代のPHP開発における規範、配置、最適化に関するいくつかの実戦的な提案もあり、Javascript言語の特徴に対する深い研究もある.