一. 回顾栈和队列
回顾一下栈和队列
- 栈：stack：后进先出
_ 队列：queue：先辈先出
计划模式有很多种，鉴戒计划模式的参考书:计划模式 - 可复用的面向对象软件元素，得知统共有 23 种计划模式。
计划模式是是先辈们对代码开辟履历的总结，是解决特定题目的一系列套路，比如适配器模式，迭代器模式
栈和队列是容器适配器，而不是容器。
- 迭代器模式：将迭代器封装之后提供统一的访问方式，优点：不暴露底层细节
- 适配器模式：适配器其实是一种转换，通过已有的东西封装转换出你想要的东西。比如电源适配器（电压电流的转换，家里的电源电压通常是220v，而某个电子产品之许哟啊20v的电压，这个时候就必要用到适配器）
stack的利用
- #define _CRT_SECURE_NO_WARNINGS
- #include<stdio.h>
- #include<iostream>
- #include<stack>
- #include<queue>
- int main()
- {
- std::stack<int> st1;
- st1.push(1);
- st1.push(2);
- st1.push(3);
- st1.push(4);
- std::cout <<"在未删除之前st1的元素个数" << st1.size() << std::endl;
- //栈是后进先出，所以现在想打印的话，打印的是栈顶元素
- while (!st1.empty())
- {
- std::cout << st1.top() << " ";
- //只能将栈顶元素删除，才能打印下一个元素
- st1.pop();
- }
- std::cout << std::endl;
- std::cout << "在删除之后st1的元素个数" << st1.size() << std::endl;
- std::stack<int> st2;
- st2.push(8);
- st2.push(7);
- st2.push(6);
- st2.push(5);
- st2.swap(st1);
- std::cout << "st1和st2交换之后，st1的元素" << std::endl;
- while (!st1.empty())
- {
- std::cout << st1.top() << " ";
- //只能将栈顶元素删除，才能打印下一个元素
- st1.pop();
- }
- std::cout << std::endl;
- return 0;
- }
二. stack的模拟实现
stack.h
先在私有部分将类的成员变量写出来，我们必要一个容器。
- //Container有可能是vector，也有可能是list
- Container _con;
必要实现判空，返回栈中元素的个数，栈顶元素，尾插和尾删，交换。
用C++的好处就是可以直接利用容器的接口，我们现在想用vector或list来实现stack（在过程中，可以利用vector和list的接口。
从接口可以看出，无论容器是vector还是list，都可以利用尾插尾删，以及back（获取末了一个元素），empty（判空）。
- 以是，模拟实现stack的时候，容器vector和list都可以利用
- 注意点：利用利用vector，要么展开命名空间using namespace std，要么写std::vector
- #pragma once
- #include<stdio.h>
- #include<iostream>
- #include<vector>
- #include<list>
- namespace hou
- {
- template<class T,class Container>
- class stack
- {
- public:
- //向容器里插入数据(这里是实现stack，是尾插尾删)
- void push(const T& x)
- {
- _con.push_back(x);
- }
- void pop()
- {
- _con.pop_back();
- }
- const T& top()
- {
- return _con.back();
- }
- bool empty()
- {
- return _con.empty();
- }
- size_t size()
- {
- return _con.size();
- }
- private:
- Container _con;
- };
- }
- #include"stack_queue.h"
- int main()
- {
- hou::stack<int,std::vector<int>> mystack1;
- mystack1.push(11);
- mystack1.push(12);
- mystack1.pop();
- std::cout<<mystack1.size()<<std::endl;
- return 0;
- }
队列queue是先辈先出，也就是尾插头删
queue.h
- #pragma once
- #include<stdio.h>
- #include<iostream>
- #include<vector>
- #include<list>
- namespace hou
- {
- template<class T,class Container>
- class queue
- {
- public:
- void push(const T& x)
- {
- _con.push_back(x);
- }
- void pop()
- {
- _con.pop_front();
- }
- const T& front()
- {
- return _con.front();
- }
- const T& back()
- {
- return _con.back();
- }
- bool empty()
- {
- return _con.empty();
- }
- size_t size()
- {
- return _con.size();
- }
- private:
- Container _con;
- };
- }
- int main()
- {
- hou::queue<int, std::list<int>> myqueue1;
- myqueue1.push(1);
- myqueue1.push(2);
- myqueue1.push(3);
- while (!myqueue1.empty())
- {
- std::cout << myqueue1.front() << std::endl;
- myqueue1.pop();
- }
- return 0;
- }
查看stack和queue的文档时发现：Container的缺省值不是vector或list，而是deque，deque是一个双端队列（两端都可以插入删除）
- queue：template <class T, class Container = deque<T> > class queue;
- list：template <class T, class Container = deque<T> > class stack;
vector的空间是连续的，而list是一个一个的结点组成的（空间不是连续的）
- vector的物理地址是连续的，可以利用[]访问元素（vector支持随机访问）。但同时也就导致头插头删非常麻烦，头插有扩容斲丧（先查看空间是否足够，再将背面的内容一个一个今后移），头删/中部删的效率低（背面的内容往前移）。
2. list的物理空间是不连续的，它无法通过[]来访问元素（不支持随机访问）。同时也致使CPU高速缓存掷中率低。但是list头插头删很容易，改变链接即可。
deque
deque兼具vector和list之长（既可以随机访问，又可以不那么）
底层实现：开一个又一个小的数组buffer，再用一个中控数组将这些buffer管理起来（中控数组它的每个元素是指针，是每个buffer的地址），以是每个buffer不用想着下一个buffer是谁，这个由中控数组在管理。
deque并不是真正连续的空间，而是由一段一段的(名字为buffer)的小空间拼接而成，再由中控数组来控制。
- 如果中控数组满了呢？那就必要异地扩容，但也不复杂，将地址复制过来就OK。
- 在deque中，不是将第一个buffer放在最前面，而是将中控数组的前几个位置空出来，为了之后必要头插做准备，如果前面有位置的话，就不用挪动数据了。
deque固然有queue和list的优点，但也有不敷的地方，无法取代它俩。
- deque在随机访问的时候，必要知道某个数据在哪个buffer里？又是在这个buffer的第几个元素？（第几个buffer：用数据地点的位置/10。buffer的第几个元素：用数据地点的位置%10)。下标的随机访问有一定的斲丧，没有vector的随机访问快。
- 若是想在某个buffer里插入数据或删除buffer里的某个数据，怎么做呢？
（1）挪动这个数据背面的数据--------->效率低
（2）只挪动当前buffer的数据----------->效率还可以，(删除某个buffer的数据且只挪动当前buffer的元素)但是会导致每个buffer的个数不一样，计算在第几个buffer的第几个元素会更麻烦。以是deque在中间插入删除也有一定的斲丧，相比list中间插入删除不敷机动，没有list快。栈和队列一般是插入或删除头尾的数据，利用deque当默认适配容器会比力适合！！！
deque不适合遍历。由于在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。而序列式场景中，可能必要经常遍历，因此在实际中，必要线性结构时，大多数情况下优先思量vector和list，deque的应用并不多，而现在能看到的一个应用就是，STL用其作为stack和queue**的底层数据结构
deque作为stack和queue的底层默认容器 ：在stack中元素增长时，deque比vector的效率高(扩容时不必要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存利用率高
总结
模拟实现stack：vector和list都可以利用
模拟实现queue：只能利用容器list（队列是先辈先出，也就是头删，而vector没有头删这个接口）
实现stack和queue的默认适配容器是deque。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
