キュー

Python SELF JA
レベル 52, レッスン 0
使用可能

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
2
タスク
Python SELF JA, レベル 52, レッスン 0
ロック未解除
キューは簡単
キューは簡単
2
タスク
Python SELF JA, レベル 52, レッスン 0
ロック未解除
キューは難しい
キューは難しい
コメント
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION