データ構造のスタックとキューの違いについて説明し、Pythonでコードを書いていきます。
スタック
リストにデータを追加する際は一番最後に追加され、データを取り出す際には最も新しいデータを取り出すデータ構造のことです。
いわゆる、「後入れ先出し」のパターンです。
キュー
リストにデータを追加する際は一番最後に追加され、データを取り出す際には最も古いデータを取り出すデータ構造のことです。
こちらは、「後入れ後出し」のパターンですね。
Pythonで書いてみる
Pythonにはこれらのデータ構造を簡単に表現できる便利なメソッドが存在します。
- append()
- リストの末尾に要素を追加します。「後入れ」を実行してくれます。
- pop()
- リストの末尾の要素を削除します。「先出し」を実行してくれます。
- popleft()
- 一番左側の要素を削除します。「後出し」を実行してくれます
- このメソッドはcollections.dequeを使用した時のみ有効となるので、注意が必要です。
スタックの場合
>>> lst = [1,2,3,4,5]
>>> lst.append(6)
>>> lst
[1,2,3,4,5,6]
>>> lst.pop()
6
キューの場合
>>> from collections import deque
>>> lst = deque([1,2,3,4,5])
>>> lst.append(6)
>>>lst
deque([1,2,3,4,5,6])
>>> lst.popleft()
1
このようにPythonで書くと、正しくスタックやキューが実行されていることが分かります。
まとめ
今回はデータ構造のスタックとキューについて説明してきました。
言葉での説明にピンとこない方は、Pythonでコードを書いて実行してみてはいかかでしょうか。