STL中的栈和队列.ppt

《STL中的栈和队列.ppt》由会员分享，可在线阅读，更多相关《STL中的栈和队列.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.3可用资源可用资源STL中中的栈和队列的栈和队列参考书：参考书：参考书：参考书：1.1.左飞编左飞编左飞编左飞编数据结构原理与经典问题求解数据结构原理与经典问题求解数据结构原理与经典问题求解数据结构原理与经典问题求解电子电子电子电子,2008.10,2008.102.P.J.PLAUGER2.P.J.PLAUGER等著等著等著等著 王昕译王昕译王昕译王昕译 C+STLC+STL中文版中文版中文版中文版电力电力电力电力,2002.5,2002.53.3.翁惠玉翁惠玉翁惠玉翁惠玉数据结构：思想与实现数据结构：思想与实现数据结构：思想与实现数据结构：思想与实现高教高教高教高教,2009.8,20

2、09.8章小莉章小莉章小莉章小莉北京电子科技学院北京电子科技学院北京电子科技学院北京电子科技学院计算机科学与技术系计算机科学与技术系计算机科学与技术系计算机科学与技术系3.3 STL中的栈和队列中的栈和队列3.3.1 STL中的中的stack1 stack1 stack类提供的常用方法类提供的常用方法类提供的常用方法类提供的常用方法2 stack2 stack类的使用举例类的使用举例类的使用举例类的使用举例3.3.2 STL中的中的queue1 queue1 queue类提供的常用方法类提供的常用方法类提供的常用方法类提供的常用方法2 queue2 queue类的使用举例类的使用举例类的使用举

3、例类的使用举例STL的适配器的适配器l lSTLSTL中的中的中的中的stackstack类是一种适配器，是通过简单地修饰类是一种适配器，是通过简单地修饰类是一种适配器，是通过简单地修饰类是一种适配器，是通过简单地修饰线性类线性类线性类线性类dequedeque的接口而获得的另一种容器类。的接口而获得的另一种容器类。的接口而获得的另一种容器类。的接口而获得的另一种容器类。l l适配器适配器适配器适配器(Adaptor)(Adaptor)：一种：一种：一种：一种设计模式设计模式设计模式设计模式，可以将一个类的，可以将一个类的，可以将一个类的，可以将一个类的接口转换为另一个类的接口，使原本因接口不

4、相容接口转换为另一个类的接口，使原本因接口不相容接口转换为另一个类的接口，使原本因接口不相容接口转换为另一个类的接口，使原本因接口不相容而不能合作的类可以一起运行。而不能合作的类可以一起运行。而不能合作的类可以一起运行。而不能合作的类可以一起运行。l lSTLSTL中的适配器是用来修改其他组件接口的中的适配器是用来修改其他组件接口的中的适配器是用来修改其他组件接口的中的适配器是用来修改其他组件接口的STLSTL组件，组件，组件，组件，是带有一个参数的类模板。是带有一个参数的类模板。是带有一个参数的类模板。是带有一个参数的类模板。l lSTLSTL包括包括包括包括3 3种适配器：种适配器：种适配

5、器：种适配器：1.1.容器适配器；容器适配器；容器适配器；容器适配器；2.2.迭代器适配器；迭代器适配器；迭代器适配器；迭代器适配器；3.3.函数适配器；函数适配器；函数适配器；函数适配器；3.3.1 STL中的中的stack（1 1）stackstack类提供类提供类提供类提供5 5种常用方法种常用方法种常用方法种常用方法方法方法方法方法说明说明说明说明void void push(const_typepush(const_type&x)&x)用于将一个新元素压入栈中用于将一个新元素压入栈中用于将一个新元素压入栈中用于将一个新元素压入栈中void pop()void pop()用于栈不为空，

6、弹出栈中一个元素用于栈不为空，弹出栈中一个元素用于栈不为空，弹出栈中一个元素用于栈不为空，弹出栈中一个元素value_typevalue_type&top()&top()用于返回栈顶元素的引用，如果栈为用于返回栈顶元素的引用，如果栈为用于返回栈顶元素的引用，如果栈为用于返回栈顶元素的引用，如果栈为空，结果为未定义；否则，返回的是空，结果为未定义；否则，返回的是空，结果为未定义；否则，返回的是空，结果为未定义；否则，返回的是一个引用一个引用一个引用一个引用size_typesize_type size()size()用于用于用于用于constconst返回栈中元素的个数返回栈中元素的个数返回栈中

7、元素的个数返回栈中元素的个数boolbool empty()empty()用于用于用于用于constconst判断栈是否为空，若空，返判断栈是否为空，若空，返判断栈是否为空，若空，返判断栈是否为空，若空，返回回回回TRUETRUE，否则返回，否则返回，否则返回，否则返回FALSEFALSE（2）stack类的使用举例类的使用举例举例举例1：int栈的使用栈的使用#include#include#include#include#include#include#include#include#include#include using namespace std;using namespace s

8、td;intint main()main()ifstreamifstream infinf;inf.open(temp.txtinf.open(temp.txt););if(!if(!infinf)cerrcerrcannot open file for input!cannot open file for input!endlendl;return EXIT_FAILURE;return EXIT_FAILURE;stack s;stack s;string line;string line;while(while(getline(inf,linegetline(inf,line)/读入一行

9、文本读入一行文本读入一行文本读入一行文本s.push(lines.push(line););/压入栈压入栈压入栈压入栈 inf.closeinf.close();();while(!while(!s.emptys.empty()()/栈不空，输出栈顶元素栈不空，输出栈顶元素栈不空，输出栈顶元素栈不空，输出栈顶元素coutcouts.tops.top()()endlendl;s.pops.pop();();/弹栈弹栈弹栈弹栈 return 0return 0;3.3.2 STL中的中的queue（1 1）queuequeue类也是容器适配器，与类也是容器适配器，与类也是容器适配器，与类也是容器适

10、配器，与stackstack相同，修饰相同，修饰相同，修饰相同，修饰dequedeque而来。主要提供而来。主要提供而来。主要提供而来。主要提供6 6种常用方法种常用方法种常用方法种常用方法方法方法方法方法说明说明说明说明void void push(const_typepush(const_type&x)&x)用于将一个新元素接到队列的末端用于将一个新元素接到队列的末端用于将一个新元素接到队列的末端用于将一个新元素接到队列的末端void pop()void pop()用于弹出队列中的第一个元素，返回用于弹出队列中的第一个元素，返回用于弹出队列中的第一个元素，返回用于弹出队列中的第一个元素，返

11、回值是值是值是值是voidvoidvalue_typevalue_type&front()&front()用于存取队列中的第一个元素，返回用于存取队列中的第一个元素，返回用于存取队列中的第一个元素，返回用于存取队列中的第一个元素，返回的是一个引用的是一个引用的是一个引用的是一个引用size_typesize_type&back()&back()用于存取队列中的最后一个元素，返用于存取队列中的最后一个元素，返用于存取队列中的最后一个元素，返用于存取队列中的最后一个元素，返回的是一个引用回的是一个引用回的是一个引用回的是一个引用size_typesize_type size()size()用于用于

12、用于用于constconst返回队列中元素的个数返回队列中元素的个数返回队列中元素的个数返回队列中元素的个数boolbool empty()empty()用于用于用于用于constconst判断队列是否为空，若空，判断队列是否为空，若空，判断队列是否为空，若空，判断队列是否为空，若空，返回返回返回返回TRUETRUE，否则返回，否则返回，否则返回，否则返回FALSEFALSE（2）queue类的使用举例类的使用举例举例举例1：int队列的使用队列的使用#include#include#include#include#include#include using namespace std;usi

13、ng namespace std;boolbool existOrNot(intexistOrNot(int num,num,queue queue myQueuemyQueue)while(!while(!myQueue.emptymyQueue.empty()()if(if(myQueue.frontmyQueue.front()=num)return true;else()=num)return true;else myQueue.popmyQueue.pop();();return false;return false;intint main()main()queue queue me

14、mQueuememQueue;intint times=12;times=12;intint tmpValuetmpValue;intint page=page=4,3,2,1,4,3,5,4,3,2,1,54,3,2,1,4,3,5,4,3,2,1,5;/页面调度序列页面调度序列页面调度序列页面调度序列for(for(intint i=0;i12;i+)i=0;i12;i+)if(if(memQueue.sizememQueue.size()3)()0)while(size0)/输出当前在内存的页面值输出当前在内存的页面值输出当前在内存的页面值输出当前在内存的页面值coutcoutmemQueue.frontmemQueue.front();();tmpValuetmpValue=memQueue.frontmemQueue.front();();memQueue.popmemQueue.pop();();memQueue.push(tmpValuememQueue.push(tmpValue););size-;size-;coutcoutendlendl;coutcout使用使用使用使用FIFOFIFO策略时，共发生缺页中断策略时，共发生缺页中断策略时，共发生缺页中断策略时，共发生缺页中断timestimes次次次次.endlendl;return 0return 0;