＜アルゴリズムの基本②＞データ構造（スタックとキュー）について

Wikipediaによると、アルゴリズムとは、

アルゴリズム（英: algorithm [ˈælgəˌrɪðəm]）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。（中略）コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。

効率の良いプログラムを作成するにはアルゴリズムを知る必要がある、とのことなので今後アルゴリズムについても少しずつまとめていきたいと思います。今回、まずはデータ構造についてです。

データ構造とは

アルゴリズムは、「データ」と「処理」の組み合わせによって表現されます。

例）料理のレシピ（＝アルゴリズム）
　データ：様々な情報を表現したもの
　　・具材や調味料（肉、玉ねぎ、じゃがいも・・・）
　　・量や時間（大さじ一杯、１分・・・）
　  ・調理器具や食器（フライパン、鍋・・・）
　処理：作り方

ここで、大量のデータを効率よく管理する仕組みを「データ構造」といいます。

例）郵便番号：3桁＋４桁 合計７桁
　各桁の数値に意味を持たせて系統建てて規定することで効率よく仕分けることができる

アルゴリズムにおける「処理」を最適化するために、その「処理」に最適な「データ構造」を構築することは必要不可欠です。

主なデータ構造

データ構造はたくさんの種類がありますが、主なものを挙げます。

データ構造	概要
配列	データを隙間なく並べて管理する。データの順番は、データの並びで管理される。一直線上に並べてものを１次元配列、縦☓横に並べたものを二次元配列、縦☓横☓奥行きに並べたものを三次元配列と呼ぶ
リスト	順番のあるデータを管理するときに使う。配列と異なり、データが「ひも」で結ばれることで順番が管理される。
スタック	データを積み重ねるようにして管理する方式 ⇒　後入れ先出し方式（LIFO = Last In First Out) データを入れる操作：PUSH,データを取り出す操作：POP　と呼ぶ。
キュー（待ち行列）	先に入力されたデータが先に出力される特徴をもったデータ構造 ⇒ 先入れ先出し方式（FIFO = First In First Out)
ツリー（木構造）	木の幹、枝、葉の関係のようにデータを管理する構造。ノード（節点、頂点）と、エッジ（ノード同士を結ぶ、枝や辺）から構成される。出発点のノードを特別に「根」または「ルートノード」と呼ぶ。

このなかで今回は、スタックとキュー（待ち行列）について記載します。ツリー構造はたくさん有りそうなので別の機会にまとめます。

Pythonでの実装

さて、これらのデータ構造をＰｙｔｈｏｎで実装するにあたってはリスト型メソッドが使えます。

まずはリスト型メソッドのおさらい

公式チュートリアルを参照頂ければ解ると思いますが、備忘録も兼ねて記載します。

# リストａを定義
>>> a = ['a', 'b', 'c']

# リストの末尾に要素を追加
>>> a.append('d')
>>> a
['a', 'b', 'c', 'd']

# リストを拡張
>>> a.extend(['d', 'c', 'b', 'a'])
>>> a
['a', 'b', 'c', 'd', 'd', 'c', 'b', 'a']

# 指定した位置に要素を挿入
>>> a.insert(4, 'e')
>>> a
['a', 'b', 'c', 'd', 'e', 'd', 'c', 'b', 'a']

# 指定した値と等しい最初の要素を削除
>>> a.remove('e')
>>> a
['a', 'b', 'c', 'd', 'd', 'c', 'b', 'a']

# 指定された位置にある要素をリストから削除し、その要素を返却。
# 位置を指定しない場合は末尾データを削除
>>> a.pop()
'a'
# 元のリストからも削除されている
>>> a
['a', 'b', 'c', 'd', 'd', 'c', 'b']

# 指定した値の最初の位置を返す
>>> a.index('b')
1

# 指定した値が含まれる数を返す
>>> a.count('b')
2

# リストをインプレース演算（元のリストを置き換える演算）で
# 並べ替え（ソートの方法は引数の設定による）
>>> a.sort()
>>> a
['a', 'b', 'b', 'c', 'c', 'd', 'd']

# リストの要素を、インプレース演算で逆順に並べ替え
>>> a.reverse()
>>> a
['d', 'd', 'c', 'c', 'b', 'b', 'a']

# 浅いコピー(shallow copy)を返す
>>> a.copy()
['d', 'd', 'c', 'c', 'b', 'b', 'a']

# 要素を全クリア
>>> a.clear()
>>> a
[]

スタックとして使う

リストをスタックとして使う場合は、append()メソッドでPUSH操作、pop()メソッドでPOP操作を行います。

>>> stack = []
# append()メソッドでデータをPUSH　（Ａ→Ｂ→Ｃとデータを入力）
>>> stack.append('A')
>>> stack.append('B')
>>> stack.append('C')
>>> stack
['A', 'B', 'C']

# POP()メソッドでデータをPOP（Ｃ→Ｂ→Ａとデータが出力）
>>> stack.pop()
'C'
>>> stack
['A', 'B']
>>> stack.pop()
'B'
>>> stack
['A']

キューとして使う

リストをキューとして使うこともできます。例えば以下

>>> que = []
# データを入力（エンキュー　＝　enqueue)　（Ａ→Ｂ→Ｃとデータを入力）
>>> que.append('A')
>>> que.append('B')
>>> que.append('C')
>>> que
['A', 'B', 'C']

# データを取り出す（デキュー　= dequeue)（Ａ→Ｂ→Ｃとデータが出力）
>>> que.pop(0)
'A'
>>> que
['B', 'C']
>>> que.pop(0)
'B'
>>> que
['C']

ただ、公式によると、

しかし、リストでは効率的にこの目的を達成することが出来ません。追加（append）や取り出し（pop）をリストの末尾に対して行うと速いのですが、挿入（insert）や取り出し（pop）をリストの先頭に対して行うと遅くなってしまいます（他の要素をひとつずつずらす必要があるからです）。

そこで、キューの場合はcollections.deque を使うことがおすすめされています。

>>> from collections import deque

# データを入力（エンキュー　＝　enqueue)
>>> que = deque()
>>> que.append('A')
>>> que.append('B')
>>> que.append('C')
>>> que
deque(['A', 'B', 'C'])

# データを取り出す（デキュー　= dequeue)
>>> que.popleft()
'A'
>>> que.popleft()
'B'
>>> que
deque(['C'])