データ構造とアルゴリズム | ③スタックとキュー

Shogo

2021年3月22日 08:31

こんにちは、現役理系大学生のShogoです！

第３回の内容は、「スタックとキュー」です。

アルゴリズムを勉強する上で、一度は耳にしたことのある言葉ではないでしょうか。実際この形式は、コンピュータ上でよく使われています。例えば、webページのブラウザバックをする際に用いられています。

今回は、そんな「スタックとキュー」を詳しく説明していきます！

6-1 スタックとキューとは

スタック（stack）とは、積み重ねるという意味です。

例として、輪投げを想像してください。輪投げは、的にいれたら輪が積み重なっていきますよね。的から輪をなくしたい場合は、上から１つずつとりだします。

このようにスタックは、後に入れたものが先に取り出されます。これを「LIFO（Last In First Out）」といいます。

キュー（queue）とは、待ち行列という意味です。このときの行列という意味は、数学的な行列ではなく、コンビニやラーメン屋で並ぶという意味での行列です。

例として、ダルマ落としを想像してください。あたりまえですが、ダルマ落としは下から積んでいきますよね。そして、胴体は一番下から飛ばします。

このようにキューは、先に入れたものが先に取り出されます。これを「FIFO（First In First Out）」といいます。

✅共通した操作

スタックとキューに共通した操作は、追加する操作と取り出す操作です。

前者は、要素をデータ構造に追加するという操作です。輪投げでいうと輪を的に入れる、ダルマ落としでいうと積み木を積むという操作です。

対して後者は、要素をデータ構造から取り出すという操作です。輪投げでいうと輪を取り出す、ダルマ落としでいうと積み木を叩くという操作です。

6-2 スタックをコードで解説

先程例であげた輪投げ（quoits）を用いて、スタックをコードで説明していきます。

✅的を用意する

class Quoits(object):
   def __init__(self):
       self.stack = [] # 的を用意する

quoits = Quoits()
print(quoits.stack)

# 出力結果
>> []

「quoits = Quoits()」で初期値である「__init__」が呼び出されます。したがって、輪投げの的となる「[]」が出力されます。

✅輪を投げる

続いて、輪をひとつずつ投げ、的となる「[]」に入れていきます。

class Quoits(object):
   def __init__(self):
       self.stack = []
       
   def push(self, ring):
       self.stack.append(ring) # 輪を的に入れる

# 的を用意する
quoits = Quoits()
print(quoits.stack)

# 輪を的に入れる 
quoits.push(0)
print(quoits.stack)
quoits.push(1)
print(quoits.stack)
quoits.push(2)
print(quoits.stack)

# 出力結果
>> []
>> [0]
>> [0, 1]
>> [0, 1, 2]

要素を追加する場合は、「quoits.push()」を使います。「quoits.push()」の「()」の値を変えることで、ひとつずつ的に値を入れていけます。

✅輪をひとつずつ片付ける

最後に、輪をひとつずつ片付けます。

class Quoits(object):
   def __init__(self):
       self.stack = []
       
   def push(self, ring):
       self.stack.append(ring)
       
   def pop(self):
       if self.stack:
           return self.stack.pop() # 輪をひとつずつ片付ける

# 的を用意する
quoits = Quoits()

# 輪を的に入れる
quoits.push(0)
quoits.push(1)
quoits.push(2)
print(quoits.stack)

# 輪をひとつずつ片付ける
quoits.pop()
print(quoits.stack)
quoits.pop()
print(quoits.stack)
quoits.pop()
print(quoits.stack)

# 出力結果
>> [0, 1, 2]
>> [0, 1]
>> [0]
>> []

要素を取り出す場合は、「quoits.pop()」を使います。「quoits.pop()」を記述することで、ひとつずつ要素を取り出すことができます。

✅「__init__」?「def」?「class」?

もしここででた「__init__」や「def」、「class」がわからない方は、こちらの記事を見てください！

6-3 キューをコードで解説

同様に、先程例であげたダルマ落とし（daruma otoshi / daruma doll drop）を用いて、キューをコードで説明していきます。

✅安定した土台を用意する

class DarumaOtoshi(object):
   def __init__(self):
       self.queue = []
       
# 安定した土台を用意する
darumaotoshi = DarumaOtoshi()
print(darumaotoshi.queue)

# 出力結果
>> []

「darumaotoshi = DarumaOtoshi()」で初期値である「__init__」が呼び出されます。したがって、安定した土台である「[]」が出力されます。

✅ダルマの胴体を積む

class DarumaOtoshi(object):
   def __init__(self):
       self.queue = []
       
   def enqueue(self, block):
       self.queue.append(block)

# 安定した土台を用意する
darumaotoshi = DarumaOtoshi()
print(darumaotoshi.queue)

# ダルマの胴体を積む
darumaotoshi.enqueue(0)
print(darumaotoshi.queue)
darumaotoshi.enqueue(1)
print(darumaotoshi.queue)
darumaotoshi.enqueue(2)
print(darumaotoshi.queue)

# 出力結果
>> []
>> [0]
>> [0, 1]
>> [0, 1, 2]

スタックとやることは一緒ですが、要素を追加する場合は、「darumaotoshi.enqueue()」を使います。「darumaotoshi.enqueue()」の「()」の値によって、ひとつずつ木を積んでいます。

✅積み木を弾く

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

   def enqueue(self, block):
       self.queue.append(block)

   def dequeue(self):
       if len(self.queue) == 0:
           return None
       result = self.queue[0]
       del self.queue[0]
       return result

# 安定した土台を用意する
darumaotoshi = DarumaOtoshi()

# ダルマの胴体を積む
darumaotoshi.enqueue(0)
darumaotoshi.enqueue(1)
darumaotoshi.enqueue(2)
print(darumaotoshi.queue)

# 積み木を弾く
darumaotoshi.dequeue()
print(darumaotoshi.queue)
darumaotoshi.dequeue()
print(darumaotoshi.queue)
darumaotoshi.dequeue()
print(darumaotoshi.queue)
darumaotoshi.dequeue()

# 出力結果
>> [0, 1, 2]
>> [1, 2]
>> [2]
>> []

要素を取り出す場合は、「darumaotoshi.dequeue()」を使います。この点は、スタックと異なるところです。0→1→2と順番に積んだ木を0から順に弾いていきます。

6-4 ライブラリで簡略化

今挙げたスタックとキューは、わざわざ長いコードを書かなくても実行することができます。

from collections import deque

# スタック
s = deque()

# 要素の追加
s.append(0)
s.append(1)
s.append(2)
print(s)

# 要素の取り出し
s.pop()
print(s)
s.pop()
print(s)
s.pop()
print(s)

# 出力結果
>> deque([0, 1, 2])
>> deque([0, 1])
>> deque([0])
>> deque([])

「from collections import deque」でライブラリを使うことで、スタックを実行できます。

また、使っている関数は違いますが、キューも同じように簡略化できます。

from collections import deque

# キュー
q = deque()

# 要素の追加
q.append(0)
q.append(1)
q.append(2)
print(q)

# 要素の取り出し
q.popleft()
print(q)
q.popleft()
print(q)
q.popleft()
print(q)

# 出力結果
>> deque([0, 1, 2])
>> deque([1, 2])
>> deque([2])
>> deque([])

まとめ

いかがだったでしょうか。

今回は、「スタックとキュー」についてお話しました。

スタックとキューは、大学の授業や情報系の試験で頻出する内容なので、ぜひここで理解しておいてください！

質問や訂正があれば、遠慮なくこの記事にコメント、もしくは、TwitterにDMをしてください！(@shogo_python)

今回の記事が"いいね！"と思ってくれた方は、スキとフォローをよろしくおねがいします！

では、またの機会にお会いしましょう！

データ構造とアルゴリズム入門講座一覧はこちらから

＜参考文献＞
「スタックとキュー　パソコン初心者講座」〈https://www.pc-master.jp/words/stack-queue.html〉