データ構造(4)pythonシーケンステーブルを使用してスタックを実装
1427 ワード
コンセプト:
スタック(stack)は、スタックと呼ばれるコンテナであり、データ要素、アクセス要素、削除要素を格納することができ、コンテナの一端(スタックトップ指標、英語:topと呼ばれる)でデータ(英語:push)と出力データ(英語:pop)の演算しか許可できないことを特徴とする.位置概念がなく、いつでもアクセス・削除できる要素が、これまで最後に保存されていた要素であることを保証し、後進先出(LIFO,Last In First Out)の原理に従って動作する.
注意:スタックはデータ構造ではなく、いくつかのデータ構造が使用されるときにスタックの特徴を持っているだけで、スタックと呼ぶことができ、容器、すなわち、先進的な先出しのアクセス方式を満たす容器と理解することができる.
適用シーン:
関数呼び出し
例えば、関数AはBを呼び出し、BはCを呼び出し、最後にCを呼び出すが、実行時はCが先に実行し、戻って、それからBが実行し、戻って、Aが再実行し、戻ってくる.現在の関数を呼び出すとローカル変数とパラメータがスタックに入り、関数が戻ると現在の関数のローカル変数とパラメータが破棄され、スタックが出ます.
pythonはシーケンステーブルを使用してスタックを実装します.
間違いがあれば指摘してください.
スタック(stack)は、スタックと呼ばれるコンテナであり、データ要素、アクセス要素、削除要素を格納することができ、コンテナの一端(スタックトップ指標、英語:topと呼ばれる)でデータ(英語:push)と出力データ(英語:pop)の演算しか許可できないことを特徴とする.位置概念がなく、いつでもアクセス・削除できる要素が、これまで最後に保存されていた要素であることを保証し、後進先出(LIFO,Last In First Out)の原理に従って動作する.
注意:スタックはデータ構造ではなく、いくつかのデータ構造が使用されるときにスタックの特徴を持っているだけで、スタックと呼ぶことができ、容器、すなわち、先進的な先出しのアクセス方式を満たす容器と理解することができる.
適用シーン:
関数呼び出し
例えば、関数AはBを呼び出し、BはCを呼び出し、最後にCを呼び出すが、実行時はCが先に実行し、戻って、それからBが実行し、戻って、Aが再実行し、戻ってくる.現在の関数を呼び出すとローカル変数とパラメータがスタックに入り、関数が戻ると現在の関数のローカル変数とパラメータが破棄され、スタックが出ます.
pythonはシーケンステーブルを使用してスタックを実装します.
class Stack(object):
def __init__(self):
self.stack = []
def push(self, item):
""" item """
self.stack.append(item)
def pop(self):
""" """
return self.stack.pop()
def is_empty(self):
""" """
return self.stack == []
def peek(self):
""" """
if self.is_empty():
return None
return self.stack[-1]
def size(self):
""" """
return len(self.stack)
if __name__ == '__main__':
st = Stack()
st.push(1)
st.push(2)
st.push(3)
st.push(4)
print(st.pop())
print(st.peek())
print(st.pop())
間違いがあれば指摘してください.