ホームページ >バックエンド開発 >PHPチュートリアル >PHPマスター| PHP開発のデータ構造:スタックとキュー
<span><span><?php </span></span><span><span>class ReadingList </span></span><span><span>{ </span></span><span> <span>protected $stack; </span></span><span> <span>protected $limit; </span></span><span> </span><span> <span>public function __construct($limit = 10) { </span></span><span> <span>// initialize the stack </span></span><span> <span>$this->stack = array(); </span></span><span> <span>// stack can only contain this many items </span></span><span> <span>$this->limit = $limit; </span></span><span> <span>} </span></span><span> </span><span> <span>public function push($item) { </span></span><span> <span>// trap for stack overflow </span></span><span> <span>if (count($this->stack) < $this->limit) { </span></span><span> <span>// prepend item to the start of the array </span></span><span> <span>array_unshift($this->stack, $item); </span></span><span> <span>} else { </span></span><span> <span>throw new RunTimeException('Stack is full!'); </span></span><span> <span>} </span></span><span> <span>} </span></span><span> </span><span> <span>public function pop() { </span></span><span> <span>if ($this->isEmpty()) { </span></span><span> <span>// trap for stack underflow </span></span><span> <span>throw new RunTimeException('Stack is empty!'); </span></span><span> <span>} else { </span></span><span> <span>// pop item from the start of the array </span></span><span> <span>return array_shift($this->stack); </span></span><span> <span>} </span></span><span> <span>} </span></span><span> </span><span> <span>public function top() { </span></span><span> <span>return current($this->stack); </span></span><span> <span>} </span></span><span> </span><span> <span>public function isEmpty() { </span></span><span> <span>return empty($this->stack); </span></span><span> <span>} </span></span><span><span>}</span></span>この例では、array_unshift()とarray_shift()を使用して、array_push()とarray_pop()を使用したため、スタックの最初の要素が常に上部になりました。 array_push()とarray_pop()を使用してセマンティックの一貫性を維持できます。その場合、スタックのn番目の要素が上部になります。抽象データ型の全体的な目的は、実際の実装からのデータの操作を抽象化することであるため、どちらにも違いはありません。 スタックにいくつかのアイテムを追加しましょう:
<span><span><?php </span></span><span><span>$myBooks = new ReadingList(); </span></span><span> </span><span><span>$myBooks->push('A Dream of Spring'); </span></span><span><span>$myBooks->push('The Winds of Winter'); </span></span><span><span>$myBooks->push('A Dance with Dragons'); </span></span><span><span>$myBooks->push('A Feast for Crows'); </span></span><span><span>$myBooks->push('A Storm of Swords'); </span></span><span><span>$myBooks->push('A Clash of Kings'); </span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>スタックからいくつかのアイテムを削除するには:
<span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones' </span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings' </span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span>スタックの一番上にあるものを見てみましょう:
<span><span><?php </span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span>削除した場合はどうなりますか?
<span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Feast for Crows'</span></span>そして、新しいアイテムを追加したら?
<span><span><?php </span></span><span><span>$myBooks->push('The Armageddon Rag'); </span></span><span><span>echo $myBooks->pop(); // outputs 'The Armageddon Rag'</span></span>スタックが最後に最後に動作することがわかります。スタックに最後に追加されたものはすべて、最初に削除されます。スタックが空になるまでアイテムをポップし続けると、スタックアンダーフローランタイム例外が得られます。
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は、プログラムの実行コールスタックを前後に例外に示すスタックトレースを親切に提供しました!
<span><span><?php </span></span><span><span>class ReadingList extends SplStack </span></span><span><span>{ </span></span><span><span>}</span></span>Splstackクラスは、当初定義していたよりもいくつかの方法を実装しています。これは、Splstackが二重にリンクされたリストとして実装されているためです。これにより、トラバー可能なスタックを実装する能力が提供されます。 別の抽象データ型自体であるリンクされたリストは、特定のシーケンスを表すために使用されるオブジェクト(ノード)の線形コレクションであり、コレクション内の各ノードがコレクションの次のノードへのポインターを維持します。最も単純な形式では、リンクされたリストは次のようになります。
<span><span><?php </span></span><span><span>class ReadingList </span></span><span><span>{ </span></span><span> <span>protected $stack; </span></span><span> <span>protected $limit; </span></span><span> </span><span> <span>public function __construct($limit = 10) { </span></span><span> <span>// initialize the stack </span></span><span> <span>$this->stack = array(); </span></span><span> <span>// stack can only contain this many items </span></span><span> <span>$this->limit = $limit; </span></span><span> <span>} </span></span><span> </span><span> <span>public function push($item) { </span></span><span> <span>// trap for stack overflow </span></span><span> <span>if (count($this->stack) < $this->limit) { </span></span><span> <span>// prepend item to the start of the array </span></span><span> <span>array_unshift($this->stack, $item); </span></span><span> <span>} else { </span></span><span> <span>throw new RunTimeException('Stack is full!'); </span></span><span> <span>} </span></span><span> <span>} </span></span><span> </span><span> <span>public function pop() { </span></span><span> <span>if ($this->isEmpty()) { </span></span><span> <span>// trap for stack underflow </span></span><span> <span>throw new RunTimeException('Stack is empty!'); </span></span><span> <span>} else { </span></span><span> <span>// pop item from the start of the array </span></span><span> <span>return array_shift($this->stack); </span></span><span> <span>} </span></span><span> <span>} </span></span><span> </span><span> <span>public function top() { </span></span><span> <span>return current($this->stack); </span></span><span> <span>} </span></span><span> </span><span> <span>public function isEmpty() { </span></span><span> <span>return empty($this->stack); </span></span><span> <span>} </span></span><span><span>}</span></span>スタックを逆順序でトラバースするために、イテレータモードをFIFOに設定するだけです(最初は、最初の外出):
<span><span><?php </span></span><span><span>$myBooks = new ReadingList(); </span></span><span> </span><span><span>$myBooks->push('A Dream of Spring'); </span></span><span><span>$myBooks->push('The Winds of Winter'); </span></span><span><span>$myBooks->push('A Dance with Dragons'); </span></span><span><span>$myBooks->push('A Feast for Crows'); </span></span><span><span>$myBooks->push('A Storm of Swords'); </span></span><span><span>$myBooks->push('A Clash of Kings'); </span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>
<span><span><?php </span></span><span><span>class ReadingList </span></span><span><span>{ </span></span><span> <span>protected $stack; </span></span><span> <span>protected $limit; </span></span><span> </span><span> <span>public function __construct($limit = 10) { </span></span><span> <span>// initialize the stack </span></span><span> <span>$this->stack = array(); </span></span><span> <span>// stack can only contain this many items </span></span><span> <span>$this->limit = $limit; </span></span><span> <span>} </span></span><span> </span><span> <span>public function push($item) { </span></span><span> <span>// trap for stack overflow </span></span><span> <span>if (count($this->stack) < $this->limit) { </span></span><span> <span>// prepend item to the start of the array </span></span><span> <span>array_unshift($this->stack, $item); </span></span><span> <span>} else { </span></span><span> <span>throw new RunTimeException('Stack is full!'); </span></span><span> <span>} </span></span><span> <span>} </span></span><span> </span><span> <span>public function pop() { </span></span><span> <span>if ($this->isEmpty()) { </span></span><span> <span>// trap for stack underflow </span></span><span> <span>throw new RunTimeException('Stack is empty!'); </span></span><span> <span>} else { </span></span><span> <span>// pop item from the start of the array </span></span><span> <span>return array_shift($this->stack); </span></span><span> <span>} </span></span><span> <span>} </span></span><span> </span><span> <span>public function top() { </span></span><span> <span>return current($this->stack); </span></span><span> <span>} </span></span><span> </span><span> <span>public function isEmpty() { </span></span><span> <span>return empty($this->stack); </span></span><span> <span>} </span></span><span><span>}</span></span>spldoublylinkedlist また、ArrayAccessインターフェイスを実装して、Array要素としてsplqueueとSplstackの両方にアイテムを追加することもできます。
<span><span><?php </span></span><span><span>$myBooks = new ReadingList(); </span></span><span> </span><span><span>$myBooks->push('A Dream of Spring'); </span></span><span><span>$myBooks->push('The Winds of Winter'); </span></span><span><span>$myBooks->push('A Dance with Dragons'); </span></span><span><span>$myBooks->push('A Feast for Crows'); </span></span><span><span>$myBooks->push('A Storm of Swords'); </span></span><span><span>$myBooks->push('A Clash of Kings'); </span></span><span><span>$myBooks->push('A Game of Thrones');</span></span>キューの前面からアイテムを削除するには:
<span><span><?php </span></span><span><span>echo $myBooks->pop(); // outputs 'A Game of Thrones' </span></span><span><span>echo $myBooks->pop(); // outputs 'A Clash of Kings' </span></span><span><span>echo $myBooks->pop(); // outputs 'A Storm of Swords'</span></span>Enqueue()はPush()のエイリアスですが、Dequeue()はPOP()のエイリアスではないことに注意してください。 pop()は、キューのコンテキストで異なる意味と機能を持っています。ここでPOP()を使用した場合、FIFOルールに違反するキューの端(テール)からアイテムを削除します。 同様に、キューの正面(ヘッド)にあるものを確認するには、top()の代わりにbottom()を使用する必要があります。
<span><span><?php </span></span><span><span>echo $myBooks->top(); // outputs 'A Feast for Crows'</span></span>
適切なデータ構造を使用すると、PHPコードのパフォーマンスが大幅に向上する可能性があります。たとえば、多数の要素を保存して特定の要素を頻繁に検索する必要がある場合、ハッシュテーブルまたはセットを使用すると、配列を使用するよりもはるかに高速になります。同様に、両端で要素を頻繁に追加および削除する必要がある場合、デクを使用することは配列を使用するよりも効率的です。 PHPには、二重にリンクされたリストを実装するデータ構造があります。これにより、リストの両端に要素を一定の時間で追加、削除、アクセスできます。また、リスト内の要素を繰り返し、要素を並べ替えるための方法を提供します。 FIFO(最初、最初のアウト)原則。 PHPでは、Splqueueクラスを使用してキューを実装できます。 enqueue()メソッドを使用してキューに要素をenqueue()メソッドを使用してキューから離れたデキュー要素を使用できます。 🎜>スタックとキューはどちらもデータ構造のタイプですが、要素の追加および削除方法に重要な違いがあります。スタックはLIFO(最後の、最初のアウト)の原則に続きます。つまり、最後に追加された要素が最初に削除された要素です。一方、キューはFIFO(最初の、最初のアウト)の原則に従います。つまり、最初に追加された要素が削除される最初の要素です。
以上がPHPマスター| PHP開発のデータ構造:スタックとキューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。