今回はスタックとキューについてお話しします。
最近ではスタックとキューのデータ構造を実装すること自体はあまりなくなりましたが、概念自体はしっかりと抑えておいた方がいいとのことで記事を書くことにしました。
また、データ構造の問題は基本情報技術者試験や応用情報技術者試験の午前の問題で問われることもあります。
簡単な問題なので上記の試験で問われても点数を落としてはいけません。
しっかりと特徴を抑えて、理解して頂きたいと思います。
出来れば応用範囲も含めてきちんと自分の基礎知識として定着させておくと実務で困らなくて済みます。
スタックとは何か？
スタックとは以下のように入ってきたデータを積み上げて、積み上げられたデータの一番上から取り出すデータ構造のことです。
データが下から詰みあがっていく感じになりますので、最初に入ったデータが一番下に来て、最後に入ったデータが最初に取り出されます。
このような仕組みをFILO（Firist In Last Out）、もしくはLIFO（Last In First Out）と呼びます。
日本語では先入れ後出しと表現しますね。
自分がWeb系システムのエンジニアの実務をやってきてスタック自体を実装することがなかったので、プログラムでスタックを実装することはあまりないかと思いますが、このスタックの考え方は再帰呼び出し、またはプログラムデバッグ時のコールスタックに応用されていますので、スタックを全く知らないとこの辺りの理解が厳しくなります。
なので、まずはスタックというデータ構造について理解したうえで、再帰呼び出しやコールスタックの考え方を学んでいくといいと思います。
なお、スタックにデータを入れられる数は有限であり、この数をオーバーするとスタックオーバーフローという例外が起きます。
プログラミングの質問をする有名なサイトにスタックオーバーフローという名のサイトがありますが、スタックオーバーフローはそれくらい有名な例外エラーであるということです。
特に再帰呼び出しを使う場合はスタックを使うということを理解していないとこのエラーで悩んでしまうことになるので、再帰呼び出しを使う場合はスタックの考え方を理解していることは必須であると考えてよいでしょう。
キューとは何か？
キューは最初に入れたデータが最初に取り出されるデータ構造のことです。
このような仕組みをFIFO（First In First Out）と呼びます。
日本語では先入れ先出しと表現します。
キューは以下のようなイメージで表現することが出来ます。
キューを実装すること自体はそれほどないかもしれません。
しかし、キューの考え方はとても重要で、待ち行列への応用や、プログラムで記述する処理に大きく関わってきます。
（待ち行列も重要な考え方なので、別途記事を作成する予定です）
特にキューからデータを取り出す間隔よりキューにデータを入れる間隔が短いとキューが詰まってしまい、処理が出来なくなってしまうことになります。
特に組込みソフトなどで重要になってきそうですが、自分と同じくWeb系のエンジニアをやっている人も意識しておくことは重要です。
大勢の人が利用するシステムの場合や大量のデータを取り扱うシステムの場合、処理が追い付かずにレスポンスが遅くなったり、レスポンスが返ってこなくなったりするのは、キューに入ったデータやリクエストが正常に処理できなくなるからです。
なので、キューの特徴もしっかり理解して、実務の開発で意識して開発を行うことが出来れば理想的です。
まとめ
今回はスタックとキューというデータ構造についてお話ししました。
今回のお話で理解しておきたいのは以下の点となります。
- スタックは最初に入れたデータが後で取り出されるデータ構造（FIFOまたはLIFOと呼ばれる）である
- スタックは再帰呼び出しやコールスタックに応用される
- キューは最初に入れたデータが最初に取り出されるデータ構造（FIFOと呼ばれる）である
- キューは待ち行列をはじめとしてシステム開発に重要な考え方である
キューやスタックの考え方は情報技術者試験で問われるくらい重要な考え方です。
後に演習問題を載せますので、きちんと答えられる程度に理解をしていただきたいと思います。
演習問題１
空のスタックがあり、データを入れて取り出すことを考えます。
スタックにデータを入れる時はpush(データの値)、スタックからデータを取り出す時は引数を用いずにpop()と表現するとします。
この時、
push(8)→push(6)→pop()→push(7)→push(4)→pop()→push(9)→pop()→pop()
の操作をした場合、最後のpop()で取り出されるデータの値はいくつになるでしょうか？
演習問題２
空のキューがあり、データを入れて取り出すことを考えます。
キューにデータを入れる操作をenq(データの値)、キューからデータを取り出す操作を引数を用いずにdeq()と表現するとします。
この時、
enq(6)→enq(8)→enq(5)→enq(2)→deq()→enq(3)→deq()→deq()→deq()
の操作をした場合、最後のdeq()で取り出される値はいくつになるでしょうか？
演習問題の解答
演習問題１：７
演習問題２：２
出来ましたでしょうか？
今回の記事はここまでとなります。
また次の記事でお会いしましょう。
