STL中的栈和队列.ppt

1、3.3可用资源STL中的栈和队列,参考书： 1.左飞编数据结构原理与经典问题求解电子, 2008.10 2.P.J.PLAUGER等著 王昕译 C+ STL中文版电力, 2002.5 3.翁惠玉数据结构：思想与实现高教, 2009.8 章小莉 北京电子科技学院 计算机科学与技术系,3.3 STL中的栈和队列,3.3.1 STL中的stack 1 stack类提供的常用方法 2 stack类的使用举例 3.3.2 STL中的queue 1 queue类提供的常用方法 2 queue类的使用举例,STL的适配器,STL中的stack类是一种适配器，是通过简单地修饰线性类deque的接口而获得的另一

2、种容器类。 适配器(Adaptor)：一种设计模式，可以将一个类的接口转换为另一个类的接口，使原本因接口不相容而不能合作的类可以一起运行。 STL中的适配器是用来修改其他组件接口的STL组件，是带有一个参数的类模板。 STL包括3种适配器： 容器适配器； 迭代器适配器； 函数适配器；,3.3.1 STL中的stack,（1）stack类提供5种常用方法,（2）stack类的使用举例,举例1：int栈的使用,#include #include #include #include using namespace std; int main() stack myStack;/定义栈 myStack.

3、push(5);/压栈 myStack.push(6); myStack.push(7); myStack.pop(); /出栈 coutmyStack.top()endl; coutmyStack.size()endl; coutmyStack.empty()endl; return 0; ,#include #include #include #include #include using namespace std; int main() ifstream inf; inf.open(temp.txt); if (!inf) cerr s; string line; while (get

4、line(inf,line)/读入一行文本 s.push(line); /压入栈 inf.close(); while (!s.empty()/栈不空，输出栈顶元素 couts.top()endl; s.pop();/弹栈 return 0; ,举例2：字符串栈的使用,3.3.2 STL中的queue,（1）queue类也是容器适配器，与stack相同，修饰deque而来。主要提供6种常用方法,（2）queue类的使用举例,举例1：int队列的使用,#include #include #include #include using namespace std; int main() queue

5、 myQueue; myQueue.push(5);myQueue.push(6);/数据入队列 myQueue.push(7); myQueue.push(8); myQueue.pop();/数据出队 coutmyQueue.front()endl; coutmyQueue.back()endl; coutmyQueue.size()endl; coutmyQueue.empty()endl; return 0; ,#include #include #include using namespace std; bool existOrNot(int num, queue myQueue)

6、while (!myQueue.empty() if (myQueue.front()=num) return true; else myQueue.pop(); return false; int main() queue memQueue; int times=12;int tmpValue; int page =4,3,2,1,4,3,5,4,3,2,1,5;/页面调度序列 for (int i=0; i12; i+) if (memQueue.size()3) memQueue.push(pagei); else if (existOrNot(pagei,memQueue)/查询页面在否 times-; else /不在，弹出第一页，调入新页 memQueue.pop(); memQueue.push(pagei); ,举例2：操作系统的内存调度算法FIFO实现,int size=memQueue.size(); while (size0)/输出当前在内存的页面值 coutmemQueue.front() ; tmpValue=memQueue.front();