データ構造 Designveloper

なぜスタックとキューなのか

配列とは異なり、スタックとキューではランダムアクセス操作がありません (「インデックス」によって要素に直接アクセスすることはできません)。 通常、push(), pop(), peek(), enqueue(), dequeue() のように、データ構造の先頭または末尾の要素のみを扱うメソッドやアクションは少なくなっています。

But…

Question: データ構造の最初または最後の要素にしかアクセスできないので、これはとても制限的に聞こえます。 なぜ、このようなものを使用したいのでしょうか。 なぜ、より柔軟性のある配列を使用しないのですか? スタックとキューは通常、低レベルのもの (配列またはリンクされたリスト) の上に構築された「高レベルのデータ構造」であり、それに対してできる操作を制限するために使用されます。

データ構造にこの制限された能力を持つことは、効率的な正しい操作のみを実行するこのデータ構造を使用する人を制御できるため、利点となるのです。 たとえば、誰かがリストの真ん中にランダムに要素を挿入して、いくつかの不変量を台無しにした場合、心配する必要はありません。 このおかげで、多くの問題から解放されました。

スタックとは何か

スタックは一端が線形なデータ構造であり、プッシュとポップという 2 つの主要操作により現実世界のスタックをモデル化しています。 スタックの最上位にあるブロックを指すトップ ポインタがあります。 これは、スタック内の要素は常に取り除かれ、一番上に追加されるからです。 この動作は一般に LIFO (Last In First Out) として知られています。

スタック操作

以下は、スタックで実行できる 2 つの基本操作です。

• Push 関数です。 スタックの先頭に要素を追加する
• Pop 関数。

スタックの基本操作の視覚化

さらに、スタックの状態を確認するために、以下の追加関数が用意されています。 スタックの先頭の要素を削除せずに返す

全てはスタックの一番上で動作します。 トップ以外にはアクセスできない。

Complexity analysis

次の複雑性の表は、リンクリストを使ってスタックを実装したと仮定しています

Stacks applications

スタックはいつ、どこで使われるか？

• 式の評価に使用できる（例：数学式を解析し評価するための分水嶺アルゴリズム）。

• 書いたテキストを元に戻すためにテキストエディタのアンドゥ機構で使用される (Mac OS では Cmd + Z、Windows では Ctrl + Z)
• 後方に移動するためにブラウザで使用され グラフの深さ方向の第一探索 (DFS) に使用できる
• 前の関数呼び出しを追跡して再帰をサポートするために裏で使用される

キューとは何ですか?

キューは線形データ構造でもあり、enqueue（「キューに入る」と考えることができる）とdequeue（「キューから削除」とも考えられる）という二つの主要操作をもって、現実世界のキューをモデル化するものである。 この構造は、現実世界の待ち行列（queue）に似ていることから、「キュー」と名付けられています。

すべてのキューにはフロントエンドとバックエンド（「リア」と呼ばれることもある）があります。

キューは FIFO (First In First Out – 最初に置かれた要素は最初にアクセスすることができる) 構造で、多くのプログラミング言語で一般的に見かけることができます。

キューの操作

キューに対して実行できる3つの基本的な操作を以下に示します。 キューの末尾に要素を追加する

Complexity analysis

画像でわかるように、enqueueとdequeueの操作には一定時間O(1)がかかる。 しかし、ある要素がキュー内に含まれているかどうかのチェックは、潜在的にすべての要素をスキャンする必要があるため、線形時間O(n)となる。

また、内部的には要素の削除（dequeuingではない）もある。

Queue applications

• Multithreading でスレッドを管理するために使用される。
• 最近追加されたx個の要素を効率的に追跡するために使用できる
• Webサーバーリクエスト管理で先着順を望む場合。 例えば 任意の時点で、私たちの Web サーバーは同時に最大 50 人までしか提供できません。

短時間に 70 件のリクエストが来た場合、そのすべてを処理することは不可能でしょう。 そこで、ウェブサーバはキューから 50 リクエストだけをポップし、 残りの 20 リクエストは保留にします。 Web サーバはリクエストの処理を終えると、次のリクエストを待ち行列から外し、 待ち行列が空になるまでそれを続けます。

• Breadth-first search (BFS) graph traversal
• queuing systems (e.g.: priority queues) の実装に使用されるもの。 プリンタは、一度に1つのシングルリクエストにのみ対応できます。 そのため、プリンタがビジー状態のときに他の要求が来ても、プリンタを管理するプログラムはそれらの要求を拒否せず、実行待ちのキューに入れる。 最初のリクエストが最初に処理されます（FIFO）。

この記事で、スタックとキューについてイメージしていただけたでしょうか。

また、次のような記事もあります。

• ウェブ アプリケーション アーキテクチャとは
• データ構造とその応用
• ビッグ O 記法とは