コンピュータ用語で、データの持ち方のことを「データ構造」と言います。「データの持ち方」と言われても、ピンと来ないかもしれません。そこで現実に置き換えて、授業で配布されたプリント（データ）を管理する方法について考えてみましょう。

  • ・新しい順に並べる
  • ・教科ごとにまとめる

    • 上記のような方法が思い浮かぶと思います。そうした管理方法のことをプログラミングの世界ではデータ構造と呼んでいるのです。

    データ構造について知ることは、プログラミングにおいて非常に大切です。なぜなら、どのデータ構造を選択するかによって、プログラムを実行した際の計算時間が大幅に変化することがあるからです。そこで今回は、代表的なデータ構造として、「スタック」「キュー」「優先度付きキュー」の 3 つを紹介します。

    スタックとは

    スタックは、以下の 2 種類の操作を行うことができるデータ構造です。

  • 操作1：スタックの一番上に要素 x を追加する。
  • 操作2：スタックの一番上にある要素を調べ、それを取り出す。

    • 積み上げた本を想像するとわかりやすいでしょう。要素xを本だとするとき、操作 1 は「読みたい本を積むこと」、操作 2 は「一番上にある本のタイトルを調べ、それを読むこと」に対応します。以下の図は、スタックが変化していく様子を例示したものです。

    スタックの実装にはさまざまな方法がありますが、Python では deque モジュールを使うと簡単に実装することができます（以下のプログラムは上図の例に対応しています）。なお、deque モジュールを利用した場合、操作 1・2 両方について、1 回当たりの計算量は O(1) と非常に高速です。

    from collections import deque

# スタック S を定義する
S = deque()

# シミュレーション
S.append(8)  # スタックに 8 を追加（操作 1）
S.append(6)  # スタックに 6 を追加（操作 1）
x4 = S.pop() # 一番上の要素を取り出す（操作 2、x4 = 6 になる）
S.append(9)  # スタックに 9 を追加（操作 1）
S.append(1)  # スタックに 1 を追加（操作 1）
x7 = S.pop() # 一番上の要素を取り出す（操作 2、x7 = 1 になる）
x8 = S.pop() # 一番上の要素を取り出す（操作 2、x8 = 9 になる）