无锡响应式网站设计,wordpress站群管理系统,网站建设学校培训学校,写方案的网站摘要
本文主要是介绍一下stack、queue、priority_queue的使用以及模拟实现#xff0c;文章末附上代码以及思维导图。
目录
摘要
一、stack的介绍和使用
1、stack的介绍
2、stack的使用
3、stack的模拟实现
二、queue的介绍和使用
1、queue的介绍
2、queue的使用
3、…摘要
本文主要是介绍一下stack、queue、priority_queue的使用以及模拟实现文章末附上代码以及思维导图。
目录
摘要
一、stack的介绍和使用
1、stack的介绍
2、stack的使用
3、stack的模拟实现
二、queue的介绍和使用
1、queue的介绍
2、queue的使用
3、queue的模拟实现
三、priority_queue的介绍和使用
1、priority_queue的介绍
2、priority_queue的使用
3、priority_queue的模拟实现
四、代码
1、stack
2、queue
3、priority_queue
五、思维导图 一、stack的介绍和使用
1、stack的介绍
和之前一样这里也是直接介绍一下文档使用方式和之前的模板大差不差如下方截图就是cplusplus的介绍下面四点就是文档上面的翻译其他的就不详细说了数据结构里面有更加详细的介绍。
1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作
empty判空操作
back获取尾部元素操作
push_back尾部插入元素操作
pop_back尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器默认情况下使用deque。 2、stack的使用
下面的一个表格就是常用的几个函数与接口说明就不一一说明怎么使用了和之前vector、list、string所演示的都差不多。
函数说明接口说明stack()构造空的栈empty()检测stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出
3、stack的模拟实现
这里是直接利用vector作为一个缺省值直接用模板去创建一栈这样都可以直接复用vector的函数这样实现起来就十分容易加上轻松了如下方代码所示因为栈不支持迭代器不能遍历只能一次出一个结果如下方图片所示其实这里是我康吃康吃写了一个类似c写的那种然后看了一下源码大佬不愧是大佬好轻松。 namespace ly1
{templateclass T, class Container vectorTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void Test_Stack(){stackint s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout s1.top() ;s1.pop();}cout endl;}
} 二、queue的介绍和使用
1、queue的介绍
和之前一样这里也是直接介绍一下文档使用方式和之前的模板大差不差如下方截图就是cplusplus的介绍下面四点就是文档上面的翻译其他的就不详细说了数据结构里面有更加详细的介绍。
1. 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。
2. 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列。
3. 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty检测队列是否为空
size返回队列中有效元素的个数
front返回队头元素的引用
back返回队尾元素的引用
push_back在队列尾部入队列
pop_front在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。 2、queue的使用
下面的一个表格就是常用的几个函数与接口说明就不一一说明怎么使用了和之前vector、list、string所演示的都差不多。
函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列
3、queue的模拟实现
这里也是利用复用直接写的代码和测试如下。 namespace ly2
{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 q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout q1.front() ;q1.pop();}cout endl;}
}
三、priority_queue的介绍和使用
1、priority_queue的介绍
下面就是优先队列的文档介绍。
1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作
empty()检测容器是否为空size()返回容器中有效元素个数
front()返回容器中第一个元素的引用
push_back()在容器尾部插入元素
pop_back()删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。
6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 2、priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。
函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回 falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
3、priority_queue的模拟实现
这个原理有点像我之前写数据结构的堆实现方法也差不多这个优先队列可以进行排序他默认是降序代码实现与测试如下。 namespace ly3
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{public:priority_queue() : c() {}templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first, last){int count c.size();int root ((count - 2) 1);for (; root 0; root--)AdjustDown(root);}void push(const T data){c.push_back(data);AdjustUP(c.size() - 1);}void pop(){if (empty())return;swap(c.front(), c.back());c.pop_back();AdjustDown(0);}size_t size()const{return c.size();}bool empty()const{return c.empty();}const T top()const{return c.front();}private:void AdjustUP(int child){int parent ((child - 1) 1);while (child){if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);child parent;parent ((child - 1) 1);}else{return;}}}void AdjustDown(int parent){size_t child parent * 2 1;while (child c.size()){if (child 1 c.size() Compare()(c[child], c[child 1]))child 1;if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);parent child;child parent * 2 1;}elsereturn;}}private:Container c;};void Test_Priority_Queue(){ly3::priority_queueint q1;q1.push(5);q1.push(1);q1.push(4);q1.push(2);q1.push(3);q1.push(6);while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;}
}
四、代码
1、stack
#pragma oncenamespace ly1
{templateclass T, class Container vectorTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void Test_Stack(){stackint s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout s1.top() ;s1.pop();}cout endl;}
}
2、queue
#pragma oncenamespace ly2
{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 q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout q1.front() ;q1.pop();}cout endl;}
}
3、priority_queue
#pragma oncenamespace ly3
{templateclass Tstruct less{bool operator()(const T left, const T right){return left right;}};templateclass Tstruct greater{bool operator()(const T left, const T right){return left right;}};templateclass T, class Container std::vectorT, class Compare lessTclass priority_queue{public:priority_queue() : c() {}templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first, last){int count c.size();int root ((count - 2) 1);for (; root 0; root--)AdjustDown(root);}void push(const T data){c.push_back(data);AdjustUP(c.size() - 1);}void pop(){if (empty())return;swap(c.front(), c.back());c.pop_back();AdjustDown(0);}size_t size()const{return c.size();}bool empty()const{return c.empty();}const T top()const{return c.front();}private:void AdjustUP(int child){int parent ((child - 1) 1);while (child){if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);child parent;parent ((child - 1) 1);}else{return;}}}void AdjustDown(int parent){size_t child parent * 2 1;while (child c.size()){if (child 1 c.size() Compare()(c[child], c[child 1]))child 1;if (Compare()(c[parent], c[child])){swap(c[child], c[parent]);parent child;child parent * 2 1;}elsereturn;}}private:Container c;};void Test_Priority_Queue(){ly3::priority_queueint q1;q1.push(5);q1.push(1);q1.push(4);q1.push(2);q1.push(3);q1.push(6);while (!q1.empty()){cout q1.top() ;q1.pop();}cout endl;}
}五、思维导图
