キューを使う

Pythonで学ぶデータ構造とアルゴリズム

Miriam Antona

Software Engineer

キュー

FIFO： 先入れ先出し
- 最初に追加した要素が、最初に取り出される

キュー

FIFO： 先入れ先出し
- 最初に追加した要素が、最初に取り出される

キュー

FIFO： 先入れ先出し
- 最初に追加した要素が、最初に取り出される

キュー - 構造

料理の名称を含むキューの模式図。

キュー - 構造

料理の名称が付いたキューの模式図。単語「head」はキューの先頭を指している。

先頭：ヘッド（head）

キュー - 構造

料理の名称が付いたキューの模式図。「tail」という単語は、キューの末尾を指している。

先頭：ヘッド（head）
末尾：テール（tail）

キュー - 機能

2つの料理名を含むキューの模式図。「head」という語はキューの先頭を、「tail」という語は末尾を指します。

キュー - 機能

キューの模式図。キューの末尾に新しい要素が挿入されている。

末尾にのみ追加できる
- エンキュー（enqueue）

キュー - 機能

キューの模式図。キューの最初の要素は、削除されるため取り消し線が引かれている。

末尾にのみ追加できる
- エンキュー（enqueue）
先頭からのみ取り出せる

キュー - 機能

キューの模式図。キューには最初の要素が削除されたため、2つの要素だけしかない。

末尾にのみ追加できる
- エンキュー（enqueue）
先頭からのみ取り出せる
- デキュー（dequeue）
その他のキュー：
- 両端キュー
- 循環キュー
- 優先度キュー

キュー - 実際の活用例

プリンターの印刷ジョブ管理
- ドキュメントは受領順に印刷される
リクエストの順番が重要なアプリ
- コンサートのチケット
- タクシー配車サービス

キュー - 作成方法

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Queue:
  def __init__(self):
    self.head = None
    self.tail = None

キュー - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

1つの要素を持つキューの模式図。キューがノードで作成されている。

キュー - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

1つの要素を持つキューの模式図。キューはノードを使用して作成されている。「head」と「tail」という語はノードを指す。

キュー - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:

2つの要素を持つキューの模式図。キューはノードで作成されている。追加する新しいノードが準備されている。

キュー - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node

3つの要素を持つキューの模式図。「tail」という単語が、まだ2番目のノードを指している。

キュー - enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node
    self.tail = new_node

3つの要素を持つキューの模式図。「tail」という語が、最後に挿入されたノードを指している。

キュー - dequeue

3つの要素を持つキューの模式図。「head」という語が最初のノードを指し、「tail」という語が最後のノードを指している。

def dequeue(self):

  if self.head:

キュー - dequeue

3つの要素を持つキューの模式図。「head」と「current_node」は先頭ノードを指し、「tail」は末尾ノードを指している。

def dequeue(self):
  if self.head:
    current_node = self.head

キュー - dequeue

3つの要素を持つキューの模式図。「head」という語は最初のノードを指し、「current_node」という語は2番目の語を指し、「tail」という語は最後のノードを指している。

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next

キュー - dequeue

2つの要素を持つキューの模式図。「head」は最初のノードを指し、「tail」は最後のノードを指している。キューとは別に、「current_node」という単語がそれを指している別のノードがある。

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

キュー - dequeue

「current_node」と「tail」という単語が付いたノードが、1つのノードを指している。単語「head」はnullを指している。

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None


    if self.head == None:

キュー - dequeue

「current_node」という単語が1つのノードを指している。「head」と「tail」という単語は null を指している。

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

    if self.head == None:
      self.tail = None

PythonのSimpleQueue

モジュール：queue
- Queue
- SimpleQueue

import queue


orders_queue = queue.SimpleQueue()


orders_queue.put("Sushi")
orders_queue.put("Lasagna")
orders_queue.put("Paella")


print("The size is: ", orders_queue.qsize())

The size is: 3

print(orders_queue.get())
print(orders_queue.get())
print(orders_queue.get())

Sushi
Lasagna
Paella

print("Empty queue: ", orders_queue.empty())

Empty queue: True

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム