Pythonで学ぶスタック

• スタック
  • スタックについて
  • Pythonでのスタック利用例
    • Pythonでの表記法と注意点
    • 連結リストの要素を逆転させる
    • 逆ポーランド記法の計算
    • ディレクトリ構造の短縮化

スタック

について改めて使い道を模索してみたのでメモ。

スタックについて

底のある箱の中に積み木を積んでいくイメージ。
いわゆるLIFO(last in first out)、最後に入れたものを最初に取り出す、というデータ構造。

要素を取り出す時の操作をpop、要素を入れる時の操作をpushという。

スタックを連結リスト、もしくは配列で実装した場合のpop、pushの操作はO(1)の計算量となります。

Pythonでのスタック利用例

Pythonでの表記法と注意点

他の言語と同様に、PythonでもStackが組み込み関数として用意されています。

ここで注意すべきなのは上記で用意したPythonでリストを用いてスタックを表す場合にはpushではなく、appendを使う点です。

スタックとして使う場合は以下のように要素の出し入れを行います。

>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

他にもスタックには様々な使い道があります。

連結リストの要素を逆転させる

def reverse_linked_list(head):
    nodes = []
    while head:
        nodes.append(head.data)
        head = head.next

逆ポーランド記法の計算

def evaluate_rpn(expression):
    inter_results = []
    delimiter = ','
    operators = {
        '+':lambda y, x: x + y,'-':lambda y,x:x-y,
        '*':lambda y,x:x*y,'/':lambda y,x:x //y
    }
    
    for token in expression.split(delimiter):
        if token in operators:
            inter_results.append(operators[token](inter_results.pop(),inter_results.pop()))
        else:
            inter_results.append(int(token))
    return inter_results[-1]


expression = "3,4,+,2,*,1,+"
evaluate_rpn(expression)
# 15

ディレクトリ構造の短縮化

def shortest_path(path):
    if not path:
        raise ValueError("パスが与えられていません")
        
    path_names = []
    if path[0] == '/':
        path_names.append("/")
    for token in (token for token in path.split("/") if token not in ['.','']):
        if token == '..':
            if not path_names or path_names[-1] == '..':
                path_names.append(token)
            else:
                if path_names[-1] == '/':
                    raise ValueError("パスエラー")
        else:
            path_names.append(token)
            
    result = '/'.join(path_names)
    return result[result.startswith('//'):]


path = "/usr/lib/../appication/../bin/"
shortest_path(path)
# '/usr/lib/appication/bin'        

この様に様々な用途に使えます。
同様にキューについてもその内書く予定です。