スタック(LIFO)とキュー(FIFO)の実装と活用例

はじめに

代表的なデータ構造であるスタックとキューをPythonにより実装します.
加えて,実践的な活用例についても実装してみたいと思います.

スタック

スタックとは

LIFO(Last-In-First-Out)型のデータ構造です.
天井だけ空いた箱を使って,モノを出し入れするようなイメージです.

名前の通り,最後に入ったモノが最初に取り出されます.
スタックにモノを追加することを「プッシュ」,スタックからモノを取り出すことを「ポップ」といいます.

データを一番上にプッシュしたり,一番上のデータをポップするためには,スタックに一番最後に入ったモノの添え字を覚えておく必要があります.これを「スタックポインタ」と言います.

Pythonで実装

class Stack:
    def __init__(self):
        self.stack = []
        self.sp = -1

    def push(self, param):
        self.sp += 1
        self.stack.append(param)

    def pop(self):
        retval = self.stack[self.sp]
        del self.stack[self.sp]
        self.sp -= 1
        return retval

    def get_length(self):
        return self.sp + 1

    def show_status(self):
        print("[*] stack :", self.stack[:self.sp+1])

実践例

実践例として,ブラウザ等の履歴管理システムをスタックを用いて実現してみようと思います.

具体的には,あるページへのアクセスを行った場合には,スタックにそのアクセス先をプッシュします.
一方で,戻るボタンが押された場合には,スタックからデータをポップし,以前どのページにアクセスしていたのかを確認します.

from stack import *

def main():
    # スタックのインスタンスを生成
    history = Stack()
    history_text = ""

    print("History Management System")
    print("commands ('back', 'check', 'end') are available.")

    while True:
        user_input = input("Where to go : ")

        if user_input == "end":
            history_text += "end"
            break
        elif user_input == "check":
            history.show_status()
        # back の場合,2件遡って表示した後,再度プッシュ
        elif user_input == "back":
            garbage = history.pop()
            before_page = history.pop()
            history_text += (before_page + " -> ")
            history.push(before_page)
        # 普通の入力の場合,履歴にそのまま追加する
        else:
            history.push(user_input)
            history_text += (user_input + " -> ")

    print(history_text)


if __name__ == '__main__':
    main()
History Management System
commands ('back', 'check', 'end') are available.
Where to go : google
Where to go : yahoo
Where to go : hatena
Where to go : twitter
Where to go : back
Where to go : back
Where to go : wiki
Where to go : bing
Where to go : back
Where to go : back
Where to go : back
Where to go : amazon
Where to go : end
google -> yahoo -> hatena -> twitter -> hatena -> yahoo -> wiki -> bing -> wiki -> yahoo -> google -> amazon -> end

キュー

キューとは

FIFO(First-In-First-Out)型のデータ構造です.
左右に穴の開いた筒を使って,モノを出し入れするようなイメージです.

名前の通り,最初に入ったモノが最初に取り出されます.
キューにモノを追加することを「エンキュー」,キューからモノを取り出すことを「デキュー」といいます.

pythonで実装

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, param):
        self.queue.insert(0, param)

    def dequeue(self):
        retval = self.queue[len(self.queue)-1]
        self.queue.pop(len(self.queue)-1)
        return retval

    def get_length(self):
        return len(self.queue)

    def show_status(self):
        print("[*] queue :", self.queue)

実践例

実践例として,無向グラフの任意の端点からの距離を求めるプログラムをキューを用いて実現してみようと思います.

具体的には,まず任意の端点から辿ることのできる端点を全てエンキューします.
エンキューが終われば,1つずつ端点をデキューし距離を設定します.
そして,その端点に対してさらに辿ることのできる端点を全てエンキューして...という作業を,未到達の端点がなくなるまで行います.

以下が,用いる無向グラフと,プログラムです.
プログラム中では,無向グラフは隣接行列として表現しています.

f:id:Szarny:20171002002334p:plain:w300

from queue import *

def main():
    # スタートするノードを入力
    start_node_num = int(input("Start Node : "))

    # キューのインスタンスを生成し,開始ノードをエンキュー
    queue = Queue()
    queue.enqueue(start_node_num)

    # 無向グラフの隣接行列
    graph = [
        [0,1,1,1,0,0,0,0,0],
        [1,0,0,1,0,0,0,0,0],
        [1,0,0,0,0,0,0,0,0],
        [1,1,0,0,1,1,0,0,0],
        [0,0,0,1,0,1,0,0,0],
        [0,0,0,1,1,0,0,0,1],
        [0,0,0,0,0,0,0,0,1],
        [0,0,0,0,0,0,0,0,1],
        [0,0,0,0,0,1,1,1,0]
    ]

    # ノード0からの距離
    distance_list = [-1] * len(graph[0])

    # 現在の距離
    current_distance = 0

    # キューが空になるまで繰り返す
    while True:
        if queue.get_length() == 0:
            break

        # エンキューされているノード数分繰り返す
        for i in range(queue.get_length()):
            node_num = queue.dequeue()

            # 到達済みならスキップ
            if distance_list[node_num] != -1:
                continue

            distance_list[node_num] = current_distance

            # 接続されていれば,エンキューする
            for forward_node_num, is_connected in enumerate(graph[node_num]):
                if is_connected:
                    queue.enqueue(forward_node_num)

        current_distance += 1

    for node_num, distance in enumerate(distance_list):
        print("[Node {}]\t{}".format(node_num, distance))

if __name__ == '__main__':
    main()
Start Node : 0
[Node 0]        0
[Node 1]        1
[Node 2]        1
[Node 3]        1
[Node 4]        2
[Node 5]        2
[Node 6]        4
[Node 7]        4
[Node 8]        3

Start Node : 5
[Node 0]        2
[Node 1]        2
[Node 2]        3
[Node 3]        1
[Node 4]        1
[Node 5]        0
[Node 6]        2
[Node 7]        2
[Node 8]        1