数据结构概论 第3章 栈和队列 董黎刚 浙江工商大学信电学院 2019年2月25日.

Presentation on theme: "数据结构概论 第3章 栈和队列 董黎刚 浙江工商大学信电学院 2019年2月25日."— Presentation transcript:

1 数据结构概论 第3章 栈和队列 董黎刚 浙江工商大学信电学院 2019年2月25日

2 1. 栈的逻辑结构

3 3.1.1 背景 栈（stack）是一种逻辑结构，是一种特殊的线性表：操作（比如插入、删除、查找）只能在线性表的一头进行。换句话说，栈是操作受限的线性表。 生活中栈的例子，比如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上，相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。 3.1 栈的逻辑结构

4 3.1.2 定义 栈：只允许一端删除和插入的线性表。 通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
栈为后进先出（Last In First Out）的线性表，可称为LIFO表。 当表中没有元素时称为空栈。 3.1 栈的逻辑结构

5 3.1.3 操作 线性表 栈 初始化 InitList（L） InitStack(S) 销毁 DestroyList(L)
清空（置零，不销毁） ClearList(L) ClearStack(S) 判空 IsEmpty(S) 判满 IsFull(S) 求长度 ListLength（L） 一般无 求结点 GetNode（L，i） GetTop(S, x) 求位置 LocateNode（L，x） 插入 InsertList（L，x，i） Push(S,x) 删掉 DeleteList（L，i） Pop(S, x) 3.1 栈的逻辑结构

6 2. 栈的物理结构 ——链栈

7 3.2.1 背景 链栈的定义与一般单链表是一样的，只是链栈的操作只限于在链表头部（也就是栈的顶部）操作。 3.2 栈的物理结构——链栈

8 3.2.2 定义 typedef struct node { int data; //数据域
//定义两个类型：LinkStackNode和LinkStack typedef struct node { int data; //数据域 struct node *next; //指针域 }LinkStackNode, *LinkStack; LinkStack top; //等同于LinkStackNode* top; 链栈操作都在顶部，为操作方便通常不设头结点 3.2 栈的物理结构——链栈

9 3.2.3 操作的实现 初始化和清空栈是不同的，初始化是创建一个空栈，清空栈是逐个释放栈中各元素结点占用的空间。
LinkStackNode *InitStack() //初始化栈 { LinkStackNode *top =(LinkStackNode *)malloc(sizeof(LinkStackNode)); //创建头结点 top->next=NULL; return top; } ClearStack(LinkStack top) //清空栈 3.2 栈的物理结构——链栈

10 3.2.3 操作的实现 如何设计算法——以ClearStack(LinkStack S)为例 步骤一：先画图（用实例试探算法的思路）
步骤二：再设计算法（先考虑一次操作，再考虑循环） 步骤三：用实例验证 while(s->next != NULL) { p=s->next; s->next = p->next; free(p); } 3.2 栈的物理结构——链栈

11 3.2.3 操作的实现 判栈空和判栈满 int StackEmpty(LinkStackNode *top) //判断栈是否空 {
//如果top->next为0，说明栈是空的，则返回TRUE return top->next==NULL; } 链栈中的结点是动态分配的，只要有内存就不会发生上溢，无须定义判断栈满运算。 3.2 栈的物理结构——链栈

12 3.2.3 操作的实现 入栈和出栈 int Push(LinkStack top, ElemType x) {
申请新结点空间（如果失败则退出） 新结点中赋值x 新结点被压入栈中 修改栈顶指针 } int Pop(LinkStack top, ElemType *x) { 判断栈是否为空（如果为空则退出） 栈顶结点元素值赋给x所指的存储空间 修改栈顶指针 释放结点占用的空间 } 3.2 栈的物理结构——链栈

13 3. 栈的物理结构 ——顺序栈

14 3.3.1 背景 由于栈的特殊性，在实际应用中，通常用顺序表而不是用链表来存储栈。为什么？
因为栈只需要在一头插入和删除元素，因此不会产生插入和删除一个元素而要移动其他元素的麻烦。 3.3 栈的物理结构——顺序栈

15 3.3.2 定义 顺序栈动画 3.3 栈的物理结构——顺序栈

16 3.3.2 定义 typedef struct { ElemType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
int top; /*栈顶指针，用来存放栈顶元素的下标, top=-1表示空栈*/ }SeqStack; 与第二章中顺序表的定义有什么不同？ 3.3 栈的物理结构——顺序栈

17 3.3.3 操作的实现 链栈 顺序栈 InitStack()和 InitStack(S)
top =malloc(sizeof (LinkStackNode));//头结点 S->top= -1 ClearStack(S) IsEmpty(S) return (top->next==NULL); return (S->top==-1); IsFull(S) 一般无 return (S->top == Stack_Size-1); GetTop(S, x) *x=top->next->data; *x = S->elem[S->top]; Push(S,x) 分配空间，赋值，修改当前栈顶指针 判断是否满 S->elem[++S->top]=x; Pop(S, x) 判断是否空，保存值到x，修改当前栈顶指针 判断是否空 *x= S->elem[S->top--]; 3.3 栈的物理结构——顺序栈

18 4. 栈的物理结构 ——共享顺序栈

19 3.4.1 背景 为了节省空间，出现了共享（顺序）栈的设计。 3.4 栈的物理结构——共享顺序栈

20 3.4.2 定义 共享栈动画

21 3.4.2 定义 利用“栈底位置不变，栈顶位置动态变化”的特性。
为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。两栈共享比两个栈分别申请M/2的空间利用率高。比如，栈空间为100。 3.4 栈的物理结构——共享顺序栈

22 3.4.3 操作的实现 顺序栈 共享顺序栈 InitStack(S) S->top= -1 S->top[0]=-1;
S->top[1]=M; IsEmpty(S) return(S->top==-1); 类似左边，但是有top[0]和top[1] IsFull(S) return(S->top == Stack_Size-1); return (top[0]==top[1]-1) GetTop(S, x) *x = S->elem[S->top]; Push(S,x) 判断是否满 S->elem[++S->top]=x; Pop(S, x) 判断是否空 *x= S->elem[S->top--]; 3.4 栈的物理结构——共享顺序栈

23 5. 栈的应用

24 3.5.1 背景 栈的典型应用有 数制转换 括号匹配 表达式求解 行编辑 3.5 栈的应用

25 3.5.2 数制转换 比如，十进制转换成八进制：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1
按照输出顺序，结果为余数的逆序:102。 先求得的余数在输出结果时最后写出，最后求出的余数最先输出，符合栈的先入后出性质，故可用栈来实现数制转换。 3.5 栈的应用

26 3.5.3 括号匹配 表达式中包含多种括号，比如圆括号、方括号和花括号，括号只能就近匹配，而不能交叉。如([ { } ]([ ]))或({([ ] [() ]) })等均为正确的格式，而 { [ ] }) }或 { [() ] 或([ ] }均为不正确的格式。 好处：栈正好适合于括号匹配中的就近原则。 算法思路：设置一个栈，每读入一个括号，若是左括号，则直接入栈；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。 3.5 栈的应用

27 3.5.3 括号匹配 比如，输入(z[a]n}的栈变化情况如下所示： 3.5 栈的应用

28 3.5.4 表达式求解 表达式中不仅括号匹配符合就近原则，操作数运算也是就近匹配。 3.5 栈的应用

29 3.5.4 表达式求解 算法思路 设置两个栈：OPDS(操作数栈)和OPRS(操作符栈)。 ——操作数operand，操作符operator
当前操作符> OPRS栈顶, 当前操作符进OPRS栈 当前操作符≤ OPRS栈顶， OPDS栈顶、次顶和OPRS栈顶，退栈进行运算，运算结果进OPDS栈。 3.5 栈的应用

30 3.5.4 表达式求解 比如，A/B↑C+D*E#运算过程的栈变化情况如下所示： (其中↑表示乘方，#表示表达式的结束） 3.5 栈的应用

31 3.5.4 表达式求解 比如，A/B↑C+D*E#运算过程的栈变化情况如下所示： 3.5 栈的应用

32 3.5.4 表达式求解 比如，A/B↑C+D*E#运算过程的栈变化情况如下所示： 3.5 栈的应用

33 3.5.4 表达式求解 比如，A/B↑C+D*E#运算过程的栈变化情况如下所示： 3.5 栈的应用

34 3.5.4 表达式求解 比如，A/B↑C+D*E#运算过程的栈变化情况如下所示： 3.5 栈的应用

35 3.5.5 行编辑 一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入一个栈。允许用户输入出错时可以及时更正。
例：在终端上用户输入为 whli##ilr#e(s#*s) 应为 while(*s) 可以用栈来实现行编辑程序。 3.5 栈的应用

36 6. 递归和栈

37 3.6.1 背景 Hanoi塔/汉诺塔/河内塔问题 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 3.6 递归和栈

38 3.6.1 背景 Hanoi塔/汉诺塔/河内塔问题 假如移动一次要1秒, 计算表明移完这些金片需要5845亿年以上（搬动次数为2^64-1，约为16*10^18次），而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。 Hanoi塔问题能够用递归算法表达，假如用2.4GHz的CPU，每3个时钟周期计算一步，则需要2*10^10秒（2.4G/3是8*10^8），也就是634年。 3.6 递归和栈

39 3.6.2 递归的定义 递归算法就是直接或者间接地调用自己的算法。 递归的原理是把问题转化为规模缩小了的同类问题。 在递归时，需要
所谓间接调用，比如函数A调用函数B，函数B调用A。 递归的原理是把问题转化为规模缩小了的同类问题。 在递归时，需要 不断把本次调用的状态数据（当前局部变量值、当前函数形参值、返回地址）保存起来，进入更低一层的调用，直到问题不能分解且解决为止。 然后再逐个把保存的各次调用的状态数据按照“先进后出”取出来。 因此递归算法的求解也符合栈的特点。 3.6 递归和栈

40 3.6.2 写递归算法 全局可以分解成若干个局部，而局部和全局具有相似性 要定义好出口（即不再继续分解的情况）。
void hanoi(int n,char x,char y,char z) { if(n==1) move(x,1,z); // 将编号为1的圆盘从X移到Z else hanoi(n-1,x,z,y); // 将X上编号为1至n-1的圆盘移到Y move(x,n,z); // 将编号为n的圆盘从X移到Z hanoi(n-1,y,x,z); // 将Y上编号为1至n-1的圆盘移到Z } 3.6 递归和栈

41 3.6.3 理解递归算法 void hanoi(int n,char x,char y,char z) { if(n==1)
move(x,1,z); else hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } 3.6 递归和栈

42 3.6.3 理解递归算法 3.6 递归和栈

43 3.6.4 递归优缺点 用递归算法解决问题往往比较简单（算法可读性较好），但是递归算法两个缺点：
递归算法运行比较费时（因为执行时需要进行栈操作）。幸好现在计算机速度越来越快，这个缺点可以忍受。 递归算法运行中有深度调用（即多个嵌套调用），调试不方便，我们容易看错执行次序和调用层次。最好手工画出调用关系以辅助调试。 3.6 递归和栈

44 3.6.5 从递归到非递归 方法一：在简单情况下，将递归算法直接转换为循环实现。在思维上要把递归的从顶向下改成一般循环的自底向上。
方法二：基于栈的方法。用户自定义栈来代替递归中隐含的栈。 3.6 递归和栈

45 3.6.6 递归中栈的使用 递归实现中的栈操作动画（以斐波那契数列为例） 3.6 递归和栈

46 7. 队列的逻辑结构

47 3.7.1 背景 队列（Queue）是一种逻辑结构，是一种特殊的线性表：操作（比如插入、删除、查找）只能在线性表的两头进行。队列是操作受限的线性表。 在日常生活中队列的例子很多,如排队买东西,排头的买完后走掉,新来的排在队尾。为什么队列的例子比栈多？ 因为队列是一种符合公平性的机制 3.7 队列的逻辑结构

48 3.7.2 定义 队列：允许一端删除，另一端插入的线性表。 允许删除的一端称为队头（Front）。 允许插入的一端称为队尾（Rear）。
队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 3.7 队列的逻辑结构

49 3.7.3 操作 线性表 栈 队列 初始化 InitList（L） InitStack(S) InitQueue(Q) 销毁
DestroyList(L) DestroyQueue(Q) 清空 ClearList(L) ClearStack(S) ClearQueue(Q) 判空 IsEmpty(S) IsEmpty(Q) 判满 IsFull(S) 求长度 ListLength（L） 一般无 求结点 GetNode（L，i） GetTop(S, x) GetHead（Q,x） 求位置 LocateNode（L，x） 插入 InsertList（L，x，i） Push(S,x) EnterQueue(Q, x) 删掉 DeleteList（L，i） Pop(S, x) DeleteQueue(Q,x) 3.7 队列的逻辑结构

50 3.7.3 操作 线性表（Link） 栈（stack） 队列（queue） 对于头尾的称呼 线性表头（head） 线性表尾（tail）
栈顶（top） 栈底（bottom） 队头（front） 队尾（rear） 对于插入删除的称呼 插入（insert） 删除（delete） 入栈（push） 出栈（pop） 入队（enqueue） 出队（dequeue） 3.7 队列的逻辑结构

51 3.7.4 双端队列 双端队列(deque) 限定插入和删除操作在表的两端进行的线性表。 可以把栈和队列看成是双端队列的特例。
3.7 队列的逻辑结构

52 8. 队列的物理结构 ——链队列

53 3.8.1 背景 链队列的定义与一般单链表的区别是： 链队列有两个指针。（一般单链表只有一个头指针或者尾指针）
链队列的操作只限于在链表头部（可进行删除操作，称为出队）和尾部（可进行插入操作，称为入队）操作。（一般单链表可以在链表中间进行删除、插入操作） 3.8 队列的物理结构——链队列

54 3.8.2 定义 typedef struct Node { ElemType data; /*数据域*/
struct Node next; /*指针域*/ }LinkQueueNode; typedef struct LinkQueueNode *front; //队头指针 LinkQueueNode *rear; //队尾指针 }LinkQueue; 3.8 队列的物理结构——链队列

55 9. 队列的物理结构 ——循环（顺序）队列

56 3.9.1 背景 队列较多采用顺序存储结构，而不是链式存储结构，为什么？
这是因为队列只能在线性表两头插入和删除，这样的话，顺序表中间插入和删除比较麻烦的缺点就不存在了。 像一般顺序表一样，表头删除元素要移动后面的元素吗？ 3.9 队列的物理结构——循环（顺序）队列

57 3.9.2 顺序队列的定义 typedef struct { ElemType elem[MAXSIZE]; /* 队列的元素空间*/
int front; /*头指针*/ int rear; /*尾指针*/ }SeqQueue; 因为front和rear都是动态变化的，不能简单地用front或rear等于-1或0，来判断队列是否为空。 3.9 队列的物理结构——循环（顺序）队列

58 3.9.2 顺序队列的定义 顺序队列动画 3.9 队列的物理结构——循环（顺序）队列

59 3.9.3 假溢出 一般的顺序队列中会出现假溢出(如下图（4）的情况)：队列中有空间，但是却装不下（溢出）。
为此，我们一般采用循环（顺序）队列。 3.9 队列的物理结构——循环（顺序）队列

60 3.9.4 循环（顺序）队列 循环队列动画 3.9 队列的物理结构——循环（顺序）队列

61 3.9.4 循环（顺序）队列 方式一 判断队空的条件是front==rear 判断队满的条件是 (rear+1)%6==front
3.9 队列的物理结构——循环（顺序）队列

62 3.9.4 循环（顺序）队列 方式二 判断队空的条件是front==rear且元素个数为0
因为顺序队列的定义中一般没有“元素个数”这个变量，所以顺序队列通常采用方式一 3.9 队列的物理结构——循环（顺序）队列

63 3.9.5 操作的实现 链队列 循环顺序队列（方式一） InitQueue(Q)
Q->front=malloc(sizeof (LinkQueueNode)); Q->front=Q->rear=0; QueueEmpty(Q) return(Q->rear==Q->front); QueueFull(Q) 无 return((Q->rear+1)%MAXSIZE ==Q->front); QueueFront(S) return Q->front->next->data; return Q->elem[Q->front]; EnterQueue(Q,x) 分配空间，赋值，修改当前队尾指针 判断是否满 Q->elem[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE; DeleteQueue(S, x) 判断是否空，保存值到x，修改当前队头指针 判断是否空 *x= S->elem[S->front]; Q->front=(Q->front+1)%MAXSIZE; 3.9 队列的物理结构——循环（顺序）队列

64 10. 队列的应用

65 3.10.1 背景 杨辉三角的打印 特点：每一行的第一个元素和最后一个元素均为1，其他位置上的数字是其上一行中与之相邻的两个整数之和
3.10 队列的应用

66 3.10.2 算法思想 显示数据只能从上到下，从左到右逐个进行，不能回溯。
如果用队列存储数据，出队列的数据一边显示，一边与后面的数据相加产生下一行数据，并把产生的数据放入队列。 队列尾 队列头 1出队并打印 1+3=4 4入队 3.10 队列的应用

67 总结