怎样建设好门户网站,wordpress主机名,租号网站建设,产品外观设计网站文章目录 1.deque的简单介绍2.模拟实现stack3.模拟实现queue 1.deque的简单介绍
deque的介绍文档 deque(双端队列)#xff1a;是一种双开口的连续空间的数据结构#xff0c;双开口的含义是#xff1a;可以在头尾两端进行插入和删除操作#xff0c;且时间复杂度… 文章目录 1.deque的简单介绍2.模拟实现stack3.模拟实现queue 1.deque的简单介绍
deque的介绍文档 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 deque的缺陷 与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下 而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构 为什么选择deque作为stack和queue的底层默认容器 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不仅效率高而且内存使用率高。 2.模拟实现stack 这个stack类模板是一个栈的实现使用了一个名为Container的模板参数来指定底层容器的类型默认为deque。也就是说如果不指定底层容器类型那么stack类将使用deque作为底层容器。 push将元素x插入到栈顶实际上是调用底层容器的push_back函数。 pop弹出栈顶元素实际上是调用底层容器的pop_back函数。 top返回栈顶元素的引用实际上是返回底层容器的最后一个元素的引用。 size返回栈中元素的个数实际上是返回底层容器的size函数的返回值。 empty判断栈是否为空实际上是调用底层容器的empty函数。 这个stack类模板的目的是提供一个封装了底层容器的栈的实现使得我们可以方便地使用栈的各种操作。底层容器的选择可以根据我们具体的需求进行自定义或者使用默认的deque容器。
#pragma once
#includevector
#includelist
#includedequenamespace st
{//空间配置器templateclass T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}3.模拟实现queue 这个queue类模板是一个队列的实现使用了一个名为Container的模板参数来指定底层容器的类型默认为deque。也就是说如果不指定底层容器类型那么queue类将使用deque作为底层容器。 push将元素x插入到队列的末尾实际上是调用底层容器的push_back函数。 pop弹出队列的第一个元素实际上是调用底层容器的pop_front函数。 front返回队列的第一个元素的引用实际上是返回底层容器的第一个元素的引用。 back返回队列的最后一个元素的引用实际上是返回底层容器的最后一个元素的引用。 size返回队列中元素的个数实际上是返回底层容器的size函数的返回值。 empty判断队列是否为空实际上是调用底层容器的empty函数。 这个queue类模板的目的是提供一个封装了底层容器的队列的实现使得用户可以方便地使用队列的各种操作。底层容器的选择可以根据具体的需求进行自定义或者使用默认的deque容器。
#pragma once
#includevector
#includelist
#includedequenamespace que
{//空间配置器templateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();//_con.erase(_con.begin());}T front(){return _con.front();}T back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}测试代码
#define _CRT_SECURE_NO_WARNINGS 1#includeiostream
#includestack
#includequeue
using namespace std;#includestack.h
#includequeue.hvoid test_stack()
{//st::stackint, std::vectorint st1;st::stackint st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout st1.top() ;st1.pop();}cout endl;st::stackint, std::listint st2;st2.push(1);st2.push(2);st2.push(3);st2.push(4);while (!st2.empty()){cout st2.top() ;st2.pop();}cout endl;
}void test_queue()
{//que::queueint, vectorint q;que::queueint q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout q1.front() ;q1.pop();}cout endl;que::queueint, listint q2;q2.push(1);q2.push(2);q2.push(3);q2.push(4);while (!q2.empty()){cout q2.front() ;q2.pop();}cout endl;
}int main()
{test_stack();test_queue();return 0;
}
