6.1 スタックの定義とその特性
スタックは、"最後に入ったものが最初に出る" (Last In, First Out, LIFO) という原則に基づいて編成された要素の集合を表す抽象データ構造だよ。スタックは本の山みたいに考えることができて、最後に追加された本は山の頂上にあり、最初に取り出されるんだ。
スタックの特性:
- LIFO (Last In, First Out): 最後に追加された要素が最初に取り出される。
- 制限された操作: スタックでは、要素の追加 (push)、削除 (pop)、および頂上の要素の確認 (peek) のみがサポートされる。
- 一方向アクセス: 要素へのアクセスはスタックの頂上からのみ可能。
- 簡単な実装: スタックは配列またはリンクリストで簡単に実装できる。
- メモリ管理: 一時的なデータや状態は、追加された順序の逆で保存および取り出される。
LIFOの動作原理:
- 要素の追加 (push): 新しい要素がスタックの頂上に追加される。
- 要素の削除 (pop): 最後に追加された要素がスタックの頂上から削除される。
- 頂上の確認 (peek): スタックの頂上にある要素を削除せずに見ることができる。
スタックの要素は一方の側(トップと呼ばれる)から追加および削除される。したがって、最後に追加された要素が常に頂上にあり、最初に削除される。
6.2 主な操作
主な操作: push, pop, peek
操作 push: 新しい要素をスタックの頂上に追加する。
時間計算量: O(1).
Pythonでlistを使ったスタックのエミュレーションの例:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # 出力: [10, 20]
操作 pop: スタックの頂上から要素を削除して返す。
時間計算量: O(1).
Pythonでlistを使ったスタックのエミュレーションの例:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # 出力: 20
print(stack) # 出力: [10]
操作 peek: スタックの頂上にある要素を削除せずに返す。
時間計算量: O(1).
実装の例:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # 出力: 10
6.3 スタックの使用例
スタックの使用例をいくつか紹介してみよう:
関数呼び出しの管理
Pythonでは、プログラムの実行中に関数を追跡するためにスタックが使用されるんだ。関数が呼び出されるたびに、その戻りアドレスとローカル変数がスタックに置かれる。関数が実行を終了すると、呼び出した関数に制御が戻り、データはスタックから取り出される。
スタック呼び出しの使用例:
この例では、再帰呼び出しの関数factorialが基底条件 (n == 1) に達するまで、それぞれの呼び出し状態をスタック呼び出しで保持する。
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 出力: 120
操作の取り消し (Undo)
スタックは、テキストエディタや他のアプリケーションでの操作取り消し機能の実装に使用される。ユーザーが操作を行うと、それはスタックに保存される。Undo操作が実行されると、最後の操作がスタックから取り出され、取り消される。
操作取り消しのためのスタック使用例:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# 使用例:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # 出力: "Hello World"
editor.undo()
print(editor.text) # 出力: "Hello"
editor.undo()
print(editor.text) # 出力: ""
GO TO FULL VERSION