データ構造は、コンピュータのストレージを整理して、効率的にデータにアクセスしたり変更したりできるようにするものです。
スタックとキューは、コンピュータサイエンスで定義された最も初期のデータ構造の一部です。
簡単に習得でき、実装も簡単なため、その用途は一般的で、ほとんどの場合、さまざまなタスクのためにソフトウェアにこれらを組み込むことになるでしょう。
スタックやキューは、ArrayやLinked Listで実装されるのが一般的です。
ここでは、スタックとキューの両方に対応するために、 List データ構造に依存することにします。
どのように機能するのですか？
スタック
スタックは、その名の通り、後入れ先出し(LIFO)の原則に従います。
コインを1枚ずつ重ねるように、一番上に置いた最後のコインは、後でスタックから取り除かれる最初のコインとなります。
したがって、スタックを実装するためには、2つの簡単な操作が必要です。
- push` – スタックの一番上に要素を追加します。
-
pop– スタックの一番上にある要素を削除します。
キュー
キューはその名の通り、先入れ先出し(FIFO)の原則に従っています。
映画のチケットを買うために行列に並ぶように、最初に並んだ人が最初にチケットを買って映画を楽しむことができるのです。
したがって、待ち行列を実装するためには、2つの簡単な操作が必要です。
-
enqueue– 要素をキューの最後に追加します。
-
dequeue– キューの先頭にある要素を削除します。
リストによるスタックとキュー
Python の組み込みの List データ構造には、スタックとキューの両方の操作をシミュレートするメソッドがバンドルされています。
ここでは、文字のスタックを考えてみましょう。
letters = []
# Let's push some letters into our list
letters.append('c')
letters.append('a')
letters.append('t')
letters.append('g')
# Now let's pop letters, we should get 'g'
last_item = letters.pop()
print(last_item)
# If we pop again we'll get 't'
last_item = letters.pop()
print(last_item)
# 'c' and 'a' remain
print(letters) # ['c', 'a']
同じ関数を使用してキューを実装することができます。
pop` 関数は、オプションで引数として取得したいアイテムのインデックスを受け取ります。
つまり、リストの最初のインデックスを 0 にして pop を使用すると、キューのような動作になります。
果物の「キュー」を考えてみましょう。
fruits = []
# Let's enqueue some fruits into our list
fruits.append('banana')
fruits.append('grapes')
fruits.append('mango')
fruits.append('orange')
# Now let's dequeue our fruits, we should get 'banana'
first_item = fruits.pop(0)
print(first_item)
# If we dequeue again we'll get 'grapes'
first_item = fruits.pop(0)
print(first_item)
# 'mango' and 'orange' remain
print(fruits) # ['c', 'a']
ここでも、リストの append と pop オペレーションを使って、キューのコアオペレーションをシミュレートしています。
Dequeライブラリによるスタックとキュー
Python には deque (発音は ‘deck’) ライブラリがあり、スタックやキューとして動作する効率的なメソッドをシーケンスに提供しています。
Deque` は Double Ended Queue の略で、格納されている要素の最初か最後を取得することができる一般化された待ち行列です。
from collections import deque
# you can initialize a deque with a list
numbers = deque()
# Use append like before to add elements
numbers.append(99)
numbers.append(15)
numbers.append(82)
numbers.append(50)
numbers.append(47)
# You can pop like a stack
last_item = numbers.pop()
print(last_item) # 47
print(numbers) # deque([99, 15, 82, 50])
# You can dequeue like a queue
first_item = numbers.popleft()
print(first_item) # 99
print(numbers) # deque([15, 82, 50])
deque` ライブラリや、Pythonが提供する他のタイプのコレクションについてもっと知りたい場合は、 Pythonのコレクションモジュール入門を参照してください。
Pythonでの実装の厳密化
もしあなたのコードがスタックを必要としていて、 List を提供した場合、プログラマが insert や remove などのリスト関数を呼んで、スタックの順番に影響を与えることを止めることはできません! これはスタックを定義する意味を根本的に台無しにします。
なぜなら、スタックはもはやあるべき姿では機能しないからです。
データに対して有効な操作しか行えないようにしたい場合もあります。
各データ構造に対して必要なメソッドだけを公開するクラスを作ればよいのです。
そのために、stack_queue.py というファイルを新規に作成し、2つのクラスを定義しましょう。
# A simple class stack that only allows pop and push operations
class Stack:
def __init__(self):
self.stack = []
def pop(self):
if len(self.stack) < 1:
return None
return self.stack.pop()
def push(self, item):
self.stack.append(item)
def size(self):
return len(self.stack)
# And a queue that only has enqueue and dequeue operations
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if len(self.queue) < 1:
return None
return self.queue.pop(0)
def size(self):
return len(self.queue)
この Stack と Queue を使用するプログラマは、データを操作するために提供されるメソッドを代わりに使用することが推奨されます。
例
あなたが新しいワープロの開発者だとします。
あなたは、ユーザーがセッションの初めまで自分の行動を戻せるようにする「取り消し機能」を作ることを課されました。
スタックは、このシナリオに理想的です。
ユーザーが行ったすべてのアクションをスタックにプッシュして記録することができます。
ユーザーがあるアクションを取り消したいときは、スタックからそれをポップします。
このように、この機能を素早くシミュレートすることができます。
document_actions = Stack()
# The first enters the title of the document
document_actions.push('action: enter; text_id: 1; text: This is my favourite document')
# Next they center the text
document_actions.push('action: format; text_id: 1; alignment: center')
# As with most writers, the user is unhappy with the first draft and undoes the center alignment
document_actions.pop()
# The title is better on the left with bold font
document_actions.push('action: format; text_id: 1; style: bold')
キューは、プログラミングの世界でも広く使われています。
ストリートファイター」や「大乱闘スマッシュブラザーズ」のようなゲームを思い浮かべてください。
これらのゲームのプレイヤーは、ボタンの組み合わせを押すことで必殺技を繰り出すことができます。
このボタンの組み合わせは、キューに格納することができます。
ここで、あなたが新しい格闘ゲームを開発する開発者だとします。
あなたのゲームでは、ボタンが押されるたびに入力イベントが発生します。
あるテスターが、ボタンが早く押されると、最初のボタンしか処理されず、必殺技が効かないことに気づきました。
これを解決するには、キューを使います。
入力イベントが来たら、すべてキューに入れることができるのです。
この方法なら、入力イベントの間隔が短くても問題なく、すべて保存されて処理に利用できます。
手を処理するときは、キューを解除することができます。
必殺技は、次のように処理することができる。
input_queue = Queue()
# The player wants to get the upper hand so pressing the right combination of buttons quickly
input_queue.enqueue('DOWN')
input_queue.enqueue('RIGHT')
input_queue.enqueue('B')
# Now we can process each item in the queue by dequeueing them
key_pressed = input_queue.dequeue() # 'DOWN'
# We'll probably change our player position
key_pressed = input_queue.dequeue() # 'RIGHT'
# We'll change the player's position again and keep track of a potential special move to perform
key_pressed = input_queue.dequeue() # 'B'
# This can do the act, but the game's logic will know to do the special move
結論
スタックとキューは、データを順番に保存したり取り出したりすることができる簡単なデータ構造です。
スタックでは、最後に入力した項目が最初に出てくる。
キューでは、最初に入力した項目が最初に出てきます。
スタックにアイテムを追加するには push オペレーションを使用し、アイテムを取得するには pop オペレーションを使用します。
キューでは、アイテムを追加するには enqueue オペレーションを使用し、アイテムを取得するには dequeue オペレーションを使用します。
Python では、組み込みの List データ構造を使用するだけで、スタックとキューを実装することができます。
また、Python には deque ライブラリがあり、1つのオブジェクトでスタックとキューの操作を効率的に提供することができます。
最後に、私たちはデータの厳密な制御のために、スタックとキューのクラスを作りました。
スタックとキューには多くの実世界での使用例があり、それらを理解することで多くのデータ保存の問題を簡単かつ効果的に解決することができます。