---
# System prepended metadata

title: 資結筆記｜佇列（Queue）
tags: [資料結構]

---

## 資結筆記｜佇列（Queue）

### 複習

&emsp;&emsp;上次提到了[鏈結串列（linked list）](https://hackmd.io/@fooox0864/BkTd014vyl)這個資料結構，如果還沒看或感興趣的讀者可以去看看唷！

<br/>

### 基本觀念

&emsp;&emsp;<font color="#0000FF">佇列</font>（queue）是一種線性的資料結構，特色是從一端插入資料，另一端讀取資料，資料讀取完後就從佇列中移除。插入資料進佇列稱為<font color="#0000FF">enqueue</font>，讀取資料稱為<font color="#0000FF">dequeue</font>。因為每筆資料都是從佇列的一端進入，從另一段離開，這個過程稱之為<font color="#0000FF">先進先出</font>（Firt In First Out）。佇列可以想像成去餐廳點餐，先點的餐點會先被製作，完成的餐點會被從佇列刪除。
 

 
 ![佇列](https://hackmd.io/_uploads/ryI6klZOyl.png)

<br/>

### 資料插入與讀取
 
&emsp;&emsp;資料的插入和讀取比較簡單，所以不花太多篇幅描寫僅簡單的條列出一些重點
  
1、讀取資料時，<font color="#f00">已讀取</font>的資料會被<font color="#f00">從佇列中移出</font>。
2、必須先讀取先進入的資料，所以<font color="#f00">不能從佇列的中間讀取</font>。
  
<br/>
  
### 佇列程式實作
  
<br/>
  
&emsp;&emsp;我們使用串列模擬佇列的功能，假設從頭部插入資料，可以用python內建insert(0,data)達到enqueue的效果。從尾部讀取資料，使用pop達到dequeue的效果。大家可以自行使用python tutor 跑跑看程式，會更了解佇列的運作。

<br/>


```
  class Queue():
    def __init__(self):
        self.queue = []                 #使用串列模擬
    
    def enqueue(self,data):             #插入資料
        self.queue.insert(0,data)
        
    def dequeue(self):                  #讀取資料
        if len(self.queue):
            return self.queue.pop()
        return "佇列是空的"



q = Queue()
q.enqueue('apple')
q.enqueue('guava')
q.enqueue('banana')

print("讀取佇列：",q.dequeue())
print("讀取佇列：",q.dequeue())
print("讀取佇列：",q.dequeue())
print("讀取佇列：",q.dequeue())
```
<br/>

&emsp;&emsp;以下是輸出的結果，可以看到先輸入的的資料會先被輸出，並且輸出完後會將資料從佇咧移除，所以最後佇列會是空的。
![佇列程式碼實作](https://hackmd.io/_uploads/B1SWPg-O1l.png)

   
### 與佇列有關的python模組
  
<br/>

&emsp;&emsp;除了用陣列模擬佇列之外，也提供一個python內建的模組，可以使用佇列的功能，但因為python tutor 沒有支援這個模組，所以大家可以在自己的電腦安裝python環境和這個模組再試試看，有興趣的讀者不仿可以自己研究看看。

```
from queue import Queue

q = Queue()
for i in range(3):            #輸入0~2至佇列中
    q.put(i)

while not q.empty():
    print(q.get())            #讀取佇列內的資料
```

<br/>

&emsp;&emsp;以下是用電腦的環境輸出的結果，程式碼寫著從0輸入到2進入佇列，然後再一一讀取出來。


![佇列模組實作](https://hackmd.io/_uploads/BJK6wgbukx.png)


  