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

ホームページ

バックエンド開発

PHPチュートリアル

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

Christopher Nolan

Feb 23, 2025 am 11:35 AM

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) 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) 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) 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 サイトの他の関連記事を参照してください。

声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

セッションロックの概念を説明します。Apr 29, 2025 am 12:39 AM

Sessionlockingisatechniqueusedtoensureauser'ssessionremainsexclusivetooneuseratatime.Itiscrucialforpreventingdatacorruptionandsecuritybreachesinmulti-userapplications.Sessionlockingisimplementedusingserver-sidelockingmechanisms,suchasReentrantLockinJ

PHPセッションの選択肢はありますか？Apr 29, 2025 am 12:36 AM

PHPセッションの代替品には、Cookie、トークンベースの認証、データベースベースのセッション、Redis/Memcachedが含まれます。 1.Cookiesは、クライアントにデータを保存することによりセッションを管理します。 2.トークンベースの認証はトークンを使用してユーザーを検証します。これは非常に安全ですが、追加のロジックが必要です。 3.Databaseベースのセッションは、データベースにデータを保存します。これは、スケーラビリティが良好ですが、パフォーマンスに影響を与える可能性があります。 4. Redis/Memcachedは分散キャッシュを使用してパフォーマンスとスケーラビリティを向上させますが、追加のマッチングが必要です

PHPのコンテキストで「セッションハイジャック」という用語を定義します。Apr 29, 2025 am 12:33 AM

SessionHijackingとは、ユーザーのSessionIDを取得してユーザーになりすましている攻撃者を指します。予防方法には、次のものが含まれます。1）HTTPSを使用した通信の暗号化。 2）SessionIDのソースの検証。 3）安全なSessionID生成アルゴリズムの使用。 4）SessionIDを定期的に更新します。

PHPの完全な形式は何ですか？Apr 28, 2025 pm 04:58 PM

この記事では、PHPについて説明し、その完全なフォーム、Web開発での主要な使用、PythonとJavaとの比較、および初心者の学習のしやすさについて説明します。

PHPはフォームデータをどのように処理しますか？Apr 28, 2025 pm 04:57 PM

PHPは、$ \ _ postおよび$ \ _を使用してフォームデータを処理し、検証、消毒、安全なデータベースインタラクションを通じてセキュリティを確保します。

PHPとASP.NETの違いは何ですか？Apr 28, 2025 pm 04:56 PM

この記事では、PHPとASP.NETを比較して、大規模なWebアプリケーション、パフォーマンスの違い、セキュリティ機能への適合性に焦点を当てています。どちらも大規模なプロジェクトでは実行可能ですが、PHPはオープンソースであり、プラットフォームに依存しませんが、ASP.NET、

PHPはケースに敏感な言語ですか？Apr 28, 2025 pm 04:55 PM

PHPの症例感度は変化します：関数は鈍感であり、変数とクラスは感度があります。ベストプラクティスには、一貫した命名と、比較のためにケース非感受性関数を使用することが含まれます。

PHPでページをリダイレクトするにはどうすればよいですか？Apr 28, 2025 pm 04:54 PM

この記事では、PHPのページリダイレクトのさまざまな方法について説明し、ヘッダー（）関数に焦点を当て、「すでに送信されているヘッダー」エラーなどの一般的な問題に対処します。

See all articles

ホットAIツール

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

脱衣画像を無料で

Clothoff.io

AI衣類リムーバー

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

ドリームウィーバー CS6

ビジュアル Web 開発ツール

WebStorm Mac版

便利なJavaScript開発ツール

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

DVWA

Damn Vulnerable Web App (DVWA) は、非常に脆弱な PHP/MySQL Web アプリケーションです。その主な目的は、セキュリティ専門家が法的環境でスキルとツールをテストするのに役立ち、Web 開発者が Web アプリケーションを保護するプロセスをより深く理解できるようにし、教師/生徒が教室環境で Web アプリケーションを教え/学習できるようにすることです。安全。 DVWA の目標は、シンプルでわかりやすいインターフェイスを通じて、さまざまな難易度で最も一般的な Web 脆弱性のいくつかを実践することです。このソフトウェアは、