PHPマスター| PHP開発のデータ構造：スタックとキュー-PHPチュートリアル-php.cn

PHPマスター| PHP開発のデータ構造：スタックとキュー

データ構造、または抽象データ型 （ADT）は、それ自体で実行できる操作のコレクションによって定義され、それらの操作の効果に対する制約によって制限されるモデルです。それは、基礎となるデータに対して何ができるかとそれがどのように行われるかの間に壁を作成します。私たちのほとんどは、通常の日常的な使用法でスタックやキューに精通していますが、スーパーマーケットのキューや自動販売機はデータ構造に何の関係がありますか？調べてみましょう。この記事では、毎日の使用に起源がある2つの基本的な抽象データ型（スタックとキュー）を紹介します。

キーテイクアウト

抽象データ型（ADT）は、実行できる一連の操作によって定義されたモデルです。スタックとキューは、日常の使用に起源を持つ基本的なADTです。コンピューターサイエンスでは、スタックは最後のオブジェクトが最初の削除（LIFO）であるシーケンシャルコレクションであり、キューは先着順（FIFO）で動作します。
PHPのSPL拡張は、SPLSTACKクラスを含む一連の標準データ構造を提供します。二重にリンクされたリストとして実装されたSplstackクラスは、トラバー可能なスタックを実装する能力を提供します。 Splstackとして実装されたReadingListクラスは、スタックを前方（トップダウン）と後方（ボトムアップ）をトラバースできます。別の抽象データ型である
一般的に使用すると、スタックは通常、レイヤーで配置されるオブジェクトの山です。たとえば、机の上の本のスタック、または学校のカフェテリアのトレイのスタックです。コンピューターサイエンスの用語では、スタックは特定のプロパティを備えたシーケンシャルコレクションであり、スタックに最後に配置されたオブジェクトが最初のオブジェクトを削除します。このプロパティは、通常、最初の

lastと呼ばれます。キャンディー、チップ、タバコの自動販売機は、同じ原則で動作します。ラックにロードされた最後のアイテムは、最初に分配されます。抽象的に言えば、スタックは、すべての追加（「プッシュ」）および（「ポップ」）からの削除（「ポップ」）からの削除が、「トップ」として定義された一端に制限されるアイテムの線形リストです。）。スタックを定義する基本操作は次のとおりです。

init - スタックを作成します。プッシュ - スタックの上部にアイテムを追加します。

ポップ - スタックの上部に追加された最後のアイテムを削除します。

上 - スタックを削除せずにスタックの上部にあるアイテムを見てください。

isEmpty - スタックにこれ以上のアイテムが含まれていないかどうかを返してください。
スタックを実装して、最大容量を持つこともできます。スタックがいっぱいで、新しいエンティティを受け入れるのに十分なスロットが含まれていない場合、それはオーバーフローであると言われています。したがって、「スタックオーバーフロー」というフレーズ。同様に、空のスタックでポップ操作が試みられた場合、「スタックアンダーフロー」が発生します。スタックがLIFOプロパティと多くの基本操作、特にプッシュアンドポップで定義されていることを知って、配列を使用してスタックを簡単に実装できます。配列はすでにプッシュおよびポップ操作を提供しているためです。これが私たちのシンプルなスタックがどのように見えるかです：
<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { // initialize the stack $this->stack = array(); // stack can only contain this many items $this->limit = $limit; } public function push($item) { // trap for stack overflow if (count($this->stack) < $this->limit) { // prepend item to the start of the array array_unshift($this->stack, $item); } else { throw new RunTimeException('Stack is full!'); } } public function pop() { if ($this->isEmpty()) { // trap for stack underflow throw new RunTimeException('Stack is empty!'); } else { // pop item from the start of the array return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } }
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
この例では、array_unshift（）とarray_shift（）を使用して、array_push（）とarray_pop（）を使用したため、スタックの最初の要素が常に上部になりました。 array_push（）とarray_pop（）を使用してセマンティックの一貫性を維持できます。その場合、スタックのn番目の要素が上部になります。抽象データ型の全体的な目的は、実際の実装からのデータの操作を抽象化することであるため、どちらにも違いはありません。スタックにいくつかのアイテムを追加しましょう：
<?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones');
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
スタックからいくつかのアイテムを削除するには：
<?php echo $myBooks->pop(); // outputs 'A Game of Thrones' echo $myBooks->pop(); // outputs 'A Clash of Kings' echo $myBooks->pop(); // outputs 'A Storm of Swords'
ログイン後にコピー
ログイン後にコピー
スタックの一番上にあるものを見てみましょう：
<?php echo $myBooks->top(); // outputs 'A Feast for Crows'
ログイン後にコピー
ログイン後にコピー
削除した場合はどうなりますか？
<?php echo $myBooks->pop(); // outputs 'A Feast for Crows'
ログイン後にコピー
そして、新しいアイテムを追加したら？
<?php $myBooks->push('The Armageddon Rag'); echo $myBooks->pop(); // outputs 'The Armageddon Rag'
ログイン後にコピー
スタックが最後に最後に動作することがわかります。スタックに最後に追加されたものはすべて、最初に削除されます。スタックが空になるまでアイテムをポップし続けると、スタックアンダーフローランタイム例外が得られます。
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
ログイン後にコピー
ああ、こんにちは…PHPは、プログラムの実行コールスタックを前後に例外に示すスタックトレースを親切に提供しました！
splstack
SPL拡張は、SPLSTACKクラス（PHP5> = 5.3.0）を含む一連の標準データ構造を提供します。同じオブジェクトを実装できますが、以下のようにSPLSTACKを使用してはるかに激しく実装できます。
<?php class ReadingList extends SplStack { }
ログイン後にコピー
Splstackクラスは、当初定義していたよりもいくつかの方法を実装しています。これは、Splstackが二重にリンクされたリストとして実装されているためです。これにより、トラバー可能なスタックを実装する能力が提供されます。別の抽象データ型自体であるリンクされたリストは、特定のシーケンスを表すために使用されるオブジェクト（ノード）の線形コレクションであり、コレクション内の各ノードがコレクションの次のノードへのポインターを維持します。最も単純な形式では、リンクされたリストは次のようになります。

二重にリンクされたリストには、各ノードには2つのポインターがあり、それぞれがコレクションの次のノードと以前のノードを指しています。このタイプのデータ構造により、両方向に横断が可能になります。

クロス（x）でマークされたノードは、nullまたはセンチネルノードを示します。これは、トラバーサルパス（つまり、パスターミネーター）の端を指定します。 ReadingListはSPLSTACKとして実装されているため、スタックを前方（トップダウン）および後方（ボトムアップ）をトラバースできます。 SplstackのデフォルトのトラバーサルモードはLIFOです。
<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { // initialize the stack $this->stack = array(); // stack can only contain this many items $this->limit = $limit; } public function push($item) { // trap for stack overflow if (count($this->stack) < $this->limit) { // prepend item to the start of the array array_unshift($this->stack, $item); } else { throw new RunTimeException('Stack is full!'); } } public function pop() { if ($this->isEmpty()) { // trap for stack underflow throw new RunTimeException('Stack is empty!'); } else { // pop item from the start of the array return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } }
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
スタックを逆順序でトラバースするために、イテレータモードをFIFOに設定するだけです（最初は、最初の外出）：
<?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones');
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー

キュー
スーパーマーケットのチェックアウトで列に並んだことがあるなら、最初の人が最初に提供されることがわかります。コンピューターの用語では、キューは別の抽象データ型であり、最初のベースまたはFIFOで最初に動作します。在庫は、特にそのようなアイテムが腐りやすい性質の場合、FIFOベースでも管理されています。キューを定義する基本操作は次のとおりです。
init - キューを作成します。

enqueue - キューの「終了」（尾）にアイテムを追加します。
dequeue - キューの「フロント」（ヘッド）からアイテムを削除します。
isEmpty - キューにこれ以上のアイテムが含まれていないかどうかを返してください。

Splqueueは二重にリンクされたリストを使用して実装されているため、このコンテキストではTOPとPOPの意味的な意味が逆になります。読み取りリストのクラスをキューとして再定義しましょう。
<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { // initialize the stack $this->stack = array(); // stack can only contain this many items $this->limit = $limit; } public function push($item) { // trap for stack overflow if (count($this->stack) < $this->limit) { // prepend item to the start of the array array_unshift($this->stack, $item); } else { throw new RunTimeException('Stack is full!'); } } public function pop() { if ($this->isEmpty()) { // trap for stack underflow throw new RunTimeException('Stack is empty!'); } else { // pop item from the start of the array return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } }
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
spldoublylinkedlist また、ArrayAccessインターフェイスを実装して、Array要素としてsplqueueとSplstackの両方にアイテムを追加することもできます。
<?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones');
ログイン後にコピー
ログイン後にコピー
ログイン後にコピー
キューの前面からアイテムを削除するには：
<?php echo $myBooks->pop(); // outputs 'A Game of Thrones' echo $myBooks->pop(); // outputs 'A Clash of Kings' echo $myBooks->pop(); // outputs 'A Storm of Swords'
ログイン後にコピー
ログイン後にコピー
Enqueue（）はPush（）のエイリアスですが、Dequeue（）はPOP（）のエイリアスではないことに注意してください。 pop（）は、キューのコンテキストで異なる意味と機能を持っています。ここでPOP（）を使用した場合、FIFOルールに違反するキューの端（テール）からアイテムを削除します。同様に、キューの正面（ヘッド）にあるものを確認するには、top（）の代わりにbottom（）を使用する必要があります。
<?php echo $myBooks->top(); // outputs 'A Feast for Crows'
ログイン後にコピー
ログイン後にコピー

要約
この記事では、スタックとキューの抽象データ型がプログラミングでどのように使用されているかを見てきました。これらのデータ構造は抽象的であり、それ自体で実行できる操作によって定義されているため、その実装と基礎となるデータの間に壁が作成されます。これらの構造は、そのような操作の効果によっても制約されています。スタックの上部からアイテムを追加または削除することしかできず、キューの前面からアイテムのみを削除したり、キューの背面にアイテムを追加したりできます。 Alexandre DulaunoyによるFlickr による画像 PHPデータ構造に関するよくある質問（FAQ）

PHPのさまざまなタイプのデータ構造は何ですか？

PHPは、配列、オブジェクト、リソースなど、いくつかのタイプのデータ構造をサポートしています。配列は、PHPで最も一般的で汎用性の高いデータ構造です。他の配列を含むあらゆる種類のデータを保持することができ、インデックス化または連想を整えることができます。 PHPのオブジェクトはクラスのインスタンスであり、プロパティとメソッドを持つことができます。リソースは、データベース接続などの外部リソースへの参照を保持する特別な変数です。最後に、最初に）原則。 PHPでは、Splstackクラスを使用してスタックを実装できます。 push（）メソッドを使用して要素をスタックに押し込み、POP（）メソッドを使用してスタックからPOP要素をPOP要素を押します。 PHPの配列とオブジェクトはどちらもデータ構造のタイプですが、いくつかの重要な違いがあります。配列は値の単純なリストであり、オブジェクトはクラスのインスタンスであり、プロパティとメソッドを持つことができます。アレイはインデックス作成または連想を整えることができますが、オブジェクトは常に文字列キーを使用します。アレイはより汎用性が高く、使いやすいですが、オブジェクトはより多くの構造とカプセル化を提供します。
データ構造を使用してPHPコードのパフォーマンスを改善するにはどうすればよいですか？

適切なデータ構造を使用すると、PHPコードのパフォーマンスが大幅に向上する可能性があります。たとえば、多数の要素を保存して特定の要素を頻繁に検索する必要がある場合、ハッシュテーブルまたはセットを使用すると、配列を使用するよりもはるかに高速になります。同様に、両端で要素を頻繁に追加および削除する必要がある場合、デクを使用することは配列を使用するよりも効率的です。 PHPには、二重にリンクされたリストを実装するデータ構造があります。これにより、リストの両端に要素を一定の時間で追加、削除、アクセスできます。また、リスト内の要素を繰り返し、要素を並べ替えるための方法を提供します。 FIFO（最初、最初のアウト）原則。 PHPでは、Splqueueクラスを使用してキューを実装できます。 enqueue（）メソッドを使用してキューに要素をenqueue（）メソッドを使用してキューから離れたデキュー要素を使用できます。 🎜>スタックとキューはどちらもデータ構造のタイプですが、要素の追加および削除方法に重要な違いがあります。スタックはLIFO（最後の、最初のアウト）の原則に続きます。つまり、最後に追加された要素が最初に削除された要素です。一方、キューはFIFO（最初の、最初のアウト）の原則に従います。つまり、最初に追加された要素が削除される最初の要素です。

PHPのSplheapクラスは、ヒープを実装するデータ構造です。ヒープは、各親ノードが子ノード以下のバイナリツリーの一種です。 Splheapクラスを使用して、MinheapまたはMax Heapを作成し、ヒープ内の要素を追加、削除、アクセスできます。 >
PHPでデータ構造を使用すると、いくつかの利点があります。より効率的で論理的な方法でデータを整理するのに役立ちます。これにより、コードが理解し、維持されやすくなります。また、特に大量のデータまたは複雑な操作を扱う場合、コードのパフォーマンスを改善することもできます。各ノードには、左の子供と右の子供と呼ばれる最大2人の子供がいるデータ構造の。 PHPでは、ノードと左右の子供の値のプロパティを持つクラスを使用して、バイナリツリーを実装できます。その後、メソッドを使用して、ツリー内のノードを追加、削除、検索できます。

以上がPHPマスター| PHP開発のデータ構造：スタックとキューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。