第3章 栈和队列（一）

知识点回顾 线性表的定义 逻辑结构 存储结构 基本操作

本节教学内容 3.1 栈的定义和特点 3.2栈的表示和操作的实现 3.3栈与递归 3.4案例分析与实现 2018年12月31日

前言：上两次课讲了线性表，线性表的特点是：元素与元素之间是一一对应关系，在日常生活中，线性表的例子比比皆是如学生基本信息表，图书信息表等，我们可以对线性表做初始化、查找、插入、删除等操作。下面我们再来看几个现实生活中的例子，一叠盘子，一桶羽毛球，这也符合线性表的特点，元素与元素之间是一一对应的关系，但是我们只能在一端进行插入和删除，如取走盘子，放新盘子，这就是这一节课给大家讲的一种数据类型：栈。 2018年12月31日

特点：先进后出（FILO）或后进先出（LIFO） 3.1 栈的定义及特点 定义：栈(Stack)是限制在表的一端进行插入和删除 运算的线性表，通常称插入、删除的这一端为栈顶 (Top)，另一端为栈底(Bottom)。当表中没有元素时 称为空栈。 特点：先进后出（FILO）或后进先出（LIFO） an a1 a2 ……... 栈底 栈顶 ... 出栈 进栈 栈s=(a1,a2,……,an)

栈与一般线性表的区别 一般线性表 栈 栈是一种特殊（操作受限）的线性表 区别：仅在于运算规则不同 逻辑结构：一对一 存储结构：顺序表、链表 运算规则：随机、顺序存取 栈 逻辑结构：一对一 存储结构：顺序栈、链栈 运算规则：后进先出 2018年12月31日

例1： 对于一个栈，给出输入项A、B、C，如果输入项序列 由ABC组成，试给出所有可能的输出序列。 A进 A出 B进 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA 不可能产生输出序列CAB

例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？ 12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能 实现； 12345的输出可以实现，只需压入一个立即弹 出一个即可。

3.2 栈的表示和操作的实现 “进” ＝压入=PUSH（) “出” ＝弹出=POP( ) 顺序栈 链栈 2018年12月31日

3.1.1 顺序栈与顺序表 前提：一定要预设栈顶指针top！ an+1 写入：v[i]= ai 读出： x= v[i] a1 a2 ai …… 顺序表V[n] a1 a2 …… an 顺序栈S ai 栈底base 栈顶top an+1 低地址 高地址 v[i] 低地址 高地址 表头 表尾 写入：v[i]= ai 读出： x= v[i] 压入：PUSH (an+1) 弹出： POP (x) 前提：一定要预设栈顶指针top！ 2018年12月31日

顺序栈的表示 #define MAXSIZE 100 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; 2018年12月31日

基本操作 顺序栈初始化 判断顺序栈是否为空 求顺序栈的长度 清空顺序栈 销毁顺序栈 顺序栈进栈 顺序栈出栈 取顺序栈栈顶元素

顺序栈 栈空 栈满 top top top 1 2 3 4 5 A B C D E F 1 2 3 4 5 top 1 2 3 4 5 F A B C D E F 1 2 3 4 5 top 1 2 3 4 5 F top top E top top D top top C top top B top top A base base base 栈空 出栈 进栈 设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) 栈顶指针top,指向实际栈顶 后的空位置，初值指向栈底，即top=base

s 顺序栈初始化 构造一个空栈 步骤： (1)分配空间并检查空间是否分配失败，若失败则返回错误 (2)设置栈底和栈顶指针 base stacksize top 构造一个空栈 步骤： (1)分配空间并检查空间是否分配失败，若失败则返回错误 s (2)设置栈底和栈顶指针 S.top = S.base; (3)设置栈大小 2018年12月31日

顺序栈初始化 int InitStack( SqStack *S ) { S->base = (SElemType *)malloc(MAXSIZE *sizeof(SElemType )) ； if( !(S->base) ) return 0; S -> top = S -> base; S -> stackSize = MAXSIZE; return 1; } 2018年12月31日

Int StackEmpty( SqStack S ) { if(S.top == S.base) return 1; 判断顺序栈是否为空 Int StackEmpty( SqStack S ) { if(S.top == S.base) return 1; else return 0; } base top 3 1 2 2018年12月31日

int StackLength( SqStack S ) { return S.top – S.base; } 求顺序栈的长度 int StackLength( SqStack S ) { return S.top – S.base; } base top A B 2018年12月31日

清空顺序栈 int ClearStack( SqStack S ) { if( S.base ) S.top = S.base; printf(“栈已清空”); return 1; } base top 3 1 2 2018年12月31日

销毁顺序栈 Int DestroyStack( SqStack *S ) { if( S->base ) free (S->base) ; S->stacksize = 0; S->base = S->top = NULL; } printf(“栈已销毁”); return 1; 2018年12月31日

顺序栈进栈 (1)判断是否栈满，若满则出错 (2)元素e压入栈顶 (3)栈顶指针加1 *(S->top)=e; A B C top base int Push( SqStack *S, SElemType e) { if( S->top – S->base== S->stacksize ) // 栈满 return 0; *(S->top)++=e; return 1; } *(S->top)=e; S->top++; 2018年12月31日

顺序栈出栈 (1)判断是否栈空，若空则出错 (2)获取栈顶元素e (3)栈顶指针减1 互换顺序？ A B C top base int Pop( SqStack *S, SElemType *e) { if( S->top == S->base ) // 栈空 return 0; S->top = S->top -1; *e＝ *(S->top); return 1; } 互换顺序？ 2018年12月31日

取顺序栈栈顶元素 判断是否空栈，若空则返回错误 否则通过栈顶指针获取栈顶元素 *e = *( S.top -- ); ??? A B C top base 判断是否空栈，若空则返回错误 否则通过栈顶指针获取栈顶元素 Status GetTop( SqStack S, SElemType *e) { if( S.top == S.base ) return ERROR; // 栈空 *e = *( S.top – 1 ); return OK; } *e = *( S.top -- ); ??? 2018年12月31日

typedef struct StackNode { SElemType data; struct StackNode *next; 3.1.2 链栈的表示 运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针 data next 栈顶 栈底 ∧ S typedef struct StackNode { SElemType data; struct StackNode *next; } StackNode, *LinkStack; LinkStack S; 2018年12月31日

void InitStack(LinkStack &S ) { S=NULL; } 链栈的初始化 ∧ S void InitStack(LinkStack &S ) { S=NULL; } 2018年12月31日

判断链栈是否为空 Status StackEmpty(LinkStack S) { if (S==NULL) return TRUE; else return FALSE; } 2018年12月31日

链栈进栈 p ∧ S Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月31日

链栈进栈 p ∧ S e Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月31日

链栈进栈 p ∧ S e Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月31日

链栈进栈 S p ∧ S e Status Push(LinkStack &S , SElemType e) { p=new StackNode; //生成新结点p if (!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; } 2018年12月31日

e = S-> data; p = S; S = S-> next; 链栈出栈 ∧ S A e = ‘A’ Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月31日

e = S-> data; p = S; S = S-> next; 链栈出栈 ∧ S A e = ‘A’ p Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月31日

e = S-> data; p = S; S = S-> next; 链栈出栈 ∧ S A e = ‘A’ p S Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月31日

e = S-> data; p = S; S = S-> next; 链栈出栈 e = ‘A’ S ∧ Status Pop (LinkStack &S,SElemType &e) {if (S==NULL) return ERROR; e = S-> data; p = S; S = S-> next; delete p; return OK; } 2018年12月31日

SElemType GetTop(LinkStack S) { 取链栈栈顶元素 SElemType GetTop(LinkStack S) { if (S==NULL) exit(1)； else return S–>data; } 2018年12月31日

3.3 　栈与递归 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 long Fact ( long n ) { if ( n == 0) return 1; else return n * Fact (n-1); } 2018年12月31日

有人送了我金、银、铜、铁、木五个宝箱，我想打开金箱子，却没有打开这个箱子的钥匙。 在金箱子上面写着一句话：“打开我的钥匙装在银箱子里。” 于是我来到银箱子前，发现还是没有打开银箱子的钥匙。 银箱子上也写着一句话：“打开我的钥匙装在铜箱子里。” 于是我再来到铜箱子前，发现还是没有打开铜箱子的钥匙。 铜箱子上也写着一句话：“打开我的钥匙装在铁箱子里。” 于是我又来到了铁箱子前，发现还是没有打开铁箱子的钥匙。 铁箱子上也写着一句话：“打开我的钥匙装在木箱子里。” 2018年12月31日

并从木箱里拿出铁箱子的钥匙，打开了铁箱， 从铁箱里拿了出铜箱的钥匙，打开了铜箱， 再从铜箱里拿出银箱的钥匙打开了银箱， 我来到木箱子前，打开了木箱， 并从木箱里拿出铁箱子的钥匙，打开了铁箱， 从铁箱里拿了出铜箱的钥匙，打开了铜箱， 再从铜箱里拿出银箱的钥匙打开了银箱， 最后从银箱里取出金箱的钥匙，打开了我想打开的金箱子。 晕吧……很啰嗦地讲了这么长一个故事。 2018年12月31日

void FindKey ( 箱子 ) { if ( 木箱子) return ; else FindKey ( 下面的箱子 ) } 2018年12月31日

当多个函数构成嵌套调用时, 遵循 后调用先返回 栈 2018年12月31日

以下三种情况常常用到递归方法 递归定义的数学函数 具有递归特性的数据结构 可递归求解的问题 2018年12月31日

1. 递归定义的数学函数: 阶乘函数: 2阶Fibonaci数列: 2018年12月31日

2. 具有递归特性的数据结构: 3. 可递归求解的问题: 树 广义表 迷宫问题 Hanoi塔问题 Root Rchild Lchild A=(a,A) 3. 可递归求解的问题: 　迷宫问题　Hanoi塔问题 2018年12月31日

用分治法求解递归问题 必备的三个条件 分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解 1、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的 2、可以通过上述转化而使问题简化 3、必须有一个明确的递归出口，或称递归的边界 2018年12月31日

else return n * Fact (n-1); //归纳项} 分治法求解递归问题算法的一般形式： void p (参数表) { if （递归结束条件）可直接求解步骤；-----基本项 else p（较小的参数）；------归纳项 } long Fact ( long n ) { if ( n == 0) return 1;//基本项 else return n * Fact (n-1); //归纳项} 2018年12月31日

递归过程的调用和返回 以求3!为例说明执行调用的过程如下图所示。 递归函数的递归过程：在递归进层(i→i+1层)时系统需要做三件事： (1) 保留本层参数与返回地址 (2) 给下层参数赋值 (3) 将程序转移到被调函数的入口 从被调用函数返回调用函数之前，递归退层(i←i+1层)系统也应完成三件工作： (1) 保存被调函数的计算结果； (2) 恢复上层参数(释放被调函数的数据区)； (3) 依照被调函数保存的返回地址，将控制转移回调用函数。

3.4案例分析与实现 数制转换 括号匹配的检验 行编辑程序

数制转换 十进制n和其它进制数的转换是计算机实现计算的基本 问题,其解决方法很多,其中一个简单算法基于下列原理: n =(n div d) 数制转换 十进制n和其它进制数的转换是计算机实现计算的基本 问题,其解决方法很多,其中一个简单算法基于下列原理: n =(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下：

n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2

void conversion( ) { initstack(s); scanf (“%”,n); while(n){ push(s,n%8); n=n/8; } while(! Stackempty(s)){ pop(s,e); printf(“%d”,e);

括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法 可用“期待的急迫程度”这个概念来描述。例： [（ [ ] [ ] ）] 1 2 3 4 5 6 7 8 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输 入的一行字符，然后逐行存入用户数据区。允许用户输 入错误，并在发现有误时可以及时更正。

行编辑程序算法如下: void lineedit( ){ initstack(s); ch=gether( ); while(ch 行编辑程序算法如下: void lineedit( ){ initstack(s); ch=gether( ); while(ch!=eof){ while(ch!=eof && ch!=‘\n’){ switch(ch){ case ‘#’ : pop(s,c); case ‘@’ : clearstack(s); default : push(s,ch); }

ch=getchar( ); } 将从栈底到栈顶的栈内字符传送至调用过程的数据区； clearstack(s); if(ch ch=getchar( ); } 将从栈底到栈顶的栈内字符传送至调用过程的数据区； clearstack(s); if(ch!=eof) ch=gethar( ); destroystack(s);

小结 掌握栈的特点，并能在相应的应用问题中正确选用 熟练掌握栈的两种存储结构的基本操作实现算法，特别应注意栈满和栈空的条件 理解递归算法执行过程中栈的状态变化过程

作业 1、设将整数1、2、3、4依次进栈，但只要出栈时栈 非空，则可将出栈操作按任何次序夹入其中，请 回答下有问题： （1）若入栈次序为push(1)，pop()，push(2)， push(3)，pop()，pop( )，push(4)，pop( )，则 出栈的数字序列为什么？ （2）能否得到出栈序列423和432？并说明为什么不 能得到或如何得到。 2、对于一个栈，给出输入项A，B，C。如果输入项 序列由A，B，C组成，试给出全部可能的输出序列。

3、设计算法判断表达式中的圆括号是否配对出现。 4、在顺序存储结构上实现栈的入栈和出栈操作。