キューの操作

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」が同じノードを指す図。「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」を指すノードの図。「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で学ぶデータ構造とアルゴリズム