操作佇列

Data Structures and Algorithms in Python

Miriam Antona

Software Engineer

佇列（Queues）

FIFO： 先進先出
- 最先插入的項目會最先被移除

佇列（Queues）

FIFO： 先進先出
- 最先插入的項目會最先被移除

佇列（Queues）

FIFO： 先進先出
- 最先插入的項目會最先被移除

佇列—結構

佇列示意圖，包含多道國際料理名稱。

佇列—結構

佇列示意圖，包含多道國際料理名稱。「head」指向佇列的起始端。

起始端：head

佇列—結構

佇列示意圖，包含多道國際料理名稱。「tail」指向佇列的末端。

起始端：head
末端：tail

佇列—特性

佇列示意圖，包含兩道國際料理名稱。「head」指向起始端，「tail」指向末端。

佇列—特性

佇列示意圖。新元素已插入佇列末端。

只能在末端進行插入
- Enqueue

佇列—特性

佇列示意圖。第一個元素被劃掉，代表將被移除。

只能在末端進行插入
- Enqueue
只能從起始端進行移除

佇列—特性

佇列示意圖。因第一個元素被移除，佇列只剩兩個元素。

只能在末端進行插入
- 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:

只有一個元素的佇列示意圖。以節點實作佇列。

佇列—enqueue

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

只有一個元素的佇列示意圖。以節點實作，"head" 與 "tail" 指向同一節點。

佇列—enqueue

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

  else:

有兩個元素的佇列示意圖。以節點實作，準備插入新節點。

佇列—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" 仍指向第二個節點。

佇列—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" 指向最後插入的節點。

佇列—dequeue

有三個元素的佇列示意圖。"head" 指向第一個節點，"tail" 指向最後一個節點。

def dequeue(self):

  if self.head:

佇列—dequeue

有三個元素的佇列示意圖。"head" 與 "current_node" 指向第一個節點，"tail" 指向最後一個節點。

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

佇列—dequeue

有三個元素的佇列示意圖。"head" 指向第一個節點，"current_node" 指向第二個節點，"tail" 指向最後一個節點。

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

佇列—dequeue

有兩個元素的佇列示意圖。"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

一起來練習吧！

Data Structures and Algorithms in Python