こんにちは。Kaneyasuです。
年が明け、また情報処理技術者の季節が近づいてきましたね。
今日は午前の問題にたまに出てくるキューとスタックについての記事を書いてみました。
本記事のターゲット
本記事はプログラミングの初心者の方に向けて記述したものです
プログラミングしているとしばしば出てくるキューとスタックについて、考え方を述べています。
概念を述べており、実際のコードは記述していません。
教科書の言葉だけではいまいちピンとこない時に、理解を深めるために役立つと幸いです。
キューとスタックとは
キュー（Queue）とスタック（Stack）は、コンピュータサイエンスにおける2つの基本的なデータ構造です。
これらはデータを格納し、取り出す方法が異なる特徴を持っています。
どちらも、データの格納と取り出しに明確なルールが設けられており、いちいち格納位置・取り出し位置を指定しないのが特徴です。
キュー(First-In-First-Out)
キューは先入先出し方と呼ばれるデータ格納方式です。
First-In-First-Out、略してFIFOと言われます。
現実世界で言うと、病院の受付番号などがこれにあたります。
病院に行って受付すると、受付番号をもらいます。
もらった受付番号順に診察は行われます。
この時、受付番号を発行せずに、来た人をいきなり診察するような仕組みだと、待っている人は自分はいつ診察されるのかわからず混乱が生じます。
診察が一瞬で終わるならいきなり診察でも対応し切れるかもしれませんが、診察は時間が読みにくいので受付番号のような仕組みが必要になります。
システム開発においては、キューは以下のような状況での採用が考慮される方式です。
- 処理時間が読みづらく、リアルタイム処理ではタイムアウトの可能性がある
- 同時実行を許すと負荷が高まり過ぎる
- 同時実行を許すと矛盾が生じうる
私が関わることの多い開発においては、帳票出力などで採用されることがあります。
帳票出力が重たく、リアルタイム処理かつ多重実行を許すと、サーバーに負荷が高まりすぎる可能性がある場合、キューを使って以下のような仕様を設計します。
前提として、システムの画面にはユーザーに向けての通知機能があるとします
- ユーザーが帳票出力ボタンをクリックしたら、キュー登録。
- 画面上に受け付けたことを通知。
- バックグラウンドプログラムが、キューに登録された順でひとつずつ帳票出力、完了したら通知
- 通知を受け取ったユーザーは、通知画面から帳票をダウンロード
即時性よりも、確実にこなすことを優先するためにキューを活用する設計です。
スタック(Last-In-First-Out)
スタックは後入先出し方と呼ばれるデータ格納方式です。
Last-In-First-Out、略してLIFOと言われます。
こちらは、現実世界で例えず、最初からコンピューターの世界でイメージした方が理解しやすいと思います。
以下の使い方が挙げられます。
- エディタのUndo機能
- ブラウザの戻る
- プログラムでエラーが発生した時のスタックトレース
この中から、エディタのUndo機能を例にしてみます。
操作履歴が下記の表だとします。
| 操作番号 | 実施した操作 |
|---|---|
| 10 | 画像Dを削除 |
| 9 | 「明日も晴れるといいですね」を追加 |
| 8 | 文字のフォントを変更 |
| 7 | 段落Aを削除 |
| 6 | リンクCを挿入 |
| 5 | 新しい段落Bを追加 |
| 4 | 「こんにちは」を「こんばんは」に変更 |
| 3 | 画像Aを挿入 |
| 2 | 「今日はいい天気です」を追加 |
| 1 | 「こんにちは」を入力 |
エディタでUndo機能を使用した場合、操作番号：10のデータを取り出し、その内容を取り消します。
操作番号：10のデータは消されます。
（実際には、Redoがあるので、どこかには残すとは思います。）
さらにUndoした場合は、操作番号：10のデータを取り出し、その内容を取り消します。
このように、スタックは辿ることが重要なデータにおいて採用が考慮される方式です。
最後に
以上、キューとスタックの考え方について述べさせていただきました。
プログラミングの学習において、ただ覚えるだけの作業は苦痛を伴います。
何に使われる技術なのかがイメージできれば、学習の苦痛は少し和らぐと思いますので、本記事が誰かの役に立てることを願います。