7.1 キューの定義とその特性
キュー は、"最初に来たものが最初に出て行く" (First In, First Out, FIFO) という原則に基づいて整理された要素の集まりを表す抽象データ構造だよ。スーパーマーケットの列を考えてみて、一番前の人が一番最初にサービスを受けるって感じ。
キューの特性:
- FIFO (First In, First Out): 最初に追加された要素が最初に削除されるものだよ。
- 制限された操作: キューがサポートする操作は限られていて、追加 (enqueue)、削除 (dequeue)、そして先頭の要素を見る (peek) くらい。
- 一方向アクセス: 要素にアクセスできるのは前(front)と後ろ(rear)だけなんだ。
- 簡単な実装: キューは配列やリンクリストを使って簡単に実装できるよ。
FIFOの働き方:
- 要素の追加 (enqueue): 新しい要素はキューの末尾に追加されるよ。
- 要素の削除 (dequeue): 最初に追加された要素がキューの先頭から削除されるんだ。
- 先頭要素の確認 (peek): キューの先頭にある要素を削除せずに見ることができるよ。
キューの要素は片方の端(後ろ)から追加され、もう片方の端(前)から削除されるんだ。つまり、最初に追加された要素が最初に削除されるってこと。
7.2 基本的な操作
基本的な操作: enqueue, dequeue, peek
操作 enqueue: 新しい要素をキューの末尾に追加するよ。
時間計算量: O(1)。
from collections import deque
queue = deque()
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
print(queue) # 出力: deque([10, 20])
操作 dequeue: 要素を削除してキューの先頭から返すよ。
時間計算量: O(1)。
from collections import deque
queue = deque()
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
print(queue) # 出力: deque([10, 20])
front_element = queue.popleft() # dequeue
print(front_element) # 出力: 10
print(queue) # 出力: deque([20])
操作 peek: キューの先頭にある要素を削除せずに返すよ。
時間計算量: O(1)。
from collections import deque
queue = deque()
queue.append(10) # enqueue 10
queue.append(20) # enqueue 20
print(queue) # 出力: deque([10, 20])
front_element = queue[0] # peek
print(front_element) # 出力: 10
7.3 キューの利用例
いくつかのキューの利用例を見てみよう。
1 プリンタのジョブ管理
キューはプリンターのジョブを管理するのにも使われるよ。ドキュメントはキューに追加され、届いた順番で印刷されるんだ。
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_job(self, job):
self.queue.append(job)
def print_job(self):
if self.queue:
job = self.queue.popleft()
print(f"Printing: {job}")
# 使用例:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job() # 出力: Printing: Document1.pdf
printer_queue.print_job() # 出力: Printing: Document2.pdf
2 ウェブサーバーでのリクエスト処理
キューはウェブサーバーに届いたクライアントのリクエストを管理するのにも使われるよ。リクエストは届いた順番で処理されるんだ。
class RequestQueue:
def __init__(self):
self.queue = deque()
def add_request(self, request):
self.queue.append(request)
def process_request(self):
if self.queue:
request = self.queue.popleft()
print(f"Processing request: {request}")
# 使用例:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request() # 出力: Processing request: GET /index.html
request_queue.process_request() # 出力: Processing request: POST /submit-form
3 メッセージングシステムでのメッセージキュー
キューはメッセージングシステム(例えば、メッセージブローカー)でのメッセージ管理にも使われるよ。メッセージは届いた順番で処理されるんだ。
class MessageQueue:
def __init__(self):
self.queue = deque()
def send_message(self, message):
self.queue.append(message)
def receive_message(self):
if self.queue:
message = self.queue.popleft()
print(f"Received message: {message}")
# 使用例:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message() # 出力: Received message: Hello
message_queue.receive_message() # 出力: Received message: World
GO TO FULL VERSION