《数据结构》课程PPT教学课件（2012）第3章 栈和队列 3.3

交第2章作业(2.82.102.212.222.342.35)； 周四下午/晚上第1次上机；请各班负责人到机房上机 时卡；上机内容：线性表的插入与删除 基本要求：试用C语言编写一个高效算法，将一循环 单链表就地逆置。 高级要求：请用循环链表方式制作一种彩票选号器

1 交第2章作业（ 2.8 2.10 2.21 2.22 2.34 2.35）； 周四下午/ 晚上第1次上机；请各班负责人到机房上机 时卡；上机内容：线性表的插入与删除 试用C语言编写一个 算法，将一循环 单链表就地逆置。 请用循环链表方式制作一种彩票选号器

第三章栈和队列 3.1栈(Stack) 3.2X队列(Queue) 1. 定义 1.定义 2.逻辑结构 2.逻辑结构 3.存储结构 3.存储结构 4.运算规则 4.运算规则 5.实现方式 5.实现方式

2 3.1 栈（Stack） 3.2 队列（Queue） 第三章 栈和队列 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式

Q4:为什么要设计堆栈？它有什么独特用途？ 调用函数或子程序非它莫属； 2.递归运算的有力工具； 3.用于保护现场和恢复现场； 4.简化了程序设计的问题。 下面用4个例子来帮助理解堆栈：

3 Q4：为什么要设计堆栈？它有什么独特用途？ 1. 调用函数或子程序非它莫属； 2. 递归运算的有力工具； 3. 用于保护现场和恢复现场； 4. 简化了程序设计的问题。 下面用4个例子来帮助理解堆栈：

例1（严题集3.10③）阅读下列递归过程，说明其功能。 void test(int&sum）f int x; 输入x10 输入 2/输入3输入4 输入5=0 scanf(x); 断点地址 if6x=产0)sum=0; 入栈 elseftest(sum);sum+=x; printf(sum); 输出 输出 输出 输出 sum= 注意：最先 输出sum三 sum=sum= sum三0 x4+x3 x4+x3 0+x4 输入的数据 x4+x3+x2+x1 +x2 1最后才被 程序功能：对键盘输入数 累加 据求和，直到输入0结束

4 void test(int &sum){ int x; scanf(x); if(x==0)sum=0; else{ ;sum+=x;} printf(sum); } 断点地址 入栈 例1（严题集3.10③）阅读下列递归过程，说明其功能。 输入x1≠0 输入x2 输入x3 输入x4 输入x5＝0 输出 sum＝0 输出 sum＝ 0+x4 输出 sum＝ x4+x3 输出 sum＝ x4+x3 +x2 输出sum＝ x4+x3 +x2+x1 注意：最先 输入的数据 x1 最后才被 累加 程序功能：对键盘输入数 据求和，直到输入0结束

例2（严题集3.1）一个栈的输入序列为1,2,3，若 在入栈的过程中允许出栈，则可能得到的出栈序列 是什么？ 答： 可以通过穷举所有可能性来求解： ①1入1出， 2入2出，3入3出，即123： ②1入1出，2、3入，3、2出， 即132； ③1、2入，2出，3入3出， 即231； ④1、2入，2、1出，3入3出， 即213； ⑤1、2、3入，3、2、1出， 即321； 合计有5种可能性

5 例2（严题集3.1）一个栈的输入序列为1,2,3，若 在入栈的过程中允许出栈，则可能得到的出栈序列 是什么？ 答： 可以通过穷举所有可能性来求解： ① 1入1出， 2入2出，3入3出， 即123； ② 1入1出， 2、3入，3、2出， 即132； ③ 1、2入，2出， 3入3出， 即231； ④ 1、2入，2、1出，3入3出， 即213； ⑤ 1、2、3入，3、2、1出， 即321； 合计有5种可能性

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

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

例4： 计算机系2001年考研题 设依次进入一个栈的元素序列为c,a,b,d, 则可得到出栈的元素序列是： A)a,b,c,d B)c,d,a,b C)/b,c,d,a D)a,c,d,b 答： A)、D)可以， B) C)不行。 讨论：有无通用的判别原则？ 有！若输入序列是，PPkP1.(PPkP) 定不存在这样的输出序列，PPP k” 即对于输入序列1,2,3，不存在输出序列3,1,2

7 例4： 设依次进入一个栈的元素序列为c，a，b，d， 则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b A）、D）可以， B）、C）不行。 讨论：有无通用的判别原则？ 有！若输入序列是 .,Pj.Pk.Pi .(Pj<Pk<Pi) ， 一定不存在这样的输出序列 .,Pi.Pj.Pk . 答： 即对于输入序列1，2，3，不存在输出序列3，1，2 计算机系2001年考研题

本节重点：顺序栈和链栈的基本操作 栈的抽象数据类型定义： 教材P44-45) ADT Stack{ 数据对象：D= 入栈、出栈、 数据关系： R-. 建栈初始化、 基本操作： 判断栈满或栈空、 读栈顶元素值等。 }ADT Stack

8 栈的抽象数据类型定义: (教材P44-45） ADT Stack{ 数据对象：D=. 数据关系：R=. 基本操作： . } ADT Stack 入栈、出栈、 建栈初始化、 判断栈满或栈空、 读栈顶元素值等

动态数组 顺序栈的存储表示（教材P46: #define STACK-INT-SIZE100X/存储空间初始分配量 #define STACKINCREMENT10X/存储空间分配增量 typedef struct{ SElemType *base; /栈的基址即栈底指针 SElemType *top; /栈顶指针 int stacksize;//当前分配的空间 }SqStack;

9 顺序栈的存储表示（教材P46)： #define STACK-INIT-SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 typedef struct{ SElemType *base; //栈的基址即栈底指针 SElemType *top; //栈顶指针 int stacksize; //当前分配的空间 } ; 动态数组

顺序栈的入栈操作—— 例如用堆栈存放(A,B,C,D) 高地址M B 低地址L top [A top A 核心语句： 顺序栈入栈函数PUSH() top=L, status Push (ElemType e) Push(A)方 {if(top>M){上溢} Push(B)方 else s[top++]=e; Push(C); Push(D房

10 顺序栈的入栈操作——例如用堆栈存放（A，B，C，D） A A C B A B A top 核心语句： top=L; 顺序栈入栈函数PUSH（） status Push(ElemType e) { if(top>M){上溢} else s[top++]=e; } Push (B); Push (C); Push (D); top top top top 低地址L Push (A); 高地址M B C D