# Python 及 C++ 雙向佇列 (deque)
> 作者：王一哲
> 日期：2023年8月5日
## 前言
雙向佇列 (double-ended queue, deque) 的性質與佇列很像，但是可以從最前面或最後面填入、取出資料，可以涵蓋 queue 及 stack 的功能。以下是在 Python 及 C++ 的實作方法。
<br />
## Python 方法1：引入 collections 函式庫中的 deque
要先引入函式庫，函式庫的官方說明書在此 [class collections.deque](https://docs.python.org/3/library/collections.html#collections.deque)。
```python
from collections import deque
```
<br />
### 建立雙向佇列
語法為
```python
雙向佇列名稱 = deque(資料, maxlen=長度)
```
如果不輸入資料，會先建立空的雙向佇列，之後再填入資料。maxlen 可以不加，預設值為 None，如果有設定 maxlen，當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去；反之，當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去。以下的程式碼會建立名稱為 q、資料為 \[0, 1, 2\]、maxlen 為3的雙向佇列。
```python
q = deque([0, 1, 2], maxlen=3)
```
如果想要知道 q 的內容，只要用 print 就可以了
```python
print(q)
```
輸出內容為
```python
deque([0, 1, 2], maxlen=3)
```
<br />
### 從最前面填入資料
語法為
```python
雙向佇列名稱.appendleft(資料)
```
當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去，例如以下的程式碼
```python
q = deque([0, 1, 2], maxlen=3)
q.appendleft(3) # q 的內容變為 [3, 0, 1]
```
如果沒有限制雙向佇列最大長度，例如以下的程式碼
```python
q = deque([0, 1, 2])
q.appendleft(3) # q 的內容變為 [3, 0, 1, 2]
```
<br />
### 從最後面填入資料
語法為
```python
雙向佇列名稱.append(資料)
```
當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去，例如以下的程式碼
```python
q = deque([0, 1, 2], maxlen=3)
q.append(3) # q 的內容變為 [1, 2, 3]
```
如果沒有限制雙向佇列最大長度，例如以下的程式碼
```python
q = deque([0, 1, 2])
q.append(3) # q 的內容變為 [0, 1, 2, 3]
```
<br />
### 清除資料
語法為
```python
雙向佇列名稱.clear()
```
不需要加上任何參數，清空資料後雙向佇列長度為 0。
<br />
### 複製雙向佇列
語法為
```python
雙向佇列2 ＝ 雙向佇列1.copy()
```
不需要加上任何參數。
<br />
### 計算雙向佇列中某筆資料的數量
語法為
```python
雙向佇列名稱.count(資料)
```
例如以下的程式碼
```python
q = deque([0, 1, 1, 1, 2])
a = q.count(1) # a 的值為 3
```
<br />
### 從最後面填入多筆資料
語法為
```python
雙向佇列名稱.extend(可迭代的資料)
```
可迭代的資料 (iterable) ，例如串列。當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去，例如以下的程式碼
```python
q = deque([0, 1, 2], maxlen=3)
q.extend([3, 4, 5]) # q 的內容變為 [3, 4, 5]
q.extend([3, 4, 5, 6]) # q 的內容變為 [4, 5, 6]
```
如果沒有限制雙向佇列最大長度，例如以下的程式碼
```python
q = deque([0, 1, 2])
q.extend([3, 4, 5]) # q 的內容變為 [0, 1, 2, 3, 4, 5]
```
<br />
### 從最前面填入多筆資料
語法為
```python
雙向佇列名稱.extendleft(可迭代的資料)
```
可迭代的資料 (iterable) ，例如串列。當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去，例如以下的程式碼
```python
q = deque([0, 1, 2], maxlen=3)
q.extend([3, 4, 5]) # q 的內容變為 [5, 4, 3]
q.extend([3, 4, 5, 6]) # q 的內容變為 [6, 5, 4]
```
如果沒有限制雙向佇列最大長度，例如以下的程式碼
```python
q = deque([0, 1, 2])
q.extend([3, 4, 5]) # q 的內容變為 [5, 4, 3, 0, 1, 2]
```
<br />
### 從雙向佇列中找到指定資料的索引值
語法為
```python
雙向佇列名稱.index(資料, 起點索引值, 終點索引值)
```
起點索引值可省略，預設值為 0。終點索引值可省略，預設值會搜尋到雙向佇列最後一筆資料，搜尋範圍不包含終點索引值。如果有多筆符合的資料，會回傳第一筆待合資料的索引值。如果在雙向佇列找不到指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼
```python
q = deque([0, 1, 2, 2, 4, 5, 6])
a = q.index(2) # 回傳值為 2
b = q.index(2, 3) # 回傳值為 3
c = q.index(6, 1, 6) # 回傳錯誤訊息 ValueError: 6 is not in deque
```
<br />
### 於指定的索引值插入資料
語法為
```python
雙向佇列名稱.insert(索引值, 資料)
```
當雙向佇列已滿且要插入資料時，回傳從最前面填入新資料時，會回傳錯誤訊息 IndexError。例如以下的程式碼
```python
q = deque([0, 1, 2, 3, 4, 5], maxlen=7)
q.insert(3, -1) # q 的內容變為 [0, 1, 2, -1, 3, 4, 5]
q.insert(4, -2) # 回傳錯誤訊息 IndexError: deque already at its maximum size
```
<br />
### 取得雙向佇列最後面的資料
回傳並移除雙向佇列最後面的資料，語法為
```python
雙向佇列名稱.pop()
```
不需要加上任何參數。如果雙向佇列中已經沒有資料，會回傳錯誤訊息 IndexError。例如以下的程式碼
```python
q = deque([0, 1])
a = q.pop() # a 的值為 1
b = q.pop() # b 的值為 0
c = q.pop() # 回傳錯誤訊息 IndexError: pop from an empty deque
```
<br />
### 取得雙向佇列最前面的資料
回傳並移除雙向佇列最前面的資料，語法為
```python
雙向佇列名稱.popleft()
```
不需要加上任何參數。如果雙向佇列中已經沒有資料，會回傳錯誤訊息 IndexError。例如以下的程式碼
```python
q = deque([0, 1])
a = q.pop() # a 的值為 0
b = q.pop() # b 的值為 1
c = q.pop() # 回傳錯誤訊息 IndexError: pop from an empty deque
```
<br />
### 移除雙向佇列指定的資料
移除雙向佇列中指定的資料，如果有多筆同樣的資料，會移除這些資料中的第一筆。語法為
```python
雙向佇列名稱.remove(資料)
```
如果雙向佇列中沒有指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼
```python
q = deque([0, 1, 2, 3, 2, 5])
q.remove(2) # q 的內容變為 [0, 1, 3, 2, 5]
q.remove(2) # q 的內容變為 [0, 1, 3, 5]
q.remove(2) # 回傳錯誤訊息 ValueError: 2 is not in deque
```
<br />
### 反轉雙向佇列中的資料
反轉雙向佇列中的資料，語法為
```python
雙向佇列名稱.reverse()
```
不需要加上任何參數。例如以下的程式碼
```python
q = deque([0, 1, 2, 3, 4, 5])
q.reverse() # q 的內容變為 [5, 4, 3, 2, 1, 0]
```
<br />
### 前後平移雙向佇列中的資料
前後平移雙向佇列中的資料，語法為
```python
雙向佇列名稱.rotate(步數)
```
步數可以省略，預設值為 1。如果步數正的，會將所有資料向右平移指定的步數，如果資料已經超出最後面時會移動到最前面；如果步數正的，改成向左平移。例如以下的程式碼
```python
q = deque([0, 1, 2, 3, 4, 5])
q.rotate() # q 的內容變為 [5, 0, 1, 2, 3, 4]
q.rotate(1) # q 的內容變為 [4, 5, 0, 1, 2, 3]
q.rotate(2) # q 的內容變為 [2, 3, 4, 5, 0, 1]
q.rotate(-1) # q 的內容變為 [3, 4, 5, 0, 1, 2]
q.rotate(-2) # q 的內容變為 [5, 0, 1, 2, 3, 4]
```
<br />
### 回傳雙向佇列最大長度
回傳雙向佇列最大長度，語法為
```python
雙向佇列名稱.maxlen
```
如果沒有設定最大長度，回傳值為 None。例如以下的程式碼
```python
q = deque([0, 1, 2, 3, 4, 5], maxlen=6)
n = q.maxlen # n 的值為 6
q2 = deque([0, 1, 2, 3, 4, 5])
n2 = q.maxlen # n2 的值為 None
```
<br />
### 取得雙向佇列長度
直接使用內建的 len 即可，回傳值格式為 int，語法為
```python
len(雙向佇列名稱)
```
<br />
### 由雙向佇列前方取出所有資料
這是很常用的技巧，假設雙向佇列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 0、1、2、3、4。
```python
while q: # 當雙向佇列中還有資料時繼續執行 while 迴圈
n = q.popleft() # 回傳並移除雙向佇列最前面的資料，回傳的資料指定給變數 n
```
<br />
### 由雙向佇列後方取出所有資料
這是很常用的技巧，假設雙向佇列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。
```python
while q: # 當雙向佇列中還有資料時繼續執行 while 迴圈
n = q.pop() # 回傳並移除雙向佇列最後面的資料，回傳的資料指定給變數 n
```
<br />
## Python 方法2：使用串列 (list)
關於串列的基本操作請看這篇〈[串列](https://hackmd.io/@yizhewang/H1rSL1W8K)〉，以下是把串列當作雙向佇列的方法。
<br />
### 建立空的串列
語法為
```python
串列名稱 = []
```
<br />
### 從最前面填入資料
由於串列沒有 appendleft 這樣的功能，可以使用 insert 代替，語法為
```python
串列名稱.insert(索引值, 資料)
```
如果要從串列最前面填入新資料，就將索引值設定為 0，例如以下的程式碼
```python
q = []
q.insert(0, 0) # q 的內容變為 [0]
q.insert(0, 1) # q 的內容變為 [1, 0]
q.insert(0, 2) # q 的內容變為 [2, 1, 0]
q.insert(1, -1) # q 的內容變為 [2, -1, 1, 0]
```
<br />
### 從最後面填入資料
語法為
```python
串列名稱.append(資料)
```
例如以下的程式碼
```python
q = []
q.append(0) # q 的內容變為 [0]
q.append(1) # q 的內容變為 [0, 1]
q.append(2) # q 的內容變為 [0, 1, 2]
```
<br />
### 清除資料
語法為
```python
串列名稱.clear()
```
不需要加上任何參數，清空資料後串列長度為 0。
<br />
### 複製串列
語法為
```python
串列2 ＝ 串列1.copy()
```
不需要加上任何參數。
<br />
### 計算串列中某筆資料的數量
語法為
```python
串列名稱.count(資料)
```
例如以下的程式碼
```python
q = [0, 1, 1, 1, 2]
a = q.count(1) # a 的值為 3
```
<br />
### 從最後面填入多筆資料
語法為
```python
串列名稱.extend(可迭代的資料)
```
可迭代的資料 (iterable)，例如串列。例如以下的程式碼
```python
q = [0, 1, 2]
q.extend([3, 4, 5]) # q 的內容變為 [0, 1, 2, 3, 4, 5]
```
也可以用 += 代替，例如以下的程式碼
```python
q = [0, 1, 2]
q += [3, 4, 5] # q 的內容變為 [0, 1, 2, 3, 4, 5]
```
<br />
### 從串列中找到指定資料的索引值
語法為
```python
串列名稱.index(資料, 起點索引值, 終點索引值)
```
起點索引值可省略，預設值為 0。終點索引值可省略，預設值會搜尋到雙向佇列最後一筆資料，搜尋範圍不包含終點索引值。如果有多筆符合的資料，會回傳第一筆待合資料的索引值。如果在串列找不到指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼
```python
q = [0, 1, 2, 2, 4, 5, 6]
a = q.index(2) # 回傳值為 2
b = q.index(2, 3) # 回傳值為 3
c = q.index(6, 1, 6) # 回傳錯誤訊息 ValueError: 6 is not in list
```
<br />
### 取得串列最後面的資料
回傳並移除串列最後面的資料，語法為
```python
串列名稱.pop()
```
參數為索引值，預設值為 -1，也就是最後一筆資料。其實 pop 可以回傳串列中任何索引值的資料，在此是為了配合雙向佇列的操作方式，因此省略索引值。例如以下的程式碼
```python
q = [0, 1]
a = q.pop() # a 的值為 1
b = q.pop() # b 的值為 0
c = q.pop() # 回傳錯誤訊息 IndexError: pop from empty list
```
<br />
### 取得串列最前面的資料
回傳並移除串列最前面的資料，語法為
```python
串列名稱.pop(0)
```
參數為索引值，最前面的資料索引值為 0。例如以下的程式碼
```python
q = [0, 1]
a = q.pop(0) # a 的值為 0
b = q.pop(1) # b 的值為 1
c = q.pop() # 回傳錯誤訊息 IndexError: pop from empty list
```
<br />
### 移除串列指定的資料
移除串列中指定的資料，如果有多筆同樣的資料，會移除這些資料中的第一筆。語法為
```python
串列名稱.remove(資料)
```
如果串列中沒有指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼
```python
q = [0, 1, 2, 3, 2, 5]
q.remove(2) # q 的內容變為 [0, 1, 3, 2, 5]
q.remove(2) # q 的內容變為 [0, 1, 3, 5]
q.remove(2) # ValueError: list.remove(x): x not in list
```
<br />
### 反轉串列中的資料
反轉串列中的資料，語法為
```python
串列名稱.reverse()
```
不需要加上任何參數。例如以下的程式碼
```python
q = [0, 1, 2, 3, 4, 5]
q.reverse() # q 的內容變為 [5, 4, 3, 2, 1, 0]
```
<br />
### 取得串列長度
直接使用內建的 len 即可，回傳值格式為 int，語法為
```python
len(串列名稱)
```
<br />
### 由串列前方取出所有資料
這是很常用的技巧，假設串列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 0、1、2、3、4。
```python
while q: # 當串列中還有資料時繼續執行 while 迴圈
n = q.pop(0) # 回傳並移除串列最前面的資料，回傳的資料指定給變數 n
```
<br />
### 由串列後方取出所有資料
這是很常用的技巧，假設串列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。
```python
while q: # 當串列中還有資料時繼續執行 while 迴圈
n = q.pop() # 回傳並移除串列最後面的資料，回傳的資料指定給變數 n
```
<br />
## C++ STL deque 函式庫
要先引入函式庫，函式庫的官方說明書在此 [cplusplus.com std::deque](https://cplusplus.com/reference/deque/deque/)。
```cpp
#include <deque>
```
<br />
### 建立雙向佇列
雙向佇列的資料可以是所有內建的資料格式，例如 int、float、string，也可以使用自訂的資料格式。語法為
```cpp=
// 産生空的雙向佇列
deque<資料格式> 雙向佇列名稱;
// 由雙向佇列2複製資料，也可以改變記憶體位置只複製部分內容
deque<資料格式> 雙向佇列名稱 (雙向佇列2名稱.begin(), 雙向佇列2名稱.end());
// 由雙向佇列2複製資料
deque<資料格式> 雙向佇列名稱 (雙向佇列2名稱);
// 由已定義的陣列複製資料
deque<資料格式> 雙向佇列名稱 (陣列名稱, 陣列名稱 + 陣列長度);
// 産生雙向佇列並指定資料
deque<資料格式> 雙向佇列名稱 {用逗號分隔的資料};
deque<資料格式> 雙向佇列名稱 = {用逗號分隔的資料};
```
例如以下的程式碼
```cpp=
deque<int> q1; // q1 是空的
deque<int> q2 (5, 1); // q2 的內容為 {1, 1, 1, 1, 1}
deque<int> q3 (q2.begin(), q2.end()); // q3 的內容為 {1, 1, 1, 1, 1}
deque<int> q4 (q3); // q4 的內容為 {1, 1, 1, 1, 1}
int data[] = {0, 1, 2, 3, 4};
deque<int> q5 (data, data + sizeof(data)/sizeof(int)); // q5 的內容為 {0, 1, 2, 3, 4}
deque<int> q6 {0, 1, 2, 3, 4}; // q6 的內容為 {0, 1, 2, 3, 4}
deque<int> q7 = {0, 1, 2, 3, 4}; // q7 的內容為 {0, 1, 2, 3, 4}
```
<br />
### 迭代器 iterator
迭代器可以用來取得物件對應的記憶體位址，有以下幾種：
```cpp=
雙向佇列名稱.begin(); // 回傳雙向佇列起點位址
雙向佇列名稱.end(); // 回傳雙向佇列終點位址
雙向佇列名稱.rbegin(); // 回傳雙向佇列終點位址，由後向前向讀取資料
雙向佇列名稱.rend(); // 回傳雙向佇列起點位址，由後向前向讀取資料
雙向佇列名稱.cbegin(); // 回傳雙向佇列起點位址，回傳值為常數
雙向佇列名稱.cend(); // 回傳雙向佇列終點位址，回傳值為常數
雙向佇列名稱.crbegin();// 回傳雙向佇列終點位址，由後向前向讀取資料，回傳值為常數
雙向佇列名稱.crend(); // 回傳雙向佇列起點位址，由後向前向讀取資料，回傳值為常數
```
迭代器的變數名稱通常是 it，寫法有兩種，例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4};
deque<int>::iterator it = q.begin();
auto it = q.begin();
```
但是 deque\<int\>::iterator 只能用在 begin()、end()，還是用 auto 會比較方便。如果要印出雙向佇列中所有的資料，可以配合迭代器處理，例如以下的程式碼
```cpp=
deque<int> q = {0, 1, 2, 3, 4};
for(auto it = q.begin(); it != q.end(); it++)
cout << *it << " \n"[it == q.end()-1]; // 印出的值為 0 1 2 3 4
for(auto it = q.rbegin(); it != q.rend(); it++)
cout << *it << " \n"[it == q.rend()-1]; // 印出的值為 4 3 2 1 0
for(auto it = q.cbegin(); it != q.cend(); it++)
cout << *it << " \n"[it == q.cend()-1]; // 印出的值為 0 1 2 3 4
for(auto it = q.crbegin(); it != q.crend(); it++)
cout << *it << " \n"[it == q.crend()-1]; // 印出的值為 4 3 2 1 0
```
<br />
### 從最前面填入資料
語法為
```cpp
雙向佇列名稱.push_front(資料);
```
例如以下的程式碼
```cpp
deque<int> q;
q.push_front(0); // q 的內容為 {0}
q.push_front(1); // q 的內容為 {1, 0}
q.push_front(2); // q 的內容為 {2, 1, 0}
```
<br />
另一個工具是 emplace_front，語法為
```cpp
雙向佇列名稱.emplace_front(資料);
```
看起來效果和 push_front 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼
```cpp
deque<int> q;
q.emplace_front(0); // q 的內容為 {0}
q.emplace_front(1); // q 的內容為 {1, 0}
q.emplace_front(2); // q 的內容為 {2, 1, 0}
```
<br />
### 從最後面填入資料
語法為
```cpp
雙向佇列名稱.push_back(資料);
```
例如以下的程式碼
```cpp
deque<int> q;
q.push_back(0); // q 的內容為 {0}
q.push_back(1); // q 的內容為 {0, 1}
q.push_back(2); // q 的內容為 {0, 1, 2}
```
<br />
另一個工具是 emplace_back，語法為
```cpp
雙向佇列名稱.emplace_back(資料);
```
看起來效果和 push_back 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼
```cpp
deque<int> q;
q.emplace_back(0); // q 的內容為 {0}
q.emplace_back(1); // q 的內容為 {0, 1}
q.emplace_back(2); // q 的內容為 {0, 1, 2}
```
<br />
### 於指定的位置插入資料
語法為
```cpp
雙向佇列名稱.insert(記憶體位址, 資料);
```
要配合迭代器取得記憶體位址，例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4};
q.insert(q.begin(), -1); // 於最前面插入 -1，q 的內容變為 {-1, 0, 1, 2, 3, 4}
q.insert(q.end(), -2); // 於最後面插入 -2，q 的內容變為 {-1, 0, 1, 2, 3, 4, -2}
q.insert(q.begin()+2, -3); // 於開頭處向後 2 格插入 -3，q 的內容變為 {-1, 0, -3, 1, 2, 3, 4, -2}
q.insert(q.end()-2, -4); // 於結尾處向前 2 格插入 -4，q 的內容變為 {-1, 0, -3, 1, 2, 3, -4, 4, -2}
```
<br />
另一個工具是 emplace，語法為
```cpp
雙向佇列名稱.emplace(記憶體位址, 資料);
```
看起來效果和 instert 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4};
q.emplace(q.begin()+1, -1); // 於開頭處向後 1 格插入 -1，q 的內容變為 {0, -1, 1, 2, 3, 4}
```
<br />
### 刪除最前面的資料
語法為
```cpp
雙向佇列名稱.pop_front();
```
不需要任何參數，沒有回傳值。例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4, 5};
q.pop_front(); // 刪除開頭處的資料，q 的內容變為 {1, 2, 3, 4, 5}
```
如果雙向佇列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼
```cpp
deque<int> q;
q.pop_front();
```
<br />
### 刪除最後面的資料
語法為
```cpp
雙向佇列名稱.pop_back();
```
不需要任何參數，沒有回傳值。例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4, 5};
q.pop_back(); // 刪除開頭處的資料，q 的內容變為 {0, 1, 2, 3, 4}
```
如果雙向佇列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼
```cpp
deque<int> q;
q.pop_back();
```
<br />
### 刪除指定範圍的資料
語法為
```cpp
雙向佇列名稱.erase(起點位址, 終點位址);
```
不包含終點位址。例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4, 5};
q.erase(q.begin()); // 刪除開頭處的資料，q 的內容變為 {1, 2, 3, 4, 5}
q.erase(q.begin(), q.begin()+2); // 刪除開頭處及下 1 格的資料，q 的內容變為 {3, 4, 5}
q.erase(q.begin(), q.end()); // 刪除所有資料
```
<br />
### 清除所有資料
語法為
```cpp
雙向佇列名稱.clear();
```
不需要加上任何參數，清空資料後雙向佇列長度為 0。
<br />
### 交換兩個雙向佇列的資料
語法為
```cpp
雙向佇列名稱1.swap(雙向佇列名稱2);
```
<br />
### 取得最前面的資料
語法為
```cpp
雙向佇列名稱.front();
```
不需要任何參數。例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4, 5};
int a = q.front(); // a 的內容為 0
```
如果雙向佇列是空的，會回傳 0，例如以下的程式碼
```cpp
deque<int> q;
int a = q.front(); // a 的內容為 0
```
<br />
### 取得最後面的資料
語法為
```cpp
雙向佇列名稱.back();
```
不需要任何參數。例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4, 5};
int a = q.back(); // a 的內容為 5
```
如果雙向佇列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼
```cpp
deque<int> q;
int a = q.back();
```
<br />
### 取得指定索引值的資料
語法有兩種，分別為
```cpp
雙向佇列名稱[索引值];
雙向佇列名稱.at(索引值);
```
兩者有點差異，例如以下的程式碼
```cpp
deque<int> q = {0, 1, 2, 3, 4, 5};
int a = q[1]; // a 的內容為 1
int b = q[10]; // 索引值超出範圍，回傳 0
int c = q.at(1); // c 的內容為 1
int d = q.at(10); // 索引值超出範圍，回傳錯誤訊息 std::out_of_range
```
<br />
### 取得雙向佇列長度
語法為
```cpp
雙向佇列名稱.size();
```
不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。
<br />
### 回傳雙向佇列最大長度
語法為
```cpp
雙向佇列名稱.max_size();
```
不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。在我使用的系統中回傳值為 2305843009213693951，為 $2^{61} - 1$。
<br />
### 調整雙向佇列長度
語法為
```cpp
雙向佇列名稱.resize(長度, 資料);
```
將雙向佇列調整成指定長度，資料參數可省略，預設值為 0。例如以下的程式碼
```cpp
deque<int> q {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
q.resize(5); // q 的內容變為 {0, 1, 2, 3, 4}
q.resize(10, -1); // q 的內容變為 {0, 1, 2, 3, 4, -1, -1, -1, -1, -1}
q.resize(15); // q 的內容變為 {0, 1, 2, 3, 4, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0}
```
<br />
### 調整雙向佇列使用的記憶體
語法為
```cpp
雙向佇列名稱.shrink_to_fit();
```
不需要任何參數，沒有回傳值。例如以下的程式碼
```cpp
deque<int> q (100); // q 的內容為 100 個 0
q.resize(10); // q 的內容變為 10 個 0
q.shrink_to_fit(); // 調整 q 使用的記憶體
```
<br />
### 檢查雙向佇列是否為空
語法為
```cpp
雙向佇列名稱.empty();
```
不需要任何參數，如果雙向佇列為空回傳 1，如果有資料回傳 0。
<br />
### 由雙向佇列前方取出所有資料
這是很常用的技巧，假設雙向佇列 q 的內容為 {0, 1, 2, 3, 4}，程式碼通常是以下的寫法，回傳值 n 依序為 0、1、2、3、4。
```cpp
while(!q.empty()) { // 當雙向佇列中還有資料時繼續執行 while 迴圈
int n = q.front(); // 回傳雙向佇列最前面的資料，回傳的資料指定給變數 n
q.pop_front(); // 移除雙向佇列最前面的資料
}
```
<br />
### 由雙向佇列後方取出所有資料
這是很常用的技巧，假設雙向佇列 q 的內容為 {0, 1, 2, 3, 4}，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。
```cpp
while(!q.empty()) { // 當雙向佇列中還有資料時繼續執行 while 迴圈
int n = q.back(); // 回傳雙向佇列最前面的資料，回傳的資料指定給變數 n
q.pop_back(); // 移除雙向佇列最前面的資料
}
```
<br />
## 結語
以上是我目前常用到的雙向佇列功能，如果之後有遇到其它需求會再補充內容。
<br />
## 參考資料
1. [Python 3.11.4 queue — A synchronized queue class](https://docs.python.org/3/library/queue.html)
2. [5.1. More on Lists](https://docs.python.org/3/tutorial/datastructures.html)
3. [cplusplus.com std::deque](https://cplusplus.com/reference/deque/deque/)
---
###### tags:`C++`、`Python`
Sign in with Wallet
Connect another wallet