【データ構造】スタック stackとキュー que【基本講座】

プログラムというとどうしてもプログラム言語を連想してしまいがちですが、実はそうではありません。
元来、アルゴリズムとデータ構造を足したものをプログラムと呼んでいるのです。
今回は、データ構造のひとつであるスタック（stack）について勉強していきます。
Pythonプログラムにおいてもたびたび問題で使用される基本情報技術者試験の範囲でもあるので、振る舞いをちゃんと理解しましょう。

出典：http://www.photo-ac.com/

ゼロから学ぶ　データ構造　スタック編(stack)

スタックの特徴

スタックとは、コンピュータで用いられる基本的なデータ構造のひとつです。データを後入れ先出しの構造で保持するものです。英語の頭文字をとって、FILO（First In Last Out）と呼ばれています。

抽象データ型としてのスタック

抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ(push)とポップ(pop)を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。

FILOの操作は、PUSHとPOPの2つです。

よく例えに出るのが、お皿で、PUSHは、お皿を重ねるイメージ。また、POPは、お皿を一番上から1枚ずつ取り除くイメージです。

具体的に言うなら、新たに皿が追加される（Pushされる）と、その新しい皿がスタックのトップとなり、下にある皿を隠してしまう。皿をスタックから取る（Popする）ということですね。

スタックと関連するデータ構造について

FILO(First In Last Out、先入れ後出し)の原則を持つデータ構造がスタックであるのに対して、FIFO(First In First Out、先入れ先出し)の原則を持つデータ構造または抽象データ型はキューである。

探索アルゴリズムでは、スタックを使用すると深さ優先探索となる。
深さ優先探索とは、木やグラフを探索するためのアルゴリズムです。アルゴリズムは、根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行うことを言います。

バックトラックは、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題、制約充足問題の解を探索する戦略の一種のことです。力まかせ探索を改良したものとも言います。

スタックをPythonで実装してみる

# スタック操作を行うクラス
class Stack:
 def __init__(self):
   self.a = []

 # PUSH関数
 # スタックにデータを末尾に追加する。
 # x:スタックに入れるデータ
 def push(self, x):
   self.a.append(x)

 # POP関数
 # スタックに追加されているデータを末尾から削除する。
 # 返り値:listの末尾の要素を削除して返します。
 def pop():
   return self.a.pop()

stack = Stack()

# listに値を追加していく。
stack.push(1)
stack.push(2)

# 削除する値をprintする。
print(stack.pop())
print(stack.pop())

> > 2
    1

# スタック操作を行うクラス

class Stack:

def __init__(self):

self.a = []

# PUSH関数

# スタックにデータを末尾に追加する。

# x:スタックに入れるデータ

def push(self, x):

self.a.append(x)

# POP関数

# スタックに追加されているデータを末尾から削除する。

# 返り値:listの末尾の要素を削除して返します。

def pop():

return self.a.pop()

stack = Stack()

# listに値を追加していく。

stack.push(1)

stack.push(2)

# 削除する値をprintする。

print(stack.pop())

> > 2

ここで新しい用語が出てきた。キューである。
次に、キューを学んでいこう。

ゼロから学ぶ　データ構造　キュー編(queue)

キューの特徴

キューとは、コンピュータで用いられる基本的なデータ構造のひとつです。データを先入れ先出しの構造で保持するものです。英語の頭文字をとって、FIFO（First In First Out）と呼ばれています。
キューは、待ち行列とも言います。

キュー（FIFO、先入れ先出し）の操作

FIFOの操作は、エンキュー（enqueue）とデキュー（dequeue）の2つです。

よく例えに出るのが、ところてん方式で、キューにデータを入れることをエンキュー（enqueue）。キューからデータを取り出すときは最初に入れたデータを押し出すイメージのデキュー（dequeue）と言われています。

その他に、レジの行列やお店の行列が例えられます。どちらも最初に並んでいる人からサービスするということですね。

キューと関連するデータ構造について

FIFO(First In First Out、先入れ先出し)の原則を持つデータ構造または抽象データ型はキューであるのに対して、FILO(First In Last Out、先入れ後出し)の原則を持つデータ構造がスタックである。

探索アルゴリズムでは、キューを使用すると幅優先探索となる。
幅優先探索とは、根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつけるものを言う。

キューをPythonで実装してみた

キューの構造と処理を理解できたのであれば、実際にコードを書いてみましょう。

# キュー操作を行うクラス
class Queue:
    def __init__(self):
        self.a = [0]*10
        self.write_pos = 0
        self.read_pos = 0

    # ENQUEUE関数
    # キューにデータを末尾に追加する。
    # x:キューに入れるデータ
    def enqueue(self, x):
        self.a[self.write_pos] = x
    	self.write_pos += 1

    
    # DEQUEUE関数
    # キューに追加されているデータを先頭から削除する。
    # 返り値:listの先頭尾の要素を削除して返します。
    def dequeue(self):
        b = self.a[self.read_pos]
        for i in range(len(a)):
        	a[i] = a[i+1];
        return b

# キュー操作を行うクラス

class Queue:

def __init__(self):

self.a = [0]*10

self.write_pos = 0

self.read_pos = 0

# ENQUEUE関数

# キューにデータを末尾に追加する。

# x:キューに入れるデータ

def enqueue(self, x):

self.a[self.write_pos] = x

self.write_pos += 1

# DEQUEUE関数

# キューに追加されているデータを先頭から削除する。

# 返り値:listの先頭尾の要素を削除して返します。

def dequeue(self):

b = self.a[self.read_pos]

for i in range(len(a)):

a[i] = a[i+1];

return b

実は、このコード典型的な間違いのコードです。

何が間違っているのか分かりますか？

コードは正常に実行できますし、値も問題ありません。
でも、コードをよーく見てください。
dequeue関数内の処理です。
1文字目を別の変数に取り出して、その次に値をn個、先頭に移動させていますよね？

実は、これが間違いなんです。

何が間違いかというと、今回は10個と限定しているのですが、これが100万個だったらどうしますか？キュー操作するたびに、100万個移動させなければなりません。これって下手するとビジー状態になりシステム不具合なのか見分けが付きにくくなりませんか？

プログラムを組むということは、そういったリスクヘッジは避けるべきです。

これをO(N)バイトオーダーN記法と言われます。
暗黙の了解でこの記法はすべきではないとされています。

そのため、O(1)バイトオーダー１の記法を使うアルゴリズムを書くべきです。

今回の問題は要素をひとつずつ移動させることが問題でしたので、視点を変えてやる必要があります。
つまり、要素を移動するのではなく配列の見方をシフトさせる方法を用いります。
つまり、a[0]→a[1]と言ったように削除したa[0]み見ないで、a[1]から見るのです。

しかし、これをすると削除された先頭が空白になってしまうので、すぐに満タンになるといったデメリットがあり非効率です。

そこで考案されたのが配列の再利用です。
イメージはリング状にすることで、例えば今回 a[10] だったので、空きがあると仮定して、10個目に入る予定の時、0番目に入れるということで、サークル状に利用するものです。

これをリングバッファと呼ばれ、下記を実装していきます。

# キュー操作を行うクラス
class Queue:
    def __init__(self):
        self.a = [0]*10
        self.write_pos = 0
        self.read_pos = 0

    # ENQUEUE関数
    # キューにデータを末尾に追加する。
    # x:キューに入れるデータ
    def enqueue(self, x):
        self.a[self.write_pos] = x
        
        self.write_pos = (self.write_pos+1)%10
        
        if not self.size():
            raise ValueError("これ以上、enqeue できません！")
        
        if self.write_pos == self.read_pos:
            raise ValueError("queue は満タンです！")

    
    # DEQUEUE関数
    # キューに追加されているデータを先頭から削除する。
    # 返り値:listの先頭尾の要素を削除して返します。
    def dequeue(self):
        if self.write_pos == self.read_pos:
            raise ValueError("queueに何も入っていない。")

        b = self.a[self.read_pos]
        self.a[self.read_pos] = 0
        self.read_pos = (self.read_pos+1)%10
        return b

    # SIZE関数
    # キューに追加されているデータを先頭と最後の差分が0かどうかを返す。
    # 返り値:listの先頭と最後の差分を返します。
    def size(self) ->int:
        l = (self.write_pos - self.read_pos) % 10
        return l

# キュー操作を行うクラス

class Queue:

def __init__(self):

self.a = [0]*10

self.write_pos = 0

self.read_pos = 0

# ENQUEUE関数

# キューにデータを末尾に追加する。

# x:キューに入れるデータ

def enqueue(self, x):

self.a[self.write_pos] = x

self.write_pos = (self.write_pos+1)%10

if not self.size():

raise ValueError("これ以上、enqeue できません！")

if self.write_pos == self.read_pos:

raise ValueError("queue は満タンです！")

# DEQUEUE関数

# キューに追加されているデータを先頭から削除する。

# 返り値:listの先頭尾の要素を削除して返します。

def dequeue(self):

if self.write_pos == self.read_pos:

raise ValueError("queueに何も入っていない。")

b = self.a[self.read_pos]

self.a[self.read_pos] = 0

self.read_pos = (self.read_pos+1)%10

return b

# SIZE関数

# キューに追加されているデータを先頭と最後の差分が0かどうかを返す。

# 返り値:listの先頭と最後の差分を返します。

def size(self) ->int:

l = (self.write_pos - self.read_pos) % 10

return l

実際にテストしてみましょう。

# テストケース1
queue = Queue()


for _ in range(5):
    queue.enqueue(_)
    print(queue.dequeue())

print(queue.a)

>> 0
1
2
3
4
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# テストケース1

queue = Queue()

for _ in range(5):

queue.enqueue(_)

print(queue.dequeue())

print(queue.a)

>> 0

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

正しく dequeue できていますね！

# テストケース2
queue = Queue()


for _ in range(10):
    queue.enqueue(_)

print(queue.a)

>> ValueError: これ以上、enqeue できません！

# テストケース2

queue = Queue()

for _ in range(10):

queue.enqueue(_)

print(queue.a)

>> ValueError: これ以上、enqeue できません！

10個目を enqueue したとき、例外が走りました。

# テストケース3
queue = Queue()

for _ in range(8):
    queue.enqueue(_)
    
for _ in range(3):
    queue.dequeue()

for _ in range(3):
    queue.enqueue(_)

print(queue.a)

>> [2, 0, 0, 3, 4, 5, 6, 7, 0, 1]

# テストケース3

queue = Queue()

for _ in range(8):

queue.enqueue(_)

for _ in range(3):

queue.dequeue()

for _ in range(3):

queue.enqueue(_)

print(queue.a)

>> [2, 0, 0, 3, 4, 5, 6, 7, 0, 1]

write_pos < read_pos のときの処理もちゃんとできていますね！
これにより size()関数は正しく動作していると言えます。

これでひとまずは、O(1) バイトオーダー1に対しての実装は完了です。

ここで、あなたはこんな質問をされるかもしれないです。

問
箱は10個あるのに、enqueue()10個目で例外がでるのはおかしいのではないか？11個目のenqueue()で例外がでるべきでは？
これはバグなのではないか？バグでないとしたら理由を。バグなら修正すべきだ。

さて、あなたはどう答えるでしょうか？自明とはいっても納得してくれそうにありません。

POINTは、
if size() == 0 :
raise ValueError(“要素0個”)

であり、
if size() == 10 :
raise ValueError(“要素満タン”)

ということができるかどうかということです。

この解を解くにあたり、size() の値域はいくらになると思いますか？

値域というのは、プログラミングで言うところの関数に渡す戻り値のことです。
また、定義域というのは、引数の変数の取りうる範囲を言います。

これは、簡単ですね。

0 <= size() < 10（size()の返す値は整数）

ですね。これにより、「if size() == 10: とか書いてもsize()は決して10にはならないので期待する動作にはならない。」という証明ができます。

次に、size()が0から10までではなく0から9までしか返せないのはなぜか？
と質問されたらあなたはどう答えるでしょうか？

これを言語化するのは、難しいかもしれませんが、数学的な証明問題としてとらえると分かりやすいかもしれません。

「太郎がa[0]にいると仮定しても一般性を失わない。このとき、花子がいる場所は10箇所しかないので、太郎と花子の組み合わせは10通りしかない。ゆえに、10個の状態しか持ち得ない。これは、size() = 0 , 1, … , 9に対応する。」

これが最適解だと思います。

次に、size()が0から10まで返すように修正しろと強制されたとき、あなたは実装できるでしょうか？

write_pos　と　read_pos　が同じ位置の時、0　or　10　が考えられるのですが、これはどちらがどうか判断できません。
なぜかというと、変数が2つしかないためです。
なので、変数を追加してやると問題は解決できます。

つまり、

enqueue()
   self.size += 1
   
dequeue()
   self.size -= 1
   
size()
   return self.size

enqueue()

self.size += 1

dequeue()

self.size -= 1

size()

return self.size

として、size()で返せばOKです。

これはこれでよく、正解なのですが、メモリ効率の良い実装になったかというと実はそうではありません。一見メモリを節約できたかと思えるかもしれませんが、この実装は、カウンター用の変数を一つ増やして、a[]の使える領域が1つ増えただけなので、メモリ領域は得をしていない。プログラムの行数が増える分だけ損していると思われるのです。

こういった理由により、enqueueが10回目に例外を出すことは、バグではなく当然の実装であると言えるのです。

スタックとキューの違いをまとめてみた！

スタックとキューの違いは、何ですか？

簡単に言うと、データの取り出し方法が違います。
スタックが重ねたお皿を重ねたり取り除いたりする操作に対して、キューは、ところてん方式です。FIFO（先入れ先出し）の原則で操作して、先に入れたデータから処理していきます。

スタックとキューは、配列とどう違うのですか？

配列は、読み書き、read write しかできません。追加や削除といった操作ができないのが特徴です。

スタックとキューは、いつ使われていますか？

スタックの用途

再帰関数の再帰呼び出し
Web ブラウザの訪問履歴 (戻りボタンで pop)
テキストエディタでの Undo 機能

キューの用途

印刷機のジョブスケジューリング
航空券予約のキャンセル待ち処理
ファイル IO などにおける非同期データ転送

がんばらないでプログラマーになる講座

初心者エンジニアみつきタンと成長していこう！

【データ構造】スタック stackとキュー queue【基本講座】

【データ構造】スタック stackとキュー que【基本講座】

ゼロから学ぶ　データ構造　スタック編(stack)

スタックの特徴

抽象データ型としてのスタック

スタックと関連するデータ構造について

スタックをPythonで実装してみる

ゼロから学ぶ　データ構造　キュー編(queue)

キューの特徴

キュー（FIFO、先入れ先出し）の操作

キューと関連するデータ構造について

キューをPythonで実装してみた

スタックとキューの違いをまとめてみた！

スタックとキューの違いは、何ですか？

スタックとキューは、配列とどう違うのですか？

スタックとキューは、いつ使われていますか？

スタックの用途

キューの用途

がんばらないでプログラマーになりたい人向けの学習方法とは？

【スクール】今流行りのプログラミングスクールについて徹底的に調べてみた

【データ構造】スタック stackとキュー que【基本講座】

ゼロから学ぶ データ構造 スタック編(stack)

スタックの特徴

抽象データ型としてのスタック

スタックと関連するデータ構造について

スタックをPythonで実装してみる

ゼロから学ぶ データ構造 キュー編(queue)

キューの特徴

キュー（FIFO、先入れ先出し）の操作

キューと関連するデータ構造について

キューをPythonで実装してみた

スタックとキューの違いをまとめてみた！

スタックとキューの違いは、何ですか？

スタックとキューは、配列とどう違うのですか？

スタックとキューは、いつ使われていますか？

スタックの用途

キューの用途

がんばらないでプログラマーになりたい人向けの学習方法とは？

【スクール】今流行りのプログラミングスクールについて徹底的に調べてみた

ゼロから学ぶ　データ構造　スタック編(stack)

ゼロから学ぶ　データ構造　キュー編(queue)