栈和队列的模拟实现

文章目录 一. 回顾栈和队列二. stack的模拟实现stack.hstack.cpp 三. queue的模拟实现queue.htest.cpp 四. 了解dequeuevector和list都有各自的缺陷deque 总结

一. 回顾栈和队列

回顾一下栈和队列

栈：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;

首先要知道stack栈都有什么接口，我们再实现 需要实现判空，返回栈中元素的个数，栈顶元素，尾插和尾删，交换。

用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; }; } stack.cpp #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是先进先出，也就是尾插头删

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; }; } test.cpp 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; } 四. 了解dequeue

查看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的空间是连续的，而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。