使用队列

Python 中的数据结构与算法

Miriam Antona

Software Engineer

队列

  • FIFO：先进先出

    • 先插入的项会先被移除

      超市排队的照片，队伍中有三个人。

Python 中的数据结构与算法

队列

  • FIFO：先进先出

    • 先插入的项会先被移除

      超市排队的照片，因第一个人离队，队伍中剩两人。

Python 中的数据结构与算法

队列

  • FIFO：先进先出

    • 先插入的项会先被移除

      超市排队的照片，因前两人离队，队伍中剩一人。

Python 中的数据结构与算法

队列 - 结构

一个包含多种国际菜名的队列示意图。

Python 中的数据结构与算法

队列 - 结构

一个包含多种国际菜名的队列示意图。单词"head"指向队首。

  • 开始：head
Python 中的数据结构与算法

队列 - 结构

一个包含多种国际菜名的队列示意图。单词"tail"指向队尾。

  • 开始：head
  • 末尾：tail
Python 中的数据结构与算法

队列 - 特性

一个包含两道国际菜名的队列示意图。单词"head"指向队首，"tail"指向队尾。

Python 中的数据结构与算法

队列 - 特性

队列示意图。一个新元素被插入到队尾。

  • 只能在末尾进行插入
    • Enqueue
Python 中的数据结构与算法

队列 - 特性

队列示意图。队首元素将被移除，因此被划掉。

  • 只能在末尾进行插入
    • Enqueue
  • 只能从队首进行移除
Python 中的数据结构与算法

队列 - 特性

队列示意图。队列只有两个元素，因为第一个元素被移除了。

  • 只能在末尾进行插入
    • Enqueue
  • 只能从队首进行移除
    • Dequeue
  • 其他队列类型：
    • 双端队列
    • 循环队列
    • 优先队列
Python 中的数据结构与算法

队列 - 真实用例

  • 打印机的打印任务
    • 文档按接收顺序打印
  • 请求顺序重要的应用
    • 演唱会购票
    • 出租车服务
Python 中的数据结构与算法

队列 - 实现

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

class Queue:
  def __init__(self):
    self.head = None
    self.tail = None
Python 中的数据结构与算法

队列 - 入队（enqueue）

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

一个含有一个元素的队列示意图。该队列用一个节点实现。

Python 中的数据结构与算法

队列 - 入队（enqueue）

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

一个含有一个元素的队列示意图。该队列用一个节点实现。单词"head"和"tail"指向该节点。

Python 中的数据结构与算法

队列 - 入队（enqueue）

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

  else:

一个含有两个元素的队列示意图。该队列由节点实现。一个新节点将被插入。

Python 中的数据结构与算法

队列 - 入队（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

一个含有三个元素的队列示意图。单词"tail"仍指向第二个节点。

Python 中的数据结构与算法

队列 - 入队（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

一个含有三个元素的队列示意图。单词"tail"指向最后插入的节点。

Python 中的数据结构与算法

队列 - 出队（dequeue）

一个含有三个元素的队列示意图。"head"指向第一个节点，"tail"指向最后一个节点。

def dequeue(self):

  if self.head:
Python 中的数据结构与算法

队列 - 出队（dequeue）

一个含有三个元素的队列示意图。"head"和"current_node"指向第一个节点，"tail"指向最后一个节点。

def dequeue(self):
  if self.head:
    current_node = self.head
Python 中的数据结构与算法

队列 - 出队（dequeue）

一个含有三个元素的队列示意图。"head"指向第一个节点，"current_node"指向第二个节点，"tail"指向最后一个节点。

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
Python 中的数据结构与算法

队列 - 出队（dequeue）

一个含有两个元素的队列示意图。"head"指向第一个节点，"tail"指向最后一个节点。队列外还有一个节点，标注为"current_node"。

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None
Python 中的数据结构与算法

队列 - 出队（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:
Python 中的数据结构与算法

队列 - 出队（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 中的数据结构与算法

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 中的数据结构与算法

Passons à la pratique !

Python 中的数据结构与算法

Preparing Video For Download...