データ構造を使いこなす — 配列・スタック・キューの仕組みと選び方

導入

プログラムがデータをどの「入れ物」に格納するかによって、処理の速さは大きく変わります。スタック・キュー・配列——それぞれに得意な場面があり、選び方を知るだけでプログラムの品質がぐっと上がります。

くわしく知ろう

データ構造とは、データを格納・管理するための形式を指します。代表的な構造を確認します。

配列（array）は、同じ型のデータを連続したメモリ領域に並べた構造です。添字（インデックス）を使ってどの要素にも直接アクセスできるため、アクセスの計算量はO(1)になっています。一方、先頭への挿入・削除では後続要素をすべてずらす必要があり、O(n)のコストが発生します。

連結リスト（linked list）は、各要素がポインタで次の要素を指す構造です。挿入・削除はポインタの付け替えだけで済むためO(1)ですが、特定要素へのアクセスは先頭から順にたどるためO(n)になります。配列と連結リストは「アクセス速度」と「挿入・削除速度」でトレードオフの関係にあります。

スタック（stack）は後から入れたものを先に取り出すLIFO（Last In First Out）の構造で、追加をpush・取り出しをpopと呼びます。関数の呼び出し管理（コールスタック）に使われています。

キュー（queue）は先に入れたものを先に取り出すFIFO（First In First Out）の構造で、追加をenqueue・取り出しをdequeueと呼びます。プリンタの印刷待ちやCPUスケジューリングで活用されています。このようなデータの操作インタフェースを定義した概念を抽象データ型（ADT）といいます。

具体例

たとえば学籍番号順の成績管理には配列が適しています。番号を添字として直接アクセスできるからです。一方、スーパーのレジ待ちは典型的なキューで、先に並んだ人が先に会計を済ませます。本を積み重ねた山はスタックの好例で、一番上の本（最後に置いた本）しか取り出せません。

まとめ・試験ポイント

• 配列＝連続メモリ領域・添字でアクセスO(1)、先頭挿入はO(n)
• 連結リスト＝ポインタで要素を連鎖、挿入・削除O(1)、ランダムアクセスO(n)
• スタック＝LIFO（後入れ先出し）・push/pop・関数呼び出し管理に使用
• キュー＝FIFO（先入れ先出し）・enqueue/dequeue・プリンタキュー・CPUスケジューリングに使用
• 抽象データ型（ADT）＝操作インタフェースで定義した概念（実装は問わない）
• 試験では配列の先頭挿入コストO(n)、スタック/キューの動作順序トレース、LIFO/FIFOの識別が頻出