5.栈和队列
思考
一.什么是栈和队列?(What)
1.栈的定义和特点
1.栈定义:后进先出(LIFO)
2.栈的示意图
3.栈的应用
2.队列的定义和特点
1.队列定义:先进先出
2.队列的应用:
3.栈和队列特点
4.案例引入
1.栈
2.队列
5.栈的表示和操作实现
1.栈的抽象数据类型的类型定义
2.栈的操作(8种)
3.顺序栈
4.链栈
6.栈与递归
1.递归的定义
2.递归的三种应用场景
3.递归问题
7.队列的表示和操作实现
1.回顾
2.队列的抽象数据类型定义
二.为什么需要栈和队列?(Why)
1.栈的应用
2.队列的应用
三.如何学好栈和队列?(How)
数据结构很重要!
数据结构很重要!!!
数据结构很重要!!!!
思考
1.什么是栈和队列?(What)
2.为什么需要栈和队列?(Why)
3.如何学好栈和队列?(How)
注:特别感谢青岛大学王卓老师
第3章 栈和队列.pdf
一.什么是栈和队列?(What)
回顾线性表:
1.栈的定义和特点
1.栈定义:后进先出(LIFO)
2.栈的示意图
1.入栈:
2.出栈:
3.思考:
4.栈的相关概念:
5.一般线性表与栈的不同:
3.栈的应用
2.队列的定义和特点
1.队列定义:先进先出
2.队列的应用:
3.栈和队列特点
插入 删除
栈 n+1 n
队列 n+1 1
4.案例引入
1.栈
1.进制转换
2.括号匹配的检验
2.队列
5.栈的表示和操作实现
1.栈的抽象数据类型的类型定义
2.栈的操作(8种)
3.顺序栈
1.顺序栈的基本知识
1.栈的存储方式:用数组存储,top是栈顶,base是栈低
2.空栈:base==top
3.栈满:top=stacksize
4.上溢:栈已经满了,又要压入元素
5.下溢:栈已经空了,还要弹出元素
2.顺序栈的表示:
注:俩个指针加减(同一数组)/也可以用数组下标=算这俩个元素之间差几个元素。
1.计算栈中元素个数
3.栈的初始化
Status InitStack(SqStack &S){
1.开辟一个新的数组
S.base=new SElemType[MAXSIZE];
if(!S.base) exit (OVERFLOW);
S.top=S.base;
S.stacksize=MAXSIZE;
}
4.判断顺序栈是否为空
Status StackEmpty(SqStack S){
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
5.求顺序栈长度
int StackLength(SqStack S){
retrun S.top-S.base;
}
6.清空顺序栈
Status ClearStack(SqStatck S){
if(S.base) S.top=S.base;
return ok;
}
7.销毁顺序栈
Status DestroyStack(SqStack &S){
if(S.base){
delete S.base;
S.stacksize=0;
S.base=S.top=Null;
}
return ok;
}
8.顺序栈的入栈
1.判断是否栈满,若满则出错
2.元素e压入栈顶
3.栈顶指针加1
Status Push(SqStack &S,SElemType e){
if(S.top-S.base==S.stacksize){
return ERROR;
}
*S.top=e; //*S.top是取出S.top指针所指的元素
S.top++; //top指针上移一个位置
return ok;
}
*号的优先级高,++后面运算
9.顺序栈的出栈
1.判断是否栈空,若空栈则出错(下溢)
2.获取栈顶元素e
3.栈顶指针减1
Status Pop(SqStack &S, SElemType &e){
if(S.top==S.base){
retrun Error;
}
--S.top;
e=S.top;
return ok;
}
4.链栈
1.链栈的表示
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;
2.链栈的初始化
3.判断链栈是否为空
4.链栈入栈
5.链栈的出栈
6.取栈顶元素
6.栈与递归
1.递归的定义
2.递归的三种应用场景
1.递归定义的数学函数
2.具有递归特性的数据结构
3.可递归求解的问题
3.递归问题
1.递归是分治法的一种
2.递归算法的一般形式
3.函数调用过程
4.多个函数构成嵌套调用
1.求n!过程
if(n==0) return 1
else return n*Fact(n-1)
2.递归函数调用的实现
递归工作栈记录:实参,局部变量,返回地址
3.系统栈
先押栈,押满后在弹出,结果返回到地址
4.递归优缺点:
优点:结构清晰,程序易读
缺点:时间开销大
保存状态信息,入栈。
返回是要出栈,恢复状态信息。
尾递归-》循环递归
long Fact(long n){
t=1;
for(i=1;i<=n;i++) t=t*i;
return t;
}
单向递归-》循环结构
Long Fib(long n){
if(n==1 || n==2) return 1;
else{
t1=1;t2=1;
for(i=3;i<=n;i++){
t3=t1+t2;
t1=t2;t2=t3;
}
return t3;
}
}
7.队列的表示和操作实现
1.回顾
头删,尾插
2.相关术语
3.队列的相关概念
4.队列的常见应用
2.队列的抽象数据类型定义
1.顺序队列表示和实现
2.顺序表的操作
1.真假溢出
真溢出:front=0 rear=MAXQSIZE
假溢出:front!=0 rear=MAXQSIZE
2.解决假溢出的方法
3.引入循环队列
4.解决如何区别队空和队满相等的情况
5.少用一个元素空间
6.求队列的长度
7.循环队列入队
8.循环队列出队
9.取队头元素
3.队列链表的操作与实现
1.链队列运算指针变化状况
2.链队列初始化
3.销毁链队列
4.将元素e入队
5.链队列出队
6.链队列的队头元素
二.为什么需要栈和队列?(Why)
1.栈的应用
2.队列的应用
三.如何学好栈和队列?(How)
1.chunk it up:指的是把要学习的知识点进行切碎,变成一个有机的整体。
先学底层一个个小知识点,不断积累,一点点串成烤串。(听课)
2.deliberate practicing:做刻意练习,多做题,多实践。
自己练习、梳理、总结(做)
3.feedback:一种是主动式反馈,还有一种叫被动式反馈。
a.主动式反馈:主动去学习,看到别人,原来这个地方可以这么写,这么写之后就特别的漂亮,而且的话程序跑的也很快。(思)
b.被动式反馈:code review。如说这是faker的直播的视角,通过他看,你看他怎么操作,你会知道哦,原来为什么他这么强或者什么?什么地方要学习?(学)
搞清楚,栈、队列的定义,各种操作,扎实基础。
清楚栈、队列的联系与区别。
用心
用心、用心
用心、用心、用心
知其然、知其所以然!!!
多学习,多思考,多总结,多输出,多交流 (five kills)~~~