《栈与队列.ppt》由会员分享,可在线阅读,更多相关《栈与队列.ppt(11页珍藏版)》请在三一文库上搜索。
1、3 栈与队列(3),教学目标,掌握栈的特点,并能在相应的应用问题中正确选用。 熟练掌握顺序栈的实现及其基本操作。 了解递归的概念 掌握队列的特点,并能在相应的应用问题中正确选用。 熟练掌握循环队列和链队列的实现算法 了解STL中的stack,queue的基本使用方法,3.1 栈的定义 3.2 栈的实现 3.3 栈的应用举例 3.4 队列的定义 3.5 队列的实现 3.6 队列的应用举例 3.7 栈、队列与STL(标准模板库),教学内容,3.7 栈、队列与STL,stack与栈 queue与队列,stack 举例:10进制向k进制转换,#include void baseChange(int n
2、, int k) stack S; while(n0) S.push(n%k); n = n/k; while(S.empty()=false) coutS.top(); S.pop(); ,int main() baseChange(120, 8); return 0; ,queue举例:舞伴,#include struct Partner string male, female; ; queue ManQ, WomanQ; queue DancerQ; void Prepare(int ManNum, int WomanNum) string name; for(int i=0; inam
3、e; ManQ.push(name); for(int i=0; iname; WomanQ.push(name); ,void DancePartner (int count) / count 为舞曲的播放轮次 string sMale,sFemale; Partner partner; for(int i=1; i=count; i+) cout“当前轮次:“iendl; / music begin while(!ManQ.empty() /舞曲结束,配对拆开进各自队列 ,/ (使用标准模板库STL): struct Pos /坐标 int x , y , steps; ; int dir
4、42 = 0,1,1,0,0,-1,-1,0; / 东南西北四个方向 const int M=6, N=8; / 迷宫的实际行,列 int MazeMN; bool visitedMN; Pos S, T; /起点和终点 int main() / 输入迷宫的数据以及起点和终点 / coutmazeBFS(); / 见下页 return 0; ,queue举例:求迷宫最短路径的长度,int mazeBFS( ) S.steps=0; fill( / 路径不通 ,本章小结,掌握栈和队列的特点,并能在相应的应用问题中正确选用 熟练掌握栈的顺序栈的进栈出栈算法,特别应注意栈满和栈空的条件 熟练掌握循环队列和链式队列的进队出队算法,特别注意队满和队空的条件 了解递归算法,本章要求:,