一、基本概念
deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。
deque和vector区别：
vector对于头部的插入删除效率低，数据量越大，效率越低；
deque相对而言，对头部的插入删除速度回比vector快；
vector访问元素时的速度会比deque快,这和两者内部实现有关。
二、构造函数
// 打印 void printDeque(const deque<int> &d) { // for (int i = 0; i < d.size(); ++i) { // cout << d[i]<<" "; // } // 只读迭代器 for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { cout << *it << " "; } cout << endl; } //deque容器构造函数 void test01() { deque<int> d1; for (int i = 0; i < 10; ++i) { d1.push_back(i); } printDeque(d1); deque<int> d2(d1.begin(), d1.end()); printDeque(d2); deque<int> d3(10, 1000); printDeque(d3); deque<int> d4(d3); printDeque(d4); }
三、赋值操作
//deque容器赋值操作 void test02() { deque<int> d1; for (int i = 0; i < 10; ++i) { d1.push_back(i); } printDeque(d1); deque<int> d2; d2 = d1; printDeque(d2); deque<int> d3; d3.assign(10, 100); printDeque(d3); deque<int> d4; d4.assign(d2.begin(), d2.end()); printDeque(d4); }
四、大小操作
//deque容器大小 void test03() { deque<int> d1; for (int i = 0; i < 10; ++i) { d1.push_back(i); } // 0 1 2 3 4 5 6 7 8 9 printDeque(d1); // 10 cout << d1.size() << endl; // 0 cout << d1.empty() << endl; // d1.resize(20); d1.resize(20, 6); // 0 1 2 3 4 5 6 7 8 9 6 6 6 6 6 6 6 6 6 6 printDeque(d1); // 20 cout << d1.size() << endl; d1.resize(3); // 0 1 2 printDeque(d1); // 3 cout << d1.size() << endl; }
五、插入和删除
//deque容器插入和删除 //两端操作 void test04() { deque<int> d1; //尾插 d1.push_back(10); d1.push_back(20); // 头插 d1.push_front(30); d1.push_front(40); // 40 30 10 20 printDeque(d1); // 尾删 d1.pop_back(); // 头删 d1.pop_front(); printDeque(d1); } // 中间操作 void test05() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); // 200 100 10 20 printDeque(d1); //insert插入 d1.insert(d1.begin(), 1000); //1000 200 100 10 20 printDeque(d1); d1.insert(d1.begin(), 2, 10000); //10000 10000 1000 200 100 10 20 printDeque(d1); // 按照区间进行插入 deque<int> d2; d2.push_back(1); d2.push_back(2); d2.push_back(3); d1.insert(d1.begin(), d2.begin(), d2.end()); // 1 2 3 10000 10000 1000 200 100 10 20 printDeque(d1); } // 删除 void test06() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); //删除 deque<int>::iterator it = d1.begin(); it++; d1.erase(it); //200 10 20 printDeque(d1); // 按照区间删除 d1.erase(d1.begin(), d1.end()); // 清空 // d1.clear(); printDeque(d1); }
六、数据存取
//deque容器的数据存取操作 void test07() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); printDeque(d1); // 返回索引idx所指的数据 cout << d1.at(0) << endl; // 返回索引所指的数据 cout << d1[0] << endl; // 返回第一个数据元素 cout << d1.front() << endl; // 返回最后一个数据元素 cout << d1.back() << endl; }
七、deque排序
//dque容器的排序 void test08() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); // 200 100 10 20 printDeque(d1); // 10 20 100 200 sort(d1.begin(), d1.end()); printDeque(d1); }
八、测试
#include <iostream> using namespace std; #include <deque> #include <algorithm> // 打印 void printDeque(const deque<int> &d) { // for (int i = 0; i < d.size(); ++i) { // cout << d[i]<<" "; // } // 只读迭代器 for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) { cout << *it << " "; } cout << endl; } //deque容器构造函数 void test01() { deque<int> d1; for (int i = 0; i < 10; ++i) { d1.push_back(i); } printDeque(d1); deque<int> d2(d1.begin(), d1.end()); printDeque(d2); deque<int> d3(10, 1000); printDeque(d3); deque<int> d4(d3); printDeque(d4); } //deque容器赋值操作 void test02() { deque<int> d1; for (int i = 0; i < 10; ++i) { d1.push_back(i); } printDeque(d1); deque<int> d2; d2 = d1; printDeque(d2); deque<int> d3; d3.assign(10, 100); printDeque(d3); deque<int> d4; d4.assign(d2.begin(), d2.end()); printDeque(d4); } //deque容器大小 void test03() { deque<int> d1; for (int i = 0; i < 10; ++i) { d1.push_back(i); } // 0 1 2 3 4 5 6 7 8 9 printDeque(d1); // 10 cout << d1.size() << endl; // 0 cout << d1.empty() << endl; // d1.resize(20); d1.resize(20, 6); // 0 1 2 3 4 5 6 7 8 9 6 6 6 6 6 6 6 6 6 6 printDeque(d1); // 20 cout << d1.size() << endl; d1.resize(3); // 0 1 2 printDeque(d1); // 3 cout << d1.size() << endl; } //deque容器插入和删除 //两端操作 void test04() { deque<int> d1; //尾插 d1.push_back(10); d1.push_back(20); // 头插 d1.push_front(30); d1.push_front(40); // 40 30 10 20 printDeque(d1); // 尾删 d1.pop_back(); // 头删 d1.pop_front(); printDeque(d1); } // 中间操作 void test05() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); // 200 100 10 20 printDeque(d1); //insert插入 d1.insert(d1.begin(), 1000); //1000 200 100 10 20 printDeque(d1); d1.insert(d1.begin(), 2, 10000); //10000 10000 1000 200 100 10 20 printDeque(d1); // 按照区间进行插入 deque<int> d2; d2.push_back(1); d2.push_back(2); d2.push_back(3); d1.insert(d1.begin(), d2.begin(), d2.end()); // 1 2 3 10000 10000 1000 200 100 10 20 printDeque(d1); } // 删除 void test06() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); //删除 deque<int>::iterator it = d1.begin(); it++; d1.erase(it); //200 10 20 printDeque(d1); // 按照区间删除 d1.erase(d1.begin(), d1.end()); // 清空 // d1.clear(); printDeque(d1); } //deque容器的数据存取操作 void test07() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); printDeque(d1); // 返回索引idx所指的数据 cout << d1.at(0) << endl; // 返回索引所指的数据 cout << d1[0] << endl; // 返回第一个数据元素 cout << d1.front() << endl; // 返回最后一个数据元素 cout << d1.back() << endl; } //dque容器的排序 void test08() { deque<int> d1; d1.push_back(10); d1.push_back(20); d1.push_front(100); d1.push_front(200); // 200 100 10 20 printDeque(d1); // 10 20 100 200 sort(d1.begin(), d1.end()); printDeque(d1); } int main() { // test01(); // test02(); // test03(); // test04(); // test05(); // test06(); // test07(); test08(); system("pause"); return 0; }
200 100 10 20 10 20 100 200
