スタックとキュー（LIFOとFIFO）【Algorithm-Data構造入門Ⅲ】

LIFOとFIFOとは

LIFO

LIFO(Last In, First Out)は、最後に追加された要素が最初に取り出されるデータ構造です。これは、例えば本棚に本を積み重ねるようなイメージです。新しい本を最後に追加し、必要なときには一番上の本から取り出します。

FIFO

FIFO(First In, First Out)は、最初に追加された要素が最初に取り出されるデータ構造です。これは、例えば列に並ぶ人々や食料品のレジの待ち行列などのイメージです。最初に並んだ人や商品が最初に処理されるという原則です。

スタックとキュー

スタック

スタックとは

スタックは、LIFOのデータ構造であり、新しい要素がスタックの一番上に追加され、最も新しい要素が最初に取り出されます。

自作関数を使用した例

class Stack:
	def __init__(self):
		self.items = []

	# 	タックの先頭に要素を追加
	def push(self, item):
		self.items.append(item)

	# 	タックの先頭から要素を削除
	def pop(self):
		return self.items.pop()

	# 	タックの先頭の要素を取得
	def peek(self):
		return self.items[-1]

	# 	タックのサイズを取得
	def size(self):
		return len(self.items)

# スタックの使用例
s = Stack()
s.push("A") # スタック: ["A"]
s.push("B") # スタック: ["A", "B"]
s.push("C") # スタック: ["A", "B", "C"]
print("スタックのサイズ:", s.size())  # 出力: 3
print("スタックのトップ:", s.peek())  # 出力: C
print("ポップされた要素:", s.pop())  # 出力: C

collectionsモジュールを使用した例

from collections import deque

# dequeを使用したスタックの例
stack = deque()
stack.append("A")
stack.append("B")
stack.append("C")
print("スタックのサイズ:", len(stack))  # 出力: 3
print("スタックのトップ:", stack[-1])  # 出力: C
print("ポップされた要素:", stack.pop())  # 出力: C

キュー

キューとは

キューは、FIFO（First In, First Out）のデータ構造であり、新しい要素がキューの末尾に追加され、最も古い要素が最初に取り出されます。

自作関数を使用した例

class Queue:
	def __init__(self):
		self.items = []

	# キューの末尾に要素を追加
	def enqueue(self, item):
		self.items.append(item)

	# キューの先頭から要素を削除
	def dequeue(self):
		return self.items.pop(0)

	# キューの先頭の要素を取得
	def size(self):
		return len(self.items)

# キューの使用例
q = Queue()
q.enqueue("A") # キュー: ["A"]
q.enqueue("B") # キュー: ["A", "B"]
q.enqueue("C") # キュー: ["A", "B", "C"]
print("キューのサイズ:", q.size())  # 出力: 3
print("キューの先頭:", q.dequeue())  # 出力: A キュー: ["B", "C"]
print("キューの先頭:", q.dequeue())  # 出力: B キュー: ["C"]

collectionsモジュールを使用した例

from collections import deque

Queue = deque()

# キューの末尾に要素を追加
def enqueue(item):
	Queue.append(item)

# キューの先頭から要素を削除
def dequeue():
	return Queue.popleft()

# キューのサイズを取得
def size():
	return len(Queue)

# キューの使用例
enqueue("A")
enqueue("B")
enqueue("C")
print("キューのサイズ:", size())  # 出力: 3
print("キューの先頭:", dequeue())  # 出力: A
print("キューの先頭:", dequeue())  # 出力: B

まとめ

スタックとキューは、データを一時的に保存し、処理順序を制御するための重要なデータ構造です。Pythonでは、リストやcollectionsモジュールを使用して簡単に実装できます。これらのデータ構造を理解し、適切に活用することで、効率的なアルゴリズムとデータ処理が可能となります。