こんにちはヤク学長です。
データサイエンティスト兼ファーマシストで、アルゴリズムやBI開発を行っています。
本記事の目的は、「アルゴリズムの基本を知る」ことを目的としています。
【本記事のもくじ】
下記の方法で、簡単に概要を抑えることができます。
- １．スタックとは
-
２．キューとは
それでは、上から順番に見ていきます。
なお、本上記の方法を順番に抑えれば成果が出ます。
記事の内容は「転載 & 引用OK」問題ありません。
１．スタックとは
スタックとは
スタックは、データ構造の一種で、データを一時的に保管するための仕組みです。スタックは、データを格納するための領域と、その領域を管理するためのポインタから構成されています。スタックには、「後入れ先出し (LIFO: Last-In, First-Out)」という特性があり、最後に追加されたデータが最初に取り出されます。
スタックは、主にプログラミング言語において関数の呼び出しや、一時的なデータの格納に用いられます。例えば、関数を呼び出すたびに、その関数で使われる変数の情報をスタックに積み、関数が終了するときには、スタックから変数の情報を取り出すことができます。また、スタックは、逆ポーランド記法の計算機や、バックトラッキングなどのアルゴリズムで使われることもあります。
Pythonにおいて、スタックはリストを用いて簡単に実装できます。具体例を以下に示します。
stack = [] # スタックの初期化
# スタックに要素を追加
stack.append(1)
stack.append(2)
stack.append(3)
# スタックから要素を取り出し
top = stack.pop()
print(top) # 3
top = stack.pop()
print(top) # 2
top = stack.pop()
print(top) # 1
上記の例では、スタックを空のリストで初期化し、append()メソッドで要素をスタックに追加しています。そして、pop()メソッドを用いて、スタックの一番上の要素を取り出しています。pop()メソッドは、リストから要素を取り出すと同時に、その要素をリストから削除するため、スタックから要素を取り出すという処理に適しています。
スタックの実例
スタックを使用する際に生じる問題の例として、スタックオーバーフローとスタックアンダーフローが挙げられます。
スタックオーバーフローは、スタックに格納するデータ量がスタックの容量を超えた場合に発生します。例えば、再帰関数を使用して無限ループを作成した場合、スタックに無限にデータが積み上げられ、スタックの容量を超えることになります。これはプログラムの異常終了やシステムのクラッシュなどを引き起こす可能性があります。
スタックアンダーフローは、スタックからデータを取り出そうとした際に、スタックが空である場合に発生します。例えば、スタックからデータを取り出す処理を複数回実行し、スタックが空になった場合に発生する可能性があります。この場合、スタックアンダーフロー例外が発生する場合があります。
これらの問題を回避するために、スタックの容量を増やしたり、再帰関数の使用を避けるなどの対策が考えられます。また、Pythonではtry-except文を使用して、スタックオーバーフローやスタックアンダーフローの例外処理を実装することができます。以下に、例を示します。
# スタックオーバーフローの例
def recursion():
recursion()
try:
recursion()
except RecursionError:
print("Recursion Error: Stack overflow")
# スタックアンダーフローの例
stack = []
try:
stack.pop()
except IndexError:
print("Index Error: Stack underflow")
上記の例では、スタックオーバーフローの場合には再帰関数を用いて無限ループを作成しています。これをtry-except文で捕捉して、RecursionErrorが発生した場合には「Recursion Error: Stack overflow」と表示します。
また、スタックアンダーフローの場合には、pop()関数を用いてスタックからデータを取り出す処理を行っています。これをtry-except文で捕捉して、IndexErrorが発生した場合には「Index Error: Stack underflow」と表示します。
２．キューとは
キュー（queue）とは、データの先入れ先出し（FIFO: First-In-First-Out）を実現するデータ構造です。キューには、最初に追加されたデータが先に取り出されるという特性があります。
キューは、例えば、コンピュータのジョブスケジューリングなど、データが順番に処理される必要がある場合に使用されます。
キューは、主に2つの操作で構成されています。
-
Enqueue（エンキュー、または入れる） 新しい要素をキューの末尾に追加します。この操作を「エンキュー」と呼びます。
-
Dequeue（デキュー、または出す） キューの先頭から要素を取り出します。この操作を「デキュー」と呼びます。
また、キューには、先頭を示すfrontと末尾を示すrearの2つのポインタがあります。
Pythonでは、リストを使ってキューを実装することができます。例えば、以下のようにしてキューを作成することができます。
queue = []キューに要素を追加する場合は、リストの末尾に要素を追加します。以下は、要素を追加するenqueue関数の例です。
def enqueue(queue, item):
queue.append(item)キューから要素を取り出す場合は、リストの先頭から要素を取り出します。以下は、要素を取り出すdequeue関数の例です。
def dequeue(queue):
if not queue:
return None
else:
return queue.pop(0)
この場合、リストのpop関数を使って先頭の要素を取り出しています。ただし、リストの先頭から要素を取り出すときには、リストの先頭に要素があるかどうかをチェックする必要があります。これを忘れると、リストが空の状態でpop関数を呼び出した場合にIndexErrorが発生してしまいます。
キューの問題と具体例
例えば、以下のように与えられた配列 arr があるとします。
arr = [1, 2, 3, 4, 5]この配列を左に2つシフトする場合、最終的には以下のようになるはずです。
[3, 4, 5, 1, 2]このような配列のシフトをキューを利用して行う場合、配列の先頭から順番にキューに追加し、指定された回数だけキューから要素を取り出して、末尾に追加することで実現できます。
具体的には、以下のような Python のコードになります。
from collections import deque
def shift_array(arr, shift_count):
n = len(arr)
q = deque(arr[:shift_count]) # キューに最初の shift_count 個の要素を追加する
for i in range(shift_count, n):
arr[i - shift_count] = arr[i] # shift_count 個前の要素を現在の要素に置き換える
for i in range(n - shift_count, n):
arr[i] = q.popleft() # キューから要素を取り出して末尾に追加する
return arrこの関数を以下のように呼び出すと、上記の例で期待されるように、配列が左に2つシフトされた結果が得られます。
>>> arr = [1, 2, 3, 4, 5]
>>> shift_array(arr, 2)
[3, 4, 5, 1, 2]
というわけで、今回は以上です。大変大変お疲れ様でした。
引き続きで、徐々に発信していきます。
コメントや感想を受け付けています。ちょっとした感想でもいいので嬉しいです。
それでは、以上です。
