数据结构栈和队列学习教案.pptx

会计学3.1栈3.1.1栈的定义(dìngyì)：InitStack(S)初始化一个(yīɡè)空栈S。二、进栈、出栈图例(túlì)3.1.2栈的表示(biǎoshì)和实现一、顺序(shùnxù)栈2、顺序(shùnxù)栈中的进栈和出栈图例3.顺序(shùnxù)栈的基本操作特点3、顺序(shùnxù)栈基本操作的实现2）判栈空3）判栈满4）进栈5）出栈6）取栈顶元素(yuánsù)〖例〗设有一个空栈，栈顶指针为1000H，现有输入(shūrù)序列为12345，PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，输出序列为______，栈顶指针为_______〖例〗在一个n个单元的顺序栈中，假定以地址(dìzhǐ)高端(下标为n-1的单元)作为栈底，则向栈中压入一个元素时，栈顶指针top的变化是______
top不变 top=n top=top-1 top=top+1〖例〗若一个栈的输入(shūrù)序列是1，2，…，n，输出序列的第一个元素是n，则第i个输出元素是______
n-i n-i+1 i n-i-1方法一：将栈的容量加到足够大，但这种方法由于(yóuyú)事先难以估计容量，有可能浪费空间。利用栈“栈底位置(wèizhi)不变，而栈顶位置(wèizhi)动态变化”的特性，为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。6、两栈共享的数据结构(shùjùjiéɡòu)定义7、两栈共享基本操作的实现(shíxiàn)2）两栈共享的进栈操作(cāozuò)算法3）两栈共享的出栈操作(cāozuò)算法〖例〗设有一个输入序列123，元素经过一个栈到达输出序列，并且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列？
分析：每一元素只能做一次入栈、一次出栈，可以入栈后停留一段时间，然后到达输出序列。那么(nàme)该题就变为如何安排三次push操作（s）和pop操作(x)的顺序以得到尽量多的不同的输出。
sssxxx:321ssxsxx:231ssxxsx:213
sxsxsx:123sxssxx:132补充：
如果进栈的序列为123456，能否(nénɡfǒu)得到435612和
135426的出栈序列，并说明为什么不能得到或
者如何得到（写出以‘S’表示进栈,‘x’表示出栈
的栈操作序列）二、链栈链栈的基本操作特点(tèdiǎn)1、链栈的存储结构(jiégòu)定义2、链栈基本操作的实现(shíxiàn)2)链栈的出栈操作(cāozuò)3.1.3栈的应用(yìngyòng)举例分析可能出现(chūxiàn)的不匹配的情况:算法(suànfǎ)的设计思想:括号匹配(pǐpèi)算法:例2、数制转换(zhuǎnhuàn)十进制转换为二进制（例如：25）
有余数是1没余数是0
25除2=12......1
12除2=6......0
6除2=3......0
3除2=1......1
1除2=0......1
然后我们将余数(yúshù)按“从下往上”的顺序书写就是：11001，那么这个11001就是十进制25的二进制形式数制转换算法
voidConversion(intN)
/*对任意非负十进制数N，打印(dǎyìn)等值的八进制数*/
{StackS;intx;/*S为顺序栈或链栈*/
InitStack(&S);
while(N>0)
{x=N%8;Push(&S,x);N=N/8;}
while(！IsEmpty(S))
{Pop(&S,&x);printf(“%d”,x);}
}3.1.4栈与递归的实现(shíxiàn)从被调用函数返回调用函数之前,应该(yīnggāi)完成下列三项任务：多个函数(hánshù)嵌套调用的规则是：递归工作栈:递归函数执行过程中占用的数据区
工作记录:每一层的参数、局部变量、返回地
址等构成的记录(数据区)
当前活动记录:栈顶工作记录(当前函数数据区)
当前环境指针:递归工作栈的栈顶指针,指向(zhǐxiànɡ)当前
活动记录。(指示当前函数数据区)例Hanoi塔问题：有3个塔座x,y,z,在塔座x上插有n个大小不同的圆盘(yuánpán),从小到大且自上而下编号为1,2,…n;按规则将它们一个个搬到塔座z上,y可用作辅助塔座。
规则为：
(1)每次只能移动一个圆盘(yuánpán)；
(2)圆盘(yuánpán)可放在任意塔座上；
(3)任何时刻塔座上都不得将大盘压在小盘之上。voidhanoi(intn;charx,chary,charz)
/*将塔座x上按直径由小到大且至上而下编号为1至n的
n个圆盘(yuánpán)按规则搬到塔座z上，y可用作辅助塔座。