データ構造「スタック・キュー」の超簡単なまとめとサンプル／Python文法

  目次

データ構造「スタック・キュー」

今回対象とするのは、以下のデータ構造です。

• スタック＜後入先出＞Last In First Out：LIFO
• キュー＜先入先出＞First In First Out：FIFO
• 両端キュー（Double Ended Queue）
• 優先度付キュー（Priority Queue）

スタック＜後入先出＞Last In First Out：LIFO

概要 

後から入れたものから、先に取り出します。

戻るボタンやUNDO機能の実装のように、新しいものから先に取り出す必要があるときの退避先として有用です。

実装／list使用 

スタックは、Pythonの標準リストで問題なく実装可能です。

• 最後尾への追加（push)：append()
• 最後尾からの取り出し(pop）：pop()

pythonの実装サンプルです。 

def stack_sample():
    lifo_list = []
    lifo_list.append("１回目の予約")
    lifo_list.append("２回目の予約")
    lifo_list.append("３回目の予約")
    poped = lifo_list.pop()
    print(poped)

最後にプッシュしたものが最初に取り出されます。

実行すると表示するのは「３回目の予約」です。

キュー＜先入先出＞First In First Out：FIFO

概要 

先に入ったものを先に出します。

スレッド等で処理を協調させるためのパイプライン処理とか、予約のキャンセル待ち処理とかジョブスケジューリングとかの実装に使えます。

処理のイメージと用語はこんな感じ。

実装／Queueを使用

docs.python.org

簡単なサンプルをやってみます。

from queue import Queue

def fifo_sample():
    q = Queue()
    q.put("１回目の予約")
    q.put("２回目の予約")
    q.put("３回目の予約")
    poped = q.get()
    print(poped)

今度は「１回目の予約」が表示されます。

最初にいれたものがちゃんと出力されてます。

両端キュー（Double Ended Queue）

概要

先頭と末尾でデータの追加・取り出し・削除等ができるデータ構造です。

FIFOとしても、LIFOとしても使えます。

さらに、先頭に追加するか、末尾に追加するかを条件で振り分けて、取り出しだけ先頭からだけにして「条件付きFIFO」みたいなものにしたりもできます。

実装／Collections.deque使用

両端キュー（Double Ended Queue）の実装は「Collections.deque」です。

docs.python.org

これは以下のように先頭と末尾の両方に追加と取り出しのインタフェースを持ちます。

• 最後尾への追加：append()
• 最後尾からの取り出し：pop()

• 先頭への追加：appendleft(x)

• 先頭からの取り出し：popleft()

となります。

from collections import deque

def deque_sample():
    q = deque()
    q.append("１回目の予約")
    q.append("２回目の予約")
    q.append("３回目の予約")
    poped = q.pop()
    print(poped)
    leftpoped = q.popleft()
    print(leftpoped)

末尾に３つ追加して、最初に最後尾から取り出し、続けて先頭から取り出しています。

なので、「３回目の予約」→「１回目の予約」と表示されます。

優先度付キュー（Priority Queue） 

概要 

キューに対して要素を追加して、取り出す時には優先度の高いものから取り出します。

優先度の高い・・というとわかりづらいですが、例えば数値なら「一番小さいもの」から取り出されます。

実装／  heapq使用

heapqモジュールを使います。

docs.python.org

• heappush()でキューに追加します。
• heappop()で優先度の一番高いものを取り出します。

ランダムな整数をヒープキューに収めて、取り出す例の実装です。

import heapq

def heapq_sample():
    hq_list = []
    heapq.heappush(hq_list, 30)
    heapq.heappush(hq_list, 20)
    heapq.heappush(hq_list, 10)
    heapq.heappush(hq_list, 100)
    poped = heapq.heappop(hq_list)
    print(poped)
    poped = heapq.heappop(hq_list)
    print(poped)

ランダムな数値をキューにpushして、取り出してます。

結果は、10,20と小さいものから取り出されます。

以上、超簡単にですが、スタックとキューについてまとめました。

ではでは。