国际 网站制作公司,洗发水营销推广软文800字,吉林市建设局网站,wordpress图片上传到七牛云stack的介绍和使用
stack的介绍
堆栈 - C 参考 (cplusplus.com) 翻译 : 1. stack 是一种容器适配器#xff0c;专门用在具有后进先出操作的上下文环境中#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。 2. stack 是作为容器适配器被实现的#xff0c;容器…stack的介绍和使用
stack的介绍
堆栈 - C 参考 (cplusplus.com) 翻译 : 1. stack 是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 2. stack 是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部( 即栈顶 ) 被压入和弹出。 3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作 empty 判空操作 back 获取尾部元素操作 push_back 尾部插入元素操作 pop_back 尾部删除元素操作 4. 标准容器 vector 、 deque 、 list 均符合这些需求默认情况下如果没有为 stack 指定特定的底层容器默认情况下使用deque 。 stack的使用 样例
void test_stack1()
{//bit::stackint, listint st;//bit::stackint, vectorint st;bit::stackint st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout st.top() ;st.pop();}cout endl;
} stack的模拟实现
#includevector
namespace bite
{templateclass Tclass stack{public:stack() {}void push(const T x) {_c.push_back(x);}void pop() {_c.pop_back();}T top() {return _c.back();}const T top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::vectorT _c;};
}
queue的介绍和使用
queue的介绍
队列 - C 参考 (cplusplus.com) 翻译 1. 队列是一种容器适配器专门用于在 FIFO 上下文 ( 先进先出 ) 中操作其中从容器一端插入元素另一端提取元素。 2. 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类 queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列。 3. 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty 检测队列是否为空 size 返回队列中有效元素的个数 front 返回队头元素的引用 back 返回队尾元素的引用 push_back 在队列尾部入队列 pop_front 在队列头部出队列 4. 标准容器类 deque 和 list 满足了这些要求。默认情况下如果没有为 queue 实例化指定容器类则使用标准容器deque 。 queue的使用 queue的模拟实现 因为 queue 的接口中存在头删和尾插因此使用 vector 来封装效率太低故可以借助 list 来模拟实现 queue 具体如下 #include list
namespace bite
{templateclass Tclass queue{public:queue() {}void push(const T x) {_c.push_back(x);}void pop() {_c.pop_front();}T back() {return _c.back();}const T back()const {return _c.back();}T front() {return _c.front();}const T front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::listT _c;};
} 容器适配器 什么是适配器 适配器是一种设计模式 ( 设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结) 该种模式是将一个类的接口转换成客户希望的另外一个接口 。 STL标准库中stack和queue的底层结构 虽然 stack 和 queue中也可以存放元素但 在 STL 中并没有将其划分在容器的行列而是将其称为 容器适配 器 这是因为 stack 和队列只是对其他容器的接口进行了包装 STL 中 stack 和 queue 默认使用 deque 比如 deque的简单介绍(了解)
deque的原理介绍 deque( 双端队列 ) 是一种双开口的 连续 空间的数据结构 双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1) 与 vector 比较头插效率高不需要搬移元素与 list 比较空间利用率比较高。 deque 并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际 deque 类似于一个动态的二维 数组 其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其 “ 整体连续 ” 以及随机访问的假象落 在了 deque 的迭代器身上 因此 deque 的迭代器设计就比较复杂如下图所示 那deque是如何借助其迭代器维护其假想连续的结构呢 deque的缺陷 与 vector 比较 deque 的优势是头部插入和删除时 不需要搬移元素效率特别高 而且在 扩容时也不 需要搬移大量的元素 因此其效率是比 vector 高的。 与 list 比较 其底层是连续空间 空间利用率比较高 不需要存储额外字段。 但是 deque 有一个致命缺陷不适合遍历因为在遍历时 deque 的迭代器要频繁的去检测其是否移动到 某段小空间的边界导致效率低下 而序列式场景中可能需要经常遍历因此 在实际中需要线性结构 时大多数情况下优先考虑 vector 和 list deque 的应用并不多而 目前能看到的一个应用就是 STL 用其作 为 stack 和 queue 的底层数据结构。 例子 #includeiostream
using namespace std;#includestack
#includedeque
#includealgorithmvoid test_op1()
{srand(time(0));const int N 1000000;dequeint dq;vectorint v;for (int i 0; i N; i){auto e rand() i;v.push_back(e);dq.push_back(e);}int begin1 clock();sort(v.begin(), v.end());//排序涉及到遍历数组int end1 clock();int begin2 clock();sort(dq.begin(), dq.end());int end2 clock();printf(vector:%d\n, end1 - begin1);printf(deque:%d\n, end2 - begin2);
}结果
vector:1810
deque:7265 为什么选择 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 不仅效率高而且内存使用率高。 结合了 deque 的优点而完美的避开了其缺陷。 总结 STL标准库中对于stack和queue的模拟实现 stack的模拟实现
#includedeque
namespace bit
{
templateclass T, class Con dequeT//templateclass T, class Con vectorT//templateclass T, class Con listTclass stack{public:stack() {}void push(const T x) {_c.push_back(x);}void pop() {_c.pop_back();}T top() {return _c.back();}const T top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:Con _c;};
} queue的模拟实现
#includedequenamespace bit
{templateclass T, class Con dequeT//templateclass T, class Con listTclass queue{public:queue() {}void push(const T x) {_c.push_back(x);}void pop() {_c.pop_front();}T back() {return _c.back();}const T back()const {return _c.back();}T front() {return _c.front();}const T front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:Con _c;};
}
