wordpress建立博客,新乡百度关键词优化外包,深圳网站制作哪家好,产品设计queue的使用与模拟实现 一、queue的介绍和使用二、queue的使用三、queue的模拟实现3.1 成员变量3.2 成员函数3.2.1 push入队列3.2.2 pop出队列3.2.3 返回队头数据3.2.4 返回队尾数据3.2.5 返回队列的大小3.2.6 判断队列是否为空 四、完整代码4.1 queue.h4.2 test.h 五、deque的… queue的使用与模拟实现 一、queue的介绍和使用二、queue的使用三、queue的模拟实现3.1 成员变量3.2 成员函数3.2.1 push入队列3.2.2 pop出队列3.2.3 返回队头数据3.2.4 返回队尾数据3.2.5 返回队列的大小3.2.6 判断队列是否为空 四、完整代码4.1 queue.h4.2 test.h 五、deque的简单介绍5.1 deque的原理介绍5.2 deque的优点和缺陷5.3 为什么选择deque作为stack和queue的底层默认容器 一、queue的介绍和使用
1.队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。 2.队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列。 3.底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty检测队列是否为空 size返回队列中有效元素的个数 front返回队头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列 4.标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。
二、queue的使用
函数说明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列
void test_queue()
{queueint q;q.push(1);q.push(2);q.push(3);q.push(4);q.pop();cout q.front() endl;cout q.size() endl;cout q.empty() endl;cout q.back() endl;}int main()
{test_queue();return 0;
}三、queue的模拟实现
3.1 成员变量
templateclass T, class Container listT
class queue
{
private:Container _con;
};3.2 成员函数
3.2.1 push入队列
void push(const T x)
{_con.push_back(x);
}3.2.2 pop出队列
void pop()
{_con.pop_front();
}3.2.3 返回队头数据
const T front()
{return _con.front();
}3.2.4 返回队尾数据
const T back()
{return _con.back();
}3.2.5 返回队列的大小
size_t size()
{return _con.size();
}3.2.6 判断队列是否为空
bool empty()
{return _con.empty();
}四、完整代码
4.1 queue.h
#pragma oncenamespace zl
{//适配器模式/配接器templateclass T, class Container listTclass 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();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){queueint q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout q.front() ;q.pop();}cout endl;}
}4.2 test.h
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
#includestack
#includevector
#includequeue
#includelist
using namespace std;
#include queue.hint main()
{zl::test_queue();return 0;
}五、deque的简单介绍
5.1 deque的原理介绍 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较(缺点1.头部中部插入/删除效率低下2.扩容。优点下标随机访问)头插效率高不需要搬移元素与list比较缺点不能支持随机访问。优点任意位置高效插入删除空间利用率比较高。 deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组
中控满了就扩容但是扩容代价低 双端队列底层是一段假想的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假想落在了deque的迭代器身上因此deque的迭代器设计就比较复杂。 那deque是如何借助其迭代器维护其假想连续的结构呢 1.deque是一个由三个固定大小的缓冲区构成的序列容器每个缓冲区都被当作一个元素来处理。为了维护deque的假想连续结构deque的迭代器实际上是一个复合迭代器它将多个子迭代器封装在一起以提供对整个deque的访问。 2.具体来说deque的迭代器实际上就是一个指向数据缓冲区的指针数组每个指针指向一个单独的存储块而这些存储块构成了deque的数据缓冲区 。
1.deque会通过维护多个内部的缓冲区来实现假想连续的结构并且迭代器也会对这些内部缓冲区进行适当划分和处理 2.在deque内部每个缓冲区被称作一个结点node并在其内部维护了一个完整的数据块 3.当deque在两端插入/删除元素时它会动态重新分配结点使得每个结点上的数据块都可以被利用从而保证数据块是假想连续的。同时迭代器会利用这些结点间的相对偏移量来实现对deque的高效遍历。
5.2 deque的优点和缺陷 优点1.相比vector扩容代价低 2.头插头删尾插尾删效率高 3.也支持随机访问。 缺点1.中间插入删除很难搞 每个buff数据不一样大效率高会影响随机访问的效率变低。每个buff数组固定大小牺牲中间插入删除的效率随机访问效率就变高了。 2.没有vector和list优点极致。 与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是比vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目能看到的一个应用就是STL用其作为stack和queue的底层数据结构。
5.3 为什么选择deque作为stack和queue的底层默认容器 stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为
stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。 结合了deque的优点而完美的避开了其缺陷。