スタックとキュー
スタックとキューは、データを効率的に管理する基本的なデータ構造です。
本ページでは、スタックの「LIFO」特性とキューの「FIFO」特性を中心に、操作方法や具体的な応用例を解説させていただきます。
目次 [ 非表示 表示 ]
スタックとは？
スタック（Stack）とは、データを順序よく管理する方法で、「LIFO（Last In, First Out）」という特性を持っています。これは、最後に追加されたデータが最初に取り出されるという意味です。例えば、本を積み重ねた場合、最後に積んだ本を最初に取り出すのと同じです。
スタックの基本操作
・プッシュ（Push）: データをスタックの上に追加する操作。
・ポップ（Pop）: スタックの上からデータを取り出す操作。
・ピーク（Peek）: スタックの上にあるデータを取り出さずに確認する操作。
スタックの例
ブラウザの履歴
ウェブブラウザの戻るボタンは、スタックを使って閲覧履歴を管理しています。最後に訪問したページから順に戻っていきます。
計算の処理
数式を計算する際、括弧の対応を確認するためにスタックが使われます。
キューとは？
キュー（Queue）は、データを順序よく管理する方法で、「FIFO（First In, First Out）」という特性を持っています。これは、最初に追加されたデータが最初に取り出されるという意味です。例えば、行列に並んだ人が順番にサービスを受けるのと同じです。
キューの基本操作
・エンキュー（Enqueue）: データをキューの末尾に追加する操作。
・デキュー（Dequeue）: キューの先頭からデータを取り出す操作。
・フロント（Front）: キューの先頭にあるデータを取り出さずに確認する操作。
キューの例
タスクの順序管理
コンピュータのタスクスケジューラーは、キューを使って実行するタスクの順序を管理しています。
プリントジョブの管理
複数の印刷要求を順番に処理するためにキューが使われます。
スタックとキューの比較
スタックとキューは、どちらもデータを順序よく管理しますが、その管理方法が異なります。スタックはLIFO（最後に入れたものが最初に出る）方式で、キューはFIFO（最初に入れたものが最初に出る）方式です。
スタックとキューの具体的な数値例
例えば、以下のデータがあるとします。
データ: A, B, C, D
スタックに追加すると
・プッシュ：A -> B -> C -> D
・ポップ：D -> C -> B -> A（この順に取り出される）
キューに追加すると
・エンキュー： A -> B -> C -> D
・デキュー： A -> B -> C -> D（この順に取り出される）
スタックとキューの具体的な応用例
スタックの応用例
関数の呼び出し管理
プログラムが関数を呼び出すとき、その情報をスタックに保存し、呼び出しが終了するとスタックから取り出します。例えば、関数Aが関数Bを呼び出し、さらに関数Cを呼び出す場合、スタックは次のようになります:
・プッシュ: A -> B -> C
・ポップ: C -> B -> A（この順に処理が終了する）
テキストエディタの操作履歴
テキストエディタでの操作履歴はスタックで管理されます。操作を元に戻す（Undo）際には、最後に行った操作から順に取り消されます。
キューの応用例
プリントスプーラー
プリントスプーラーは、印刷要求をキューに追加し、先に追加された要求から順に印刷します。例えば、A4用紙に10ページ印刷する要求と、写真を1枚印刷する要求がある場合、キューの順序で処理されます:
・エンキュー: 10ページ -> 写真
・デキュー: 10ページ -> 写真（この順に印刷される）
ネットワークパケットの送受信
ネットワークでデータを送受信する際、パケットはキューに追加され、順番に処理されます。例えば、ウェブサイトにアクセスするとき、リクエストパケットがキューに追加され、順次処理されます。
スタックとキューの性能
スタックとキューの操作は、どれも非常に効率的です。一般的に、スタックとキューの操作はどれもO(1)の時間計算量を持ちます。つまり、データの数に関係なく、一定時間で操作を完了できます。
スタックの操作時間
・プッシュ：O(1)
・ポップ：O(1)
・ピーク：O(1)
キューの操作時間
・エンキュー：O(1)
・デキュー：O(1)
・フロント：O(1)
実世界でのスタックとキューの応用
スタックとキューは、現実の様々なシステムやアプリケーションで使用されています。以下に具体的な例を示します。
スタックの実世界での応用例
ウェブブラウザの戻るボタン
ウェブブラウザで訪問したページをスタックに保存し、戻るボタンを押すと最後に訪問したページから順に戻ることができます。
計算機の処理
括弧を含む計算式を解く際、スタックを使用して括弧の対応を確認します。
キューの実世界での応用例
コールセンターの待ち行列
顧客からの電話を順番に処理するためにキューを使用します。最初に電話をかけた顧客が最初に対応されます。
フードデリバリーの注文管理
デリバリーサービスは、注文をキューに追加し、先に注文した顧客から順に料理を配達します。
まとめ
スタックとキューは、データを効率的に管理するための重要なツールです。スタックはLIFOの原則に基づき、最新のデータを最初に取り出すのに適しています。一方、キューはFIFOの原則に基づき、順番にデータを処理するのに適しています。
これらのデータ構造を理解し、適切に活用することで、プログラムやシステムの効率を大幅に向上させることができます。