Pythonのリストをスタックとキューとして使う方法を徹底解説

本記事では、Python 3.x(およびそれ以前のバージョン)におけるスタック(Stack)とキュー(Queue)という基本的なデータ構造について解説します。それぞれのデータ構造の仕組みや操作方法を、実際のコード例とともにわかりやすく学んでいきましょう。

本記事で扱う主なトピックは以下の通りです。

1. 挿入操作(Push / Enqueue)
2. 削除操作(Pop / Dequeue)
3. 表示・走査(トラバース)操作

前提知識:リストとリスト操作の基礎
関連するデータ構造:リスト操作

スタック(Stack)とは

スタックでは、オブジェクトが積み重なるように格納され、取り出す際には到着した順序とは逆の順序で削除されます。つまり、LIFO(Last In First Out:後入れ先出し)の考え方に従うデータ構造です。

スタックに対する主な操作

• 要素の追加(Push):スタックの最上部(トップ)に要素を追加します。追加した要素の数だけスタックのサイズが増加します。
• 要素の削除(Pop):2つのケースがあります。スタックが空の場合は削除対象の要素が存在せず「アンダーフロー(Underflow)」が発生します。一方、要素が存在する場合は最上部の要素が削除され、その分だけスタックのサイズが減少します。
• 走査・表示(Display):スタック内の各要素を順番に訪問し、画面に表示します。

さらに、「ピーク(Peek)」という追加機能を実装することもできます。これはスタックの最上部にある値を取り出さずに参照する機能です。

スタックの特徴

• 挿入された順序が保持される
• 重複した要素を許容する
• 同種のデータ型を格納するのに適している
• 構文解析(パース)処理などで非常に有用

サンプルコード

def isEmpty(stk): # スタックが空かどうかを判定
    if stk==[]:
        return True
    else:
        return False

def Push(stk,item): # スタックへの要素の追加を許可
    stk.append(item)
    top=len(stk)-1

def Pop(stk):
    if isEmpty(stk): # スタックが空かどうかを確認
        print("Underflow")
    else: # スタックからの要素の削除を許可
        item=stk.pop()
        if len(stk)==0:
            top=None
        else:
            top=len(stk)
            print("Popped item is "+str(item))

def Display(stk):
    if isEmpty(stk):
        print("Stack is empty")
    else:
        top=len(stk)-1
        print("Elements in the stack are: ")
        for i in range(top,-1,-1):
            print (str(stk[i]))

# 実行用コード
if __name__ == "__main__":
    stk=[]
    top=None
    Push(stk,1)
    Push(stk,2)
    Push(stk,3)
    Push(stk,4)
    Pop(stk)
    Display(stk)

上記のコードは、Python 3.xにおけるスタックの基本機能を実装したものです。if-else文を複数組み合わせてユーザーに選択肢を提示すれば、メニュー形式の対話型プログラムに拡張することも可能です。スタックを構成する基本的な考え方は、どちらの場合でも変わりません。

また、input()関数を使えばユーザーからの入力を受け付ける形式にもできます(ここでは説明を簡単にするため、静的な値を直接指定しています)。

実行結果

Popped item is 4
Elements in the stack are:
3
2
1

キュー(Queue)とは

キューでは、オブジェクトが一列に並ぶように格納され、到着した順序どおりに取り出されます。つまり、FIFO(First In First Out:先入れ先出し)の考え方に従うデータ構造です。

キューに対する主な操作

• 要素の追加(Enqueue):キューの末尾(リア側)に要素を追加します。追加した要素の数だけキューのサイズが増加します。
• 要素の削除(Dequeue):2つのケースがあります。キューが空の場合は削除対象の要素が存在せず「アンダーフロー」が発生します。要素が存在する場合は先頭(フロント側)の要素が削除され、その分だけキューのサイズが減少します。
• 走査・表示(Display):キュー内の各要素を順番に訪問し、画面に表示します。

こちらも「ピーク(Peek)」機能を追加できます。キューの場合は末尾(リア側)の値を参照する機能として実装します。

キューの特徴

• 挿入された順序が保持される
• 重複した要素を許容する
• 同種のデータ型を格納するのに適している
• CPUのタスクスケジューリングなどで非常に有用

サンプルコード

# キューの末尾に要素を追加する
def enqueue(data):
    queue.insert(0,data)

# キューの先頭要素を削除する
def dequeue():
    if len(queue)>0:
        return queue.pop()
    return ("Queue Empty!")

# キューの要素を表示する
def display():
    print("Elements on queue are:");
    for i in range(len(queue)):
        print(queue[i])

# 実行用コード
if __name__=="__main__":
    queue=[]
    enqueue(5)
    enqueue(6)
    enqueue(9)
    enqueue(5)
    enqueue(3)
    print("Popped Element is: "+str(dequeue()))
    display()

上記のコードは、Python 3.xにおけるキューの基本機能を実装したものです。スタックと同様に、if-else文を組み合わせてメニュー形式のプログラムにすることもできます。キューを構成する基本的な考え方は、実装形態に関わらず共通しています。

input()関数を使用すれば、ユーザー入力に対応したプログラムに変更することも可能です(ここでは静的な値を使用しています)。

実行結果

Popped item is: 5
Elements on queue are:
3
5
9
6

まとめ

本記事では、Python 3.xにおいてスタックとキューのデータ構造を実装する方法を学びました。ここで紹介したアルゴリズムは、他のプログラミング言語でスタックやキューを扱うプログラムを作成する際にも応用できます。ぜひ自分のコードに取り入れてみてください。