スタック(Stack)とキュー(Queue)は自分の知るがぎり簡単な部類のデータ構造ですが、どっちがどっちか間違いやすく意外と厄介です。この記事でっはその違いを簡単に紹介できればと思います。
スタック(Stack)とキュー(Queue)の違い
違いを一言で言うと、スタック(Stack)は筒で、キュー(Queue)は列です。
スタック(Stack)は筒で中に一度入れると取り出すのは筒の上にあるもの、すなわち最後に入れたものになります。
キュー(Queue)は列で最初に並んだ人が最初に呼ばれ(取り出され)ます。
スタック (Stack):
スタックは、「最後に入ったものが最初に出る」(Last In, First Out; LIFO)という原則に従ったデータ構造です。
スタックに要素を追加する操作を「プッシュ」(push)、要素を取り出す操作を「ポップ」(pop)と呼びます。
これは、物理的な積み重ね(例えば、皿の山)と考えるとわかりやすいです。最後に積み上げた皿が、最初に取り出されます。
class Stack():
def __init__(self):
self.stackList = []
def push(self, element):
self.stackList.append(element)
def remove(self):
self.stackList.pop()
def show(self):
print(self.stackList)
stack = Stack()
stack.push(1) # スタックに1を追加
stack.push(5) # スタックに5を追加
stack.push(7) # スタックに7を追加
stack.show() # スタックの状態を表示 ([1, 5, 7])
stack.remove() # スタックから最後に追加された要素(7)を削除
stack.show() # スタックの状態を表示 ([1, 5])
Stack
クラスが定義され、その中にpush
、remove
、show
というメソッドが定義されています。
push
: スタックに要素を追加します。remove
: スタックから最後に追加された要素を削除します。ただし、このメソッドは削除された要素を返さないので、pop
と名付ける方が一般的かもしれません。show
: スタックの現在の状態を表示します。
このremoveが最後に追加した要素を取り出すことから、「最後に入ったものが最初に出る」が実装されています。
キュー (Queue):
キューは、「最初に入ったものが最初に出る」(First In, First Out; FIFO)という原則に従ったデータ構造です。
キューに要素を追加する操作を「エンキュー」(enqueue)、要素を取り出す操作を「デキュー」(dequeue)と呼びます。
これは、物理的な行列(例えば、チケット売り場の列)と考えるとわかりやすいです。最初に列に並んだ人が、最初にサービスを受けるでしょう。
class Queue():
def __init__(self):
self.stackList = []
def enqueue(self, element):
self.stackList.append(element)
def dequeue(self):
self.stackList.pop(0)
def show(self):
print(self.stackList)
queue = Queue()
queue.enqueue(1) # キューに1を追加
queue.enqueue(5) # キューに5を追加
queue.enqueue(7) # キューに7を追加
queue.show() # キューの状態を表示 ([1, 5, 7])
queue.dequeue() # キューから最初に追加された要素(1)を削除
queue.show() # キューの状態を表示 ([5, 7])
Queue
クラスが定義され、その中にenqueue
、dequeue
、およびshow
というメソッドが定義されています。
enqueue
: キューの末尾に要素を追加します。dequeue
: キューの先頭から要素を削除します。ただし、このメソッドは削除された要素を返さないので、一般的なキューの実装では削除された要素を返します。show
: キューの現在の状態を表示します。
dequeuueでリストの一番最初に追加した要素を取り出すことで、「最初に入ったものが最初に出る」が実装されています。