静安做网站公司,wordpress春菜,漳州网站建设技术,哪个网站可以学做包子接下来我们将实现 stack、queue 类的常用函数#xff0c;其实对于 stack 和 queue 的常用函数实现可以说得上是非常简单#xff0c;若想详细了解可以看这篇#xff1a;栈和队列循环队列#xff08;C/C#xff09;_栈和循环队列-CSDN博客#xff1b;在本篇中我们将使… 接下来我们将实现 stack、queue 类的常用函数其实对于 stack 和 queue 的常用函数实现可以说得上是非常简单若想详细了解可以看这篇栈和队列循环队列C/C_栈和循环队列-CSDN博客在本篇中我们将使用容器适配器来实现栈和队列。 目录如下: 目录 1. stack 2. queue 3. deque 3.1 deque的原理介绍 3.2 deque 的缺陷 3.3 stack、queue为什么选择deque 1. stack 我们首先实现的为 stack根据 cplusplus 网站来实现 stack 的常用函数如下 如上对于该 stack 函数而言就只有以上这些类函数关于其他的 operator 重载函数不包括。对于以上每个函数的实现我们并不会在底层实现它而是使用容器适配器来实现它如下直接给出函数 namespace MyStack_Queue {templateclass T, class Container vectorTclass stack {public:stack(const Container con Container()):_con(con){}stack(const stack st):_con(st._con){}bool empty() {return _con.empty();}size_t size() {return _con.size();}void push(const T e) {_con.push_back(e);}void pop() {_con.pop_back();}T top() {return _con.back();}const T top() const {return _con.back();}void swap(stack st) {_con.swap(st._con);}private:Container _con;};
} 如上所示我们在模板处定义了一个类型和一个容器这个容器的缺省值为 vector所以当我们在下面函数的实现中将成员变量默认定义为了 vector 类但其实在 stack 底层大多默认都是使用 deque然后在实现成员函数的时候默认调用 vector 类中函数这样就非常方便的实现了一个栈。 对于以上容器的缺省值我们不仅仅可以使用 vector我们还可以使用 deque还可以使用 list 来实现只需要在实例化一个对象的时候将值传入就可以了如下 void Test00() {MyStack_Queue::stackint, listint st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()) {int tmp st.top();st.pop();cout tmp endl;}cout endl;} 如上的测试代码我们使用了一个 list 容器实现了一个栈。但是在实现栈的时候还是建议使用 vector 类型。 2. queue queue 的实现和 stack 十分的相似我们使用容器实现对于 queue 的成员函数如下 下列为我们使用容器实现的代码 templateclass T,class Container dequeTclass queue {public:queue(const Container con Container()):_con(con){}queue(const Container q) {_con(q._con);}bool empty() {return _con.empty();}size_t size() {return _con.size();}T front() {return _con.front();}const T front() const {return _con.front;}T back() {return _con.back();}const T back() const {return _con.back();}void pop() {_con.pop_front();}void push(const T e) {_con.push_back(e);}void swap(queue q) {_con.swap(q._con);}private:Container _con;}; 对于以上容器的缺省值我们使用的是 deque当然我们使用 list 也是一种高效的方式。 3. deque 接下来我们将简单的讲解 deque -- 双端队列仅仅只是讲解其原理和优缺点并不会实现 deque因为 deque 的迭代器实现起来很复杂所以我们仅仅将其作为一个了解的知识即可。 3.1 deque的原理介绍 deque双端队列是一种双开口的“连续”空间的数据结构。双开的含义为可以在头尾两端进行插入和删除操作且时间复杂度为 O(1)与 vector 相比头插效率高与 list 相比空间利用率比较高。如下 deque 并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际上类似于一个动态的二维数组其具体的实现原理如下 所以具体的空间开辟如上所示存在一个中控数组里面存储的是每一个分组的地址当我们想要获取元素的时候就是通过这样的结构进行获取的。但是 deque 同时也支持 operator[] 重载函数所以可以随机访问到我们的元素在这样的数据结构中为了维护随机访问假象那么这个责任就落到了 deque 的迭代器身上迭代器的设计原理如下 所以对于 deque 的迭代器有着四个指针分别指向不同的地方所以 deque 最难的是它的迭代器。 3.2 deque 的缺陷 与 vector 相比deque 的优势为头插和尾删时不需要搬移元素效率特别的高而且在扩容的时候也不需要搬移大量的元素因此效率比 vector 高。 与 list 相比较其底层是一个连续的空间空间利用率比较高不需要存储额外字段。 但deque 有着一个很致命的缺陷不适合遍历因为在遍历的时候deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而在序列场景中可能要经常遍历因此在时间中需要线性结构时大多情况考虑的都是 vector listdeque 应用的场景并不多而目前能看到运用的场景就是在 STL 中的 stack 和 queue 底层数据结构。 3.3 stack、queue为什么选择deque stack 是一种先进先出的特殊线性数据结构因此只要有 push_back() 和 pop_back() 操作的线性结构都可以作为 stack 的底层容器比如 vector 和 list 都可以queue 是先进选出的特殊数据结构只要具有 push_back() pop_front 操作的线性结构都可以作为 queue 的底层容器比如 list。但是 STL 中对 stack 和 queue 默认选择 deque 作为底层容器主要是因为 1. stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。 2. 在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。 其中结合了 deque 的优点完美的避开了其缺陷。
