スタックとキュー

スタックとは、リスト項目の ** と削除がトップと呼ばれる一端でのみ可能な順序付きリストのことです。スタックはLIFO（Last-in-First-Out）データ構造であり、キューはリスト項目の**を一方の端（バックエンドと呼ぶ）で、項目の削除をもう一方の端（フロントエンドと呼ぶ）で行う順序付きリストであると考えられている。この**と削除のメカニズムにより、キューはFIFO（First In First Out）データ構造になります。

スタックとは何ですか？

前述したように、スタックはトップと呼ばれる末端からしか要素が追加・削除されないデータ構造である。プッシュ操作はスタックの先頭に新しい要素を追加し、ポップ操作はスタックの先頭から要素を削除する操作である。スタックが満杯の場合、プッシュ操作時にスタックオーバーフローとして扱われる。既に空のスタックに対してpop操作を行った場合、スタックのオーバーフローとして扱われる。スタックに対して実行できる操作の数は非常に少ないため、制限されたデータ構造と考えられている。さらに、pushとpopの操作の定義から、最後に追加された要素が最初にスタックから削除されることは明らかである。したがって、スタックは後入れ先出しのデータ構造であると考えられる。

キューとは何ですか？

キューでは、要素はキューの後ろから追加され、キューの前から削除される。最初に追加された要素は最初にキューから削除されるので、FIFOオーダーを維持することができます。要素を異なる順番で追加・削除するため、キューはチェックアウト・ラインの概念を表しています。キューがサポートする一般的な操作は、イン・キュー操作とアウト・キュー操作である。キューイング操作は、要素をキューの後ろに追加する操作で、アンキューイング操作は、要素をキューの前から取り除く操作である。一般に、キューに追加できる要素数には、メモリ制限以外に制限はない。

スタックとキューの違いは何ですか？

スタックとキューはどちらも順序付きリストですが、いくつかの重要な違いがあります。スタックでは、項目の追加や削除は一方の端（トップと呼ぶ）からしか行えないが、キューでは、項目の追加は一方の端（バックエンドと呼ぶ）から、項目の削除はもう一方の端（フロントエンドと呼ぶ）から行うことができる。スタックでは、最後に追加されたアイテムが最初にスタックから取り除かれます。したがって、スタックは後入れ先出しのデータ構造であると考えられている。待ち行列では、最初に追加された項目が最初に待ち行列から削除されます。したがって、キューはFIFOデータ構造とみなされる。

関連記事