文档介绍：3 栈与队列(3)
教学目标
掌握栈的特点，并能在相应的应用问题中正确选用。
熟练掌握顺序栈的实现及其基本操作。
了解递归的概念
掌握队列的特点，并能在相应的应用问题中正确选用。
熟练掌握循环队列和链队列的实现算法
了解STL中的3 栈与队列(3)
教学目标
掌握栈的特点，并能在相应的应用问题中正确选用。
熟练掌握顺序栈的实现及其基本操作。
了解递归的概念
掌握队列的特点，并能在相应的应用问题中正确选用。
熟练掌握循环队列和链队列的实现算法
了解STL中的stack,queue的基本使用方法
栈的定义
栈的实现
栈的应用举例
队列的定义
队列的实现
队列的应用举例
栈、队列与STL（标准模板库）
教学内容
栈、队列与STL
stack与栈
queue与队列
stack 举例：10进制向k进制转换
#include <stack>
void baseChange(int n, int k){
stack<int> S;
while(n>0){
(n%k);
n = n/k;
}
while(()==false){
cout<<();
();
}
}
int main()
{
baseChange(120, 8);
return 0;
}
// （使用标准模板库STL）：
struct Pos{ //坐标
int x , y , steps;
};
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; // 东南西北四个方向
const int M=6, N=8; // 迷宫的实际行,列
int Maze[M][N];
bool visited[M][N];
Pos S, T; //起点和终点
int main()
{
// 输入迷宫的数据以及起点和终点
// ……
cout<<mazeBFS(); // 见下页
return 0;
}
queue举例：求迷宫最短路径的长度
int mazeBFS( ) {
=0;
fill(&visited[0][0], &visited[M-1][N-1]+1, false); // 清空visited数组
Queue<Pos> Q; // 队列初始化
(S); visited[0][0]=true; // 起点入队
while (!()) { // 队列不空
Pos p=(); (); // 取队头元素, 元素出队
if ( == && ==) return ; // 成功到达终点
for(int i=0; i<4; i++) { // 处理4个direction
Pos e={+dir[i][0], +dir[i][1], +1};
if (>=M || <0 || >=N || <0) continue;
if(visited[][] || Maze[][]==0) continue;
(e); visited[][]=true; // 入队, 置访问标记
}
}
return -1; // 路径不通
}
本章小结
掌握栈和队列的特点，并能在相应的应用问题中正确选用
熟练掌握栈的顺序栈的进栈出栈算法，特别应注意栈满和栈空的条件
熟练掌握循环队列和链式队列的进队出队算法，特别注意队满和队空的条件
了解递归算法
内容
要求
栈和队列的概念和结构特点
熟练掌握
栈和队列的抽象数据类型定义
掌握
栈的顺序存储方式的实现
熟练掌握
栈的链式存储方式的实现
基本掌握
链式队列和循环队列的实现
熟练掌握
栈的应用（进制转换，括号匹配）
熟练掌握
栈与递归（递归实现回溯法）
掌握
队列的应用（事件模拟）
基本掌握
利用STL中的stack,queue解决问题
掌握
本章要求：