第11章スタック – note to self

用語

スタック
　抽象データ型であり、最後に追加した要素だけを削除できる線形データ構造
ラストイン・ファーストアウト（LIFO）
　最後に追加した要素を最初に削除するデータ構造
アクセスが制限されたデータ構造
　（スタックは）特定の順でしか情報にアクセスするよう強制されたデータ構造
ブッシュ
　スタックに新しい要素を追加する
ポップ
　最後に追加した要素をスタックから削除する
ピーク
　スタックの要素を削除せずに1番上の要素を確認する
有限スタック（ bouded stack ）
　追加できる要素数に上限があるスタック
無限スタック（ unbounded stack ）
　追加できる要素に上限がないスタック

はじめに

もし、抽象型データとデータ構造の違いについて、まだ理解できていないと感じるなら、スタックはこれら2つの概念を理解する好例

スタックを抽象データ型として論じる際は、実装などを考えずに「最後に追加した要素にだけアクセスを許すもの」と考える

このようなデータ構造の実装方法はいろいろある。たとえば、連結リストあるいは配列のどちらかを使って、スタックの状態を表現するクラスを実装できます。連結リストあるいは配列という特定のデータ構造を用いて、スタック抽象データ型を具体的なデータ構造として実装するのです。

つまり、データ構造は、抽象データ型の現実の実装ということです。

スタックをいつ使うのか

スタックに対する要素のプッシュ、ポップの計算量は O(1) です
スタックはデータの追加と削除に対しては効率的だが、スタック全体にアクセスするような操作は非効率

たとえば、スタックの要素を表示したいとき

解決策の1つは、スタックから要素を削除しながら表示するやり方です。この処理の計算量は O(n) です← O(1) ではなく？ただし、この方法だと、リストが逆順に表示されます（LIFOだから）。またスタックからすべての要素を削除するので、スタックが空になってしまいます

別の解決方法は、元のスタックの要素をポップ（削除）しながら、一時的なスタックに追加していくやり方です
その後、一時的なスタックから要素をポップで削除しながら表示し、元のスタックに追加していきます
この方法は、一時的なスタックに全データを保持するので、より多くのリソースが必要になります
また配列の要素を表示する場合の計算量 O(n) と比べて2倍の時間がかかります

スタックは、計算においてもっともよく使われるデータ構造の一つです
スタックを使うと、後の章で学習する木やグラフのデータを検索する幅優先アルゴリズムを実現できます
また、PythonやJavaのようなプログラミング言語のランタイムシステムは、内部で関数呼び出しを処理するのにスタックを使います
コンパイラもスタックを使う。例えば、一般的な数学の式のように、入れ子になった丸括弧のペアを持つ式や、角括弧と波括弧のペアが入れ子になっている式などを解析するために、スタックを活用しています

スタックはほかにも、機械学習や他の人工知能分野で使われているバックトラックアルゴリズムでも使います
これは、スタックの要素の追加と削除の計算量が、ともに O(1) だからです
データの追加と削除が多い場合、データ構造にスタックを選択するのが適しています
たとえば、「 undo （元に戻す）」「 redo（再実行）」の両方を操作するために、1つあるいは2つのスタックを使います
たとえば、ブラウザが閲覧履歴を戻ったり進んだりするために2つのスタックを使います
ただし、スタックのすべての要素にアクセスするための計算量は O(n) なので、収集しているデータに継続的にアクセスする必要があるアルゴリズムの場合、スタックは良い選択ではありません

スタックを作成する

Pythonでスタックを実装するには、いくつかある。

実装例1

1つは stack クラスを作り、内部的には配列を使ってそのデータを管理する方法です

class Stack:
    def __init__(self):
        self.items = []
        
    def push(self, data):
        self.items.append(data)
        
    def pop(self):
        return self.items.pop()
    
    def size(self):
        return len(self.items)
        
    def is_empty(self):
        return not self.items
        
    def peek(self):
        return self.items[-1]

説明

行2
- Stack クラスの __init__ メソッドに、items インスタンス変数を定義し、空のリストを代入する
- このリストはスタック内で要素を見失わないように記録しておくための場所になる
行17
- スタックの最後の要素を返す

実装例2.

連結リストを使っても Stack クラスを実装できる
次のコードは、連結リストを使った push と pop の機能を持つシンプルなスタックの作り方

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class Stack:
    def __init__(self):
        self.head = None
        
    def push(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            node.next = self.head
            self.head = node
            
    def pop(self):
        if self.head is None:
            raise IndexError('pop from empty stack')
        poppednode = self.head
        self.head = self.head.next
        return poppednode.data

説明

行1
- まず、スタック内の連結リストの役割をする Node クラスを定義する
行6
- Stack クラスの内部に、連結リストの戦闘用要素を保持するための head インスタン変数を定義
行10
- push メソッドの中で新しいノードを作り、head が None の場合は head に代入する
- そうでなければ、元の head を新しいノードの next に代入し、head に新しいノードを代入する
行18
- スタックが空の状態で pop しようとしたら例外を発生させます
- スタックが空でなければ、連結リストから最初の要素を削除してその要素を返します
- すると2番目の要素が連結リストの最初の要素になります

▼要素を push し、pop している例

実装例3

Pythonの list をそのままスタックとして使う方法
ただし、list の場合、要素を入れた順番と逆の順番で「のみ」取り出せる、というスタックの制限から開放されているため、スタックとして実装したい場合は、Stack クラスを作成する必要がある

スタックを使って文字を反転させる

文字列を反転させる方法は3つある

# 1
'super'[::-1]

>>> 'repus'

# 2
''.join(revesed('super'))

>>> 'repus'

# 3
def reverse_string(a_string):
    stack = []
    string = ''
    for c in a_string:
        stack.append(c)
        
    for _ in a_string:
        string += stack.pop()
    return string

print(reverse_string('ビーバー'))

>>> ーバービ

最小値を保持するスタック

スタックの追加と削除の操作に加えて、最小の取得もできるデータ構造の設計をおこなう。
追加、削除、最小値の取得の3要素は O(1) で実行できるように設計してください。
この問題を解く鍵は、内部で main と min の2つのスタックを使うこと。
main スタックは、すべての追加と削除の結果を保持する。min スタックは、スタックの最小値を保持する。
この課題の解決方法を学ぶことは、技術面接をただ通過するのに役立つだけでなく、日々のプログラミングで直面する様々な状況に役立つ。次のコードはPythonで最小値を記録するスタックを実装する方法です。

class MinStack():
    def __init__(self):
        self.main = []
        self.min = [[]
                    
    def push(self, n):
        if len(self.main) == 0:
            self.min.append(n)
        elif n <= self.min[-1]:
            self.min.append(n)
        else:
            self.min.append(self.min[-1])
        self.main.append(n)
                    
    def pop(self):
        self.min.pop()
        return self.main.pop()
                    
    def get_min(self):
        return self.min[-1]

括弧用のスタック

与えられた文字の中の括弧が適切か否かを、スタックを使って確認せよ
スタックを使うこと。まず文字列の各文字を繰返し確認する
括弧開きが合ったら、スタックに追加する
括弧閉じの場合は、すでにスタックに括弧開きが存在するか否かを確認する
もし存在しなかったら、文字列の括弧は適切ではありません
括弧開きが存在したら、スタックから括弧開きを削除する
もし、文字列の括弧開きと括弧閉じの数が同じなら、ループの最後では、スタックは空になっている
スタックが空でなければ括弧開きと括弧閉じの数が等しくないということです

def check_parentheses(a_string):
    stack = []
    for c in a_string:
        if c == "(":
            stack.append(c)
        if c == ")":
            if len(stack) == 0:
                return False
            else:
                stack.pop()
    return len(stack) == 0

月	火	水	木	金	土	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31