独学プログラマー21章読んでみた：データ構造

この章はデータ構造について書いてありました。前にもデータ構造について書いてあった章があって、そこではリスト、タプル、辞書について書いてありました。今回はそれに追加で、スタックとキューというものが紹介されていました。

スタック

スタックはリストと同じように要素を追加したり、削除したりできるデータ構造のことですが、リストとの違いは、要素の追加・削除を最後の要素に対してしか行えないという点です。

例えば[1,2,3]というスタックは3の後ろにしか追加することができなくて、3しか削除できません。なので2を削除したい場合は3を削除した後にしか行えないということになります。

スタックから要素を削除することをpop、スタックに要素を追加することをpushと言います。また、このように最後に入れた要素だけ取り出せるデータ構造をラストイン・ファーストアウト(LIFO)と言います。わかりやすいですね！最後に入ったものが最初に出る。

スタックのデータ構造はpythonのライブラリで提供されているらしいです。この本では理解のために1回自分で実装することを進められていました。

スタッククラスには5つのメソッドがあります。

is_empty：中に要素がなければTrueを返す
push：要素をスタックの1番上に積む
pop：スタックの1番上の要素を削除
peek：スタックの1番上の要素を返す
size：スタックの要素数を返す

pushメソッドではpythonにもともと入っているappendメソッドを使い要素を追加し、popメソッドではデータ構造の指定のインデックスを削除できるpopメソッドを使って実装しています。インデックスを指定しなかった場合、データ構造の末尾の要素が削除されます。mainでは動作確認のために色々自分でチェックしてみた内容です。

f:id:yoshinon444:20181028154255p:plain

これを使うことで要素の並び順を逆に並び替えたりすることもできます。あるデータ構造を作り新しいデータ構造にpopメソッドを使って後ろから代入していけば良いです。pushメソッドは1つずつしか要素を追加することができないので、一気に追加する場合はfor文を回す必要があります。

キュー

キューもリストと同様に要素を追加したり削除したりできますが、スタックのように追加・削除の際に特別なルールがあります。スタックとは違い、最初に入れた要素が1番はじめに取り出すことができます。このようなデータ構造をファーストイン・ファーストアウト(FIFO)と言います。最初に入ったものが最初に出る。スタックと逆ですね。

これもpythonの組み込みクラスcollection.dequeとして提供していますが、実装して見ましょうということでした。

本来もっと多くのメソッドが用意されているらしいのですがここでは4つのメソッドを持たせます。