Last Updated on 2021-09-29 by Clay
deque 是 C++ 標準模板函式庫(Standard Template Library, STL)中的雙向佇列容器(Double-ended Queue),跟 vector 相似,不過在 vector 中若是要添加新元素至開端,其時間複雜度為 O(N),但在 deque 中則是 O(1)。同樣地,也能在我們需要儲存更多元素的時候自動擴展空間,讓我們不必煩惱佇列長度的問題。
很容易混淆的是,deque 實際上仍然是使用連續記憶體空間實作而成的,並不是雙向的 linked list。
以下就簡單介紹該如何使用 deque,首先是不同函式使用的示意圖,接著是陳列出我要記錄的函式。
- push_back()
- push_front()
- pop_back()
- pop_front()
- back()
- front()
- insert()
- erase()
- clear()
- size()
- empty()
- begin()
- end()
push_back()
push_back()
會在 deque 的最尾端新增元素。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; d.push_back(6); d.push_back(7); d.push_back(8); for (auto n: d) { cout << n << endl; } return 0; }
Output:
1
2
3
4
5
6
7
8
push_front()
跟 push_back()
不同,push_front()
是在 deque 的開頭新增元素。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; d.push_front(0); d.push_front(-1); d.push_front(-2); for (auto n: d) { cout << n << endl; } return 0; }
Output:
-2
-1
0
1
2
3
4
5
pop_back()
pop_back()
會移除 deque 最尾端的元素。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; d.pop_back(); d.pop_back(); for (auto n: d) { cout << n << endl; } return 0; }
Output:
1
2
3
pop_front()
很相似地,pop_front()
是用於移除 deque 最開頭的元素。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; d.pop_front(); d.pop_front(); for (auto n: d) { cout << n << endl; } return 0; }
Output:
3
4
5
back()
back()
會取出 deque 最尾端的元素(並不是移除的意思)。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // back() cout << d.back() << endl; cout << d.back() << endl; return 0; }
Output:
5
5
可以看到最尾端的元素並沒有被移除。
front()
front()
跟 back()
很相似,不過 front()
是回傳 deque 最開頭的元素。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // front() cout << d.front() << endl; return 0; }
Output:
1
begin()
begin()
返回一個指向 deque 開頭的迭代器,可以用來迭代 deque 內的元素、或是指定特定的 index。
迭代印出所有元素配合 end()
一起示範。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // begin() cout << *d.begin() << endl; return 0; }
Output:
1
可以看到,確實指向 deque 開頭。
end()
end()
則是指向 deque 結尾,不是最後一個元素,而是最後一個元素的下一個位置。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // Print deque<int>::iterator it = d.begin(); while (it != d.end()) { cout << *it << endl; it++; } return 0; }
Output:
1
2
3
4
5
insert()
d.insert(position, n, val)
- position: 插入元素的 index 值
- n: 元素插入次數
- val: 插入的元素值
以下看個簡單的範例:
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // insert() d.insert(d.begin(), 3, 100); // Print for (auto n: d) { cout << n << endl; } return 0; }
Output:
100
100
100
1
2
3
4
5
erase()
跟 insert()
不同,erase()
是刪除元素,需要使用迭代器指定刪除的元素或位置,同時也會返回指向刪除元素下一元素的迭代器。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // erase() d.erase(d.begin()); // Print for (auto n: d) { cout << n << endl; } return 0; }
Output:
2
3
4
5
(本來輸出有誤,感謝網友 CLARE0710 告知)
clear()
清空整個 deque 佇列。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; d.clear(); return 0; }
size()
檢查 deque 的尺寸。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // size() cout << "size: " << d.size() << endl; return 0; }
Output:
size: 5
empty()
如果 deque 佇列為空返回 1;若是存在任何元素,則返回 0。
#include <iostream> #include <deque> using namespace std; int main() { deque<int> d = {1, 2, 3, 4, 5}; // Not empty cout << "Before clearing: " << d.empty() << endl; // clear() d.clear(); // Empty cout << "After clearing: " << d.empty() << endl; return 0; }
Output:
Before clearing: 0
After clearing: 1
References
- http://www.cplusplus.com/reference/deque/deque/
- https://www.geeksforgeeks.org/deque-cpp-stl/
- https://www.softwaretestinghelp.com/deque-in-cpp/
- https://appdividend.com/2019/10/09/deque-in-cpp-example-cpp-deque-program/
erase的output 有錯喔
感謝告知!我複製到了別處的輸出 XD