上海网站建设定,企业网站教程,怎么查看网站公司,公司销售管理系统stack和queue stackstack的介绍stack的使用stack的实现 queuequeue的介绍queue的使用queue的实现 deque简单介绍deque#xff08;双端队列#xff09;双开口连续打引号的原因 deque底层结构deque的迭代器封装结构#xff08;复杂#xff09;deque的优缺点 栈和队列数据结构… stack和queue stackstack的介绍stack的使用stack的实现 queuequeue的介绍queue的使用queue的实现 deque简单介绍deque双端队列双开口连续打引号的原因 deque底层结构deque的迭代器封装结构复杂deque的优缺点 栈和队列数据结构画图分析如果对栈和队列的结构不了解的可以先看该链接的内容 stack
使用stack时需要头文件#includestack
stack的介绍
stack是一种容器适配器用于具有后进先出(LIFO)的环境中。只能从容器的一端栈顶执行删除、插入和提取操作。
stack是作为容器适配器实现的容器适配器是对特定容器类封装作为其底层的容器。vector、deque、list均符合特定的底层容器需求如果没有指定特定的底层容器默认使用deque
stack的使用
函数接口说明stack()构造空的栈empty()判断栈是否为空size()返回栈中的元素个数top()返回栈顶元素的引用push()将val压栈pop()出栈顶元素
test: void test_stack()
{stackint st;st.push(1);st.push(2);st.push(3);st.push(4);cout st.size() endl;while (!st.empty()){cout st.top() ;st.pop();}cout endl;
}注意从栈的接口可以看出栈实际是一种特殊的vector使用vector完全可以模拟实现stack
stack的实现
stack接口的实现是对deque容器接口的封装。
#include dequenamespace kpl
{//容器可以使用vector,deque容器在本博客最后一个知识点介绍//templateclass T, class Container vectorT//templateclass T, class Container listTtemplateclass T, class Container dequeTclass stack{public:stack(){}void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}T top(){return _con.back();}const T top() const{return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}queue
使用queue时需要头文件#includequeue
queue的介绍
queue是一种容器适配器用于具有先进先出(FIFO)的环境中。从容器的一端插入元素另一端提取元素。
queue作为容器适配器实现容器适配器是对特定容器类封装作为其底层的容器。deque、list符合特定的底层容器需求如果没有为queue实列化指定特定的底层容器默认使用deque
queue的使用
函数接口说明queue()构造空的队列empty()判断队列是否为空size()返回队列中的元素个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将val入列pop()在队头元素出队列
test:
void test_queue()
{queueint q;q.push(1);q.push(2);q.push(3);q.push(4);cout size: q.size() endl;cout front: q.front() endl;q.pop();cout back: q.back() endl;while (!q.empty()){cout front: q.front() ;q.pop();}cout endl;
}queue的实现
因为queue的接口有头插和尾插使用vector封装效率底所以可以借助list模拟实现。这里我们依旧使用的默认容器deque
queue接口的实现是对deque容器接口的封装。
#include dequenamespace kpl
{//templateclass T, class Container listTtemplateclass T, class Container dequeTclass queue{public:queue(){}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 push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}private:Container _con;};
}deque
简单介绍deque双端队列 概念是一种双开口“连续”空间的数据结构。 双开口 连续打引号的原因 原因deque并不是真正连续的空间而是由一段段连续的小空间拼接而成分段连续。 deque底层结构 deque的迭代器封装结构复杂 deque的优缺点 deque的优缺点决定了它适合当stack和queue的底层数据结构 stack和queue不需要遍历deque不适合遍历只需要在固定的一端或者两端操作即可。stack元素在增长时deque比vector的效率高不需要搬移数据queue元素在增长是内存使用率高效率也高。
