本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、データ構造として有名なスタックについて学んでいきます。
スタックとは
スタック（Stack）とは、挿入および削除がリストの先頭で行われるものを指し、一般的にLIFO（Last In First Out：後入れ先出し）のデータ構造のものを言います。
身近なところでスタックの概念が使われているのが、プログラムを実行するときです。
プログラムを実行すると、OSからメモリ領域が割り当てられます。
このメモリ領域は、（アドレスの低い順に）静的領域（テキスト領域、データ領域）、ヒープ領域およびスタック領域です。
スタック領域は、OSが管理する仮想アドレス空間の最も高いアドレスから低いアドレスに向かって伸張していきます。
なお、64bit Linuxの場合は、0x0000000000000000～0x0000FFFFFFFFFFFFまでの48bitが仮想アドレス空間となります。
そして、プログラムを実行している中でサブルーチンを呼び出す際に、メインプログラムへの戻りアドレスや、サブルーチン内で使用するローカル変数の値などをスタック領域に保存する際にこのスタックという概念が使われています。
Pythonでスタックを作ってみる
それでは、Pythonでスタックを実装してみます。
ここでは書籍に倣って、逆ポーランド記法という数式の記述方法を読み取って、計算結果を返すプログラムを作成します。
# my_stack.py
import sys
class Stack:
def __init__(self, limit=32):
self.stack = []
self.limit = limit
def push(self, n):
if len(self.stack) >= self.limit:
print("stack is overflow")
return False
self.stack.append(n)
def pop(self):
if len(self.stack) == 0:
print("stack is empty.")
return False
return self.stack.pop()
def answer(self):
return self.stack[0]
st = Stack()
c = ''
x = ''
while c != '\n':
c = sys.stdin.read(1)
if c.isdigit():
x += c
elif c == ' ' or c == '\t':
if x:
st.push(int(x))
x = ''
continue
elif c == '+':
b = st.pop()
a = st.pop()
st.push(a + b)
elif c == '-':
b = st.pop()
a = st.pop()
st.push(a - b)
elif c == '*':
b = st.pop()
a = st.pop()
st.push(a * b)
elif c == '/':
b = st.pop()
a = st.pop()
st.push(a / b)
else:
pass
print('answer: {}'.format(st.answer()))
動作確認
それでは上記で作成したスクリプトを実行してみます。
数式で、"（1 + 1）×（2 + 2）"を逆ポーランド記法で記述するには、"1 1 + 2 2 + *"と書きます。
> python my_stack.py 1 1 + 2 2 + * answer: 8
ちゃんと計算できていることが確認できました。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
