一個地球人在臺北: Python 及 C++ 雙向佇列 (deque)

作者：王一哲
日期：2023年8月5日

前言

雙向佇列 (double-ended queue, deque) 的性質與佇列很像，但是可以從最前面或最後面填入、取出資料，可以涵蓋 queue 及 stack 的功能。以下是在 Python 及 C++ 的實作方法。

Python 方法1：引入 collections 函式庫中的 deque

要先引入函式庫，函式庫的官方說明書在此 class collections.deque。

from collections import deque

建立雙向佇列

語法為

雙向佇列名稱 = deque(資料, maxlen=長度)

如果不輸入資料，會先建立空的雙向佇列，之後再填入資料。maxlen 可以不加，預設值為 None，如果有設定 maxlen，當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去；反之，當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去。以下的程式碼會建立名稱為 q、資料為 [0, 1, 2]、maxlen 為3的雙向佇列。

q = deque([0, 1, 2], maxlen=3)

如果想要知道 q 的內容，只要用 print 就可以了

print(q)

輸出內容為

deque([0, 1, 2], maxlen=3)

從最前面填入資料

語法為

雙向佇列名稱.appendleft(資料)

當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去，例如以下的程式碼

q = deque([0, 1, 2], maxlen=3)
q.appendleft(3)  # q 的內容變為 [3, 0, 1]

如果沒有限制雙向佇列最大長度，例如以下的程式碼

q = deque([0, 1, 2])
q.appendleft(3)  # q 的內容變為 [3, 0, 1, 2]

從最後面填入資料

語法為

雙向佇列名稱.append(資料)

當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去，例如以下的程式碼

q = deque([0, 1, 2], maxlen=3)
q.append(3)  # q 的內容變為 [1, 2, 3]

如果沒有限制雙向佇列最大長度，例如以下的程式碼

q = deque([0, 1, 2])
q.append(3)  # q 的內容變為 [0, 1, 2, 3]

清除資料

語法為

雙向佇列名稱.clear()

不需要加上任何參數，清空資料後雙向佇列長度為 0。

複製雙向佇列

語法為

雙向佇列2 ＝ 雙向佇列1.copy()

不需要加上任何參數。

計算雙向佇列中某筆資料的數量

語法為

雙向佇列名稱.count(資料)

例如以下的程式碼

q = deque([0, 1, 1, 1, 2])
a = q.count(1)  # a 的值為 3

從最後面填入多筆資料

語法為

雙向佇列名稱.extend(可迭代的資料)

可迭代的資料 (iterable) ，例如串列。當雙向佇列已滿且要從最後面填入新資料時，會將最前面的資料推出去，例如以下的程式碼

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]

如果沒有限制雙向佇列最大長度，例如以下的程式碼

q = deque([0, 1, 2])
q.extend([3, 4, 5])     # q 的內容變為 [0, 1, 2, 3, 4, 5]

從最前面填入多筆資料

語法為

雙向佇列名稱.extendleft(可迭代的資料)

可迭代的資料 (iterable) ，例如串列。當雙向佇列已滿且要從最前面填入新資料時，會將最後面的資料推出去，例如以下的程式碼

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]

如果沒有限制雙向佇列最大長度，例如以下的程式碼

q = deque([0, 1, 2])
q.extend([3, 4, 5])     # q 的內容變為 [5, 4, 3, 0, 1, 2]

從雙向佇列中找到指定資料的索引值

語法為

雙向佇列名稱.index(資料, 起點索引值, 終點索引值)

起點索引值可省略，預設值為 0。終點索引值可省略，預設值會搜尋到雙向佇列最後一筆資料，搜尋範圍不包含終點索引值。如果有多筆符合的資料，會回傳第一筆待合資料的索引值。如果在雙向佇列找不到指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼

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

於指定的索引值插入資料

語法為

雙向佇列名稱.insert(索引值, 資料)

當雙向佇列已滿且要插入資料時，回傳從最前面填入新資料時，會回傳錯誤訊息 IndexError。例如以下的程式碼

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

取得雙向佇列最後面的資料

回傳並移除雙向佇列最後面的資料，語法為

雙向佇列名稱.pop()

不需要加上任何參數。如果雙向佇列中已經沒有資料，會回傳錯誤訊息 IndexError。例如以下的程式碼

q = deque([0, 1])
a = q.pop()   # a 的值為 1
b = q.pop()   # b 的值為 0
c = q.pop()   # 回傳錯誤訊息 IndexError: pop from an empty deque

取得雙向佇列最前面的資料

回傳並移除雙向佇列最前面的資料，語法為

雙向佇列名稱.popleft()

不需要加上任何參數。如果雙向佇列中已經沒有資料，會回傳錯誤訊息 IndexError。例如以下的程式碼

q = deque([0, 1])
a = q.pop()   # a 的值為 0
b = q.pop()   # b 的值為 1
c = q.pop()   # 回傳錯誤訊息 IndexError: pop from an empty deque

移除雙向佇列指定的資料

移除雙向佇列中指定的資料，如果有多筆同樣的資料，會移除這些資料中的第一筆。語法為

雙向佇列名稱.remove(資料)

如果雙向佇列中沒有指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼

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

反轉雙向佇列中的資料

反轉雙向佇列中的資料，語法為

雙向佇列名稱.reverse()

不需要加上任何參數。例如以下的程式碼

q = deque([0, 1, 2, 3, 4, 5])
q.reverse()   # q 的內容變為 [5, 4, 3, 2, 1, 0]

前後平移雙向佇列中的資料

前後平移雙向佇列中的資料，語法為

雙向佇列名稱.rotate(步數)

步數可以省略，預設值為 1。如果步數正的，會將所有資料向右平移指定的步數，如果資料已經超出最後面時會移動到最前面；如果步數正的，改成向左平移。例如以下的程式碼

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]

回傳雙向佇列最大長度

回傳雙向佇列最大長度，語法為

雙向佇列名稱.maxlen

如果沒有設定最大長度，回傳值為 None。例如以下的程式碼

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

取得雙向佇列長度

直接使用內建的 len 即可，回傳值格式為 int，語法為

len(雙向佇列名稱)

由雙向佇列前方取出所有資料

這是很常用的技巧，假設雙向佇列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 0、1、2、3、4。

while q:             # 當雙向佇列中還有資料時繼續執行 while 迴圈
    n = q.popleft()  # 回傳並移除雙向佇列最前面的資料，回傳的資料指定給變數 n

由雙向佇列後方取出所有資料

這是很常用的技巧，假設雙向佇列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。

while q:             # 當雙向佇列中還有資料時繼續執行 while 迴圈
    n = q.pop()      # 回傳並移除雙向佇列最後面的資料，回傳的資料指定給變數 n

Python 方法2：使用串列 (list)

關於串列的基本操作請看這篇〈串列〉，以下是把串列當作雙向佇列的方法。

建立空的串列

語法為

串列名稱 = []

從最前面填入資料

由於串列沒有 appendleft 這樣的功能，可以使用 insert 代替，語法為

串列名稱.insert(索引值, 資料)

如果要從串列最前面填入新資料，就將索引值設定為 0，例如以下的程式碼

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]

從最後面填入資料

語法為

串列名稱.append(資料)

例如以下的程式碼

q = []
q.append(0)   # q 的內容變為 [0]
q.append(1)   # q 的內容變為 [0, 1]
q.append(2)   # q 的內容變為 [0, 1, 2]

清除資料

語法為

串列名稱.clear()

不需要加上任何參數，清空資料後串列長度為 0。

複製串列

語法為

串列2 ＝ 串列1.copy()

不需要加上任何參數。

計算串列中某筆資料的數量

語法為

串列名稱.count(資料)

例如以下的程式碼

q = [0, 1, 1, 1, 2]
a = q.count(1)  # a 的值為 3

從最後面填入多筆資料

語法為

串列名稱.extend(可迭代的資料)

可迭代的資料 (iterable)，例如串列。例如以下的程式碼

q = [0, 1, 2]
q.extend([3, 4, 5]) # q 的內容變為 [0, 1, 2, 3, 4, 5]

也可以用 += 代替，例如以下的程式碼

q = [0, 1, 2]
q += [3, 4, 5]      # q 的內容變為 [0, 1, 2, 3, 4, 5]

從串列中找到指定資料的索引值

語法為

串列名稱.index(資料, 起點索引值, 終點索引值)

起點索引值可省略，預設值為 0。終點索引值可省略，預設值會搜尋到雙向佇列最後一筆資料，搜尋範圍不包含終點索引值。如果有多筆符合的資料，會回傳第一筆待合資料的索引值。如果在串列找不到指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼

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

取得串列最後面的資料

回傳並移除串列最後面的資料，語法為

串列名稱.pop()

參數為索引值，預設值為 -1，也就是最後一筆資料。其實 pop 可以回傳串列中任何索引值的資料，在此是為了配合雙向佇列的操作方式，因此省略索引值。例如以下的程式碼

q = [0, 1]
a = q.pop()   # a 的值為 1
b = q.pop()   # b 的值為 0
c = q.pop()   # 回傳錯誤訊息 IndexError: pop from empty list

取得串列最前面的資料

回傳並移除串列最前面的資料，語法為

串列名稱.pop(0)

參數為索引值，最前面的資料索引值為 0。例如以下的程式碼

q = [0, 1]
a = q.pop(0)  # a 的值為 0
b = q.pop(1)  # b 的值為 1
c = q.pop()   # 回傳錯誤訊息 IndexError: pop from empty list

移除串列指定的資料

移除串列中指定的資料，如果有多筆同樣的資料，會移除這些資料中的第一筆。語法為

串列名稱.remove(資料)

如果串列中沒有指定的資料，會回傳錯誤訊息 ValueError。例如以下的程式碼

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

反轉串列中的資料

反轉串列中的資料，語法為

串列名稱.reverse()

不需要加上任何參數。例如以下的程式碼

q = [0, 1, 2, 3, 4, 5]
q.reverse()   # q 的內容變為 [5, 4, 3, 2, 1, 0]

取得串列長度

直接使用內建的 len 即可，回傳值格式為 int，語法為

len(串列名稱)

由串列前方取出所有資料

這是很常用的技巧，假設串列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 0、1、2、3、4。

while q:          # 當串列中還有資料時繼續執行 while 迴圈
    n = q.pop(0)  # 回傳並移除串列最前面的資料，回傳的資料指定給變數 n

由串列後方取出所有資料

這是很常用的技巧，假設串列 q 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。

while q:          # 當串列中還有資料時繼續執行 while 迴圈
    n = q.pop()   # 回傳並移除串列最後面的資料，回傳的資料指定給變數 n

C++ STL deque 函式庫

要先引入函式庫，函式庫的官方說明書在此 cplusplus.com std::deque。

#include <deque>

建立雙向佇列

雙向佇列的資料可以是所有內建的資料格式，例如 int、float、string，也可以使用自訂的資料格式。語法為

// 産生空的雙向佇列
deque<資料格式> 雙向佇列名稱;
// 産生填入相同資料的雙向佇列，資料可省略，預設值為 0
deque<資料格式> 雙向佇列名稱 (資料數量, 資料);
// 由雙向佇列2複製資料，也可以改變記憶體位置只複製部分內容
deque<資料格式> 雙向佇列名稱 (雙向佇列2名稱.begin(), 雙向佇列2名稱.end());
// 由雙向佇列2複製資料
deque<資料格式> 雙向佇列名稱 (雙向佇列2名稱);
// 由已定義的陣列複製資料
deque<資料格式> 雙向佇列名稱 (陣列名稱, 陣列名稱 + 陣列長度);
// 産生雙向佇列並指定資料
deque<資料格式> 雙向佇列名稱 {用逗號分隔的資料};
deque<資料格式> 雙向佇列名稱 = {用逗號分隔的資料};

例如以下的程式碼

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}

迭代器 iterator

迭代器可以用來取得物件對應的記憶體位址，有以下幾種：

雙向佇列名稱.begin();  // 回傳雙向佇列起點位址
雙向佇列名稱.end();    // 回傳雙向佇列終點位址
雙向佇列名稱.rbegin(); // 回傳雙向佇列終點位址，由後向前向讀取資料
雙向佇列名稱.rend();   // 回傳雙向佇列起點位址，由後向前向讀取資料
雙向佇列名稱.cbegin(); // 回傳雙向佇列起點位址，回傳值為常數
雙向佇列名稱.cend();   // 回傳雙向佇列終點位址，回傳值為常數
雙向佇列名稱.crbegin();// 回傳雙向佇列終點位址，由後向前向讀取資料，回傳值為常數
雙向佇列名稱.crend();  // 回傳雙向佇列起點位址，由後向前向讀取資料，回傳值為常數

迭代器的變數名稱通常是 it，寫法有兩種，例如以下的程式碼

deque<int> q = {0, 1, 2, 3, 4};
deque<int>::iterator it = q.begin();
auto it = q.begin();

但是 deque<int>::iterator 只能用在 begin()、end()，還是用 auto 會比較方便。如果要印出雙向佇列中所有的資料，可以配合迭代器處理，例如以下的程式碼

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

從最前面填入資料

語法為

雙向佇列名稱.push_front(資料);

例如以下的程式碼

deque<int> q;
q.push_front(0);  // q 的內容為 {0}
q.push_front(1);  // q 的內容為 {1, 0}
q.push_front(2);  // q 的內容為 {2, 1, 0}

另一個工具是 emplace_front，語法為

雙向佇列名稱.emplace_front(資料);

看起來效果和 push_front 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼

deque<int> q;
q.emplace_front(0);  // q 的內容為 {0}
q.emplace_front(1);  // q 的內容為 {1, 0}
q.emplace_front(2);  // q 的內容為 {2, 1, 0}

從最後面填入資料

語法為

雙向佇列名稱.push_back(資料);

例如以下的程式碼

deque<int> q;
q.push_back(0);  // q 的內容為 {0}
q.push_back(1);  // q 的內容為 {0, 1}
q.push_back(2);  // q 的內容為 {0, 1, 2}

另一個工具是 emplace_back，語法為

雙向佇列名稱.emplace_back(資料);

看起來效果和 push_back 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼

deque<int> q;
q.emplace_back(0);  // q 的內容為 {0}
q.emplace_back(1);  // q 的內容為 {0, 1}
q.emplace_back(2);  // q 的內容為 {0, 1, 2}

於指定的位置插入資料

語法為

雙向佇列名稱.insert(記憶體位址, 資料);

要配合迭代器取得記憶體位址，例如以下的程式碼

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}

另一個工具是 emplace，語法為

雙向佇列名稱.emplace(記憶體位址, 資料);

看起來效果和 instert 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼

deque<int> q = {0, 1, 2, 3, 4};
q.emplace(q.begin()+1, -1);  // 於開頭處向後 1 格插入 -1，q 的內容變為 {0, -1, 1, 2, 3, 4}

刪除最前面的資料

語法為

雙向佇列名稱.pop_front();

不需要任何參數，沒有回傳值。例如以下的程式碼

deque<int> q = {0, 1, 2, 3, 4, 5};
q.pop_front();  // 刪除開頭處的資料，q 的內容變為 {1, 2, 3, 4, 5}

如果雙向佇列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼

deque<int> q;
q.pop_front();

刪除最後面的資料

語法為

雙向佇列名稱.pop_back();

不需要任何參數，沒有回傳值。例如以下的程式碼

deque<int> q = {0, 1, 2, 3, 4, 5};
q.pop_back();  // 刪除開頭處的資料，q 的內容變為 {0, 1, 2, 3, 4}

如果雙向佇列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼

deque<int> q;
q.pop_back();

刪除指定範圍的資料

語法為

雙向佇列名稱.erase(起點位址, 終點位址);

不包含終點位址。例如以下的程式碼

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());  // 刪除所有資料

清除所有資料

語法為

雙向佇列名稱.clear();

不需要加上任何參數，清空資料後雙向佇列長度為 0。

交換兩個雙向佇列的資料

語法為

雙向佇列名稱1.swap(雙向佇列名稱2);

取得最前面的資料

語法為

雙向佇列名稱.front();

不需要任何參數。例如以下的程式碼

deque<int> q = {0, 1, 2, 3, 4, 5};
int a = q.front();  // a 的內容為 0

如果雙向佇列是空的，會回傳 0，例如以下的程式碼

deque<int> q;
int a = q.front();  // a 的內容為 0

取得最後面的資料

語法為

雙向佇列名稱.back();

不需要任何參數。例如以下的程式碼

deque<int> q = {0, 1, 2, 3, 4, 5};
int a = q.back();  // a 的內容為 5

如果雙向佇列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼

deque<int> q;
int a = q.back();

取得指定索引值的資料

語法有兩種，分別為

雙向佇列名稱[索引值];
雙向佇列名稱.at(索引值);

兩者有點差異，例如以下的程式碼

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

取得雙向佇列長度

語法為

雙向佇列名稱.size();

不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。

回傳雙向佇列最大長度

語法為

雙向佇列名稱.max_size();

不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。在我使用的系統中回傳值為 2305843009213693951，為 $2^{61} - 1$。

調整雙向佇列長度

語法為

雙向佇列名稱.resize(長度, 資料);

將雙向佇列調整成指定長度，資料參數可省略，預設值為 0。例如以下的程式碼

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}

調整雙向佇列使用的記憶體

語法為

雙向佇列名稱.shrink_to_fit();

不需要任何參數，沒有回傳值。例如以下的程式碼

deque<int> q (100);  // q 的內容為 100 個 0
q.resize(10);        // q 的內容變為 10 個 0
q.shrink_to_fit();   // 調整 q 使用的記憶體

檢查雙向佇列是否為空

語法為

雙向佇列名稱.empty();

不需要任何參數，如果雙向佇列為空回傳 1，如果有資料回傳 0。

由雙向佇列前方取出所有資料

這是很常用的技巧，假設雙向佇列 q 的內容為 {0, 1, 2, 3, 4}，程式碼通常是以下的寫法，回傳值 n 依序為 0、1、2、3、4。

while(!q.empty()) {     // 當雙向佇列中還有資料時繼續執行 while 迴圈
    int n = q.front();  // 回傳雙向佇列最前面的資料，回傳的資料指定給變數 n
    q.pop_front();      // 移除雙向佇列最前面的資料
}

由雙向佇列後方取出所有資料

這是很常用的技巧，假設雙向佇列 q 的內容為 {0, 1, 2, 3, 4}，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。

while(!q.empty()) {     // 當雙向佇列中還有資料時繼續執行 while 迴圈
    int n = q.back();   // 回傳雙向佇列最前面的資料，回傳的資料指定給變數 n
    q.pop_back();       // 移除雙向佇列最前面的資料
}

結語

以上是我目前常用到的雙向佇列功能，如果之後有遇到其它需求會再補充內容。

參考資料

HackMD 版本連結：https://hackmd.io/@yizhewang/S1WYlgFih

熱門文章

2023年8月5日 星期六

Python 及 C++ 雙向佇列 (deque)

前言

Python 方法1：引入 collections 函式庫中的 deque

建立雙向佇列

從最前面填入資料

從最後面填入資料

清除資料

複製雙向佇列

計算雙向佇列中某筆資料的數量

從最後面填入多筆資料

從最前面填入多筆資料

從雙向佇列中找到指定資料的索引值

於指定的索引值插入資料

取得雙向佇列最後面的資料

取得雙向佇列最前面的資料

移除雙向佇列指定的資料

反轉雙向佇列中的資料

前後平移雙向佇列中的資料

回傳雙向佇列最大長度

取得雙向佇列長度

由雙向佇列前方取出所有資料

由雙向佇列後方取出所有資料

Python 方法2：使用串列 (list)

建立空的串列

從最前面填入資料

從最後面填入資料

清除資料

複製串列

計算串列中某筆資料的數量

從最後面填入多筆資料

從串列中找到指定資料的索引值

取得串列最後面的資料

取得串列最前面的資料

移除串列指定的資料

反轉串列中的資料

取得串列長度

由串列前方取出所有資料

由串列後方取出所有資料

C++ STL deque 函式庫

建立雙向佇列

迭代器 iterator

從最前面填入資料

從最後面填入資料

於指定的位置插入資料

刪除最前面的資料

刪除最後面的資料

刪除指定範圍的資料

清除所有資料

交換兩個雙向佇列的資料

取得最前面的資料

取得最後面的資料

取得指定索引值的資料

取得雙向佇列長度

回傳雙向佇列最大長度

調整雙向佇列長度

調整雙向佇列使用的記憶體

檢查雙向佇列是否為空

由雙向佇列前方取出所有資料

由雙向佇列後方取出所有資料

結語

參考資料

沒有留言:

張貼留言

2023年8月5日星期六