第3章 栈和队列 3.1 栈 本章主题：栈和队列的应用 教学目的：掌握栈和队列的应用方法,理解栈的重要作用 第3章 栈和队列 本章主题：栈和队列的应用 教学目的：掌握栈和队列的应用方法,理解栈的重要作用 教学重点：利用栈实现行编辑,利用栈实现表达式求值 教学难点：利用栈实现表达式求值 3.1 栈 栈，也叫堆栈，是最常用也是最重要的数据结构之一。比如编译器中的语法识别、数学表达式的处理、程序运行中的函数及过程的调用等，都要用到栈的有关特性。它们是栈应用于实际问题的典型。 2019/1/12

3.1.1 栈的定义和运算 1．栈的定义 栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。 特点：后进先出 栈又称为“后进先出”的线性表，简称LIFO表。 2019/1/12

将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 2．栈的基本运算 初始化栈InitStack(S) 设置一个空栈S。 压栈Push(S,x) 将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 取栈顶元素GetTop(S,x) 若栈S不空，则由x返回栈顶元素。 判栈空Empty(S) 若栈S为空栈，结果为1，否则结果为0。 2019/1/12

栈有两种存储表示方法:顺序存储和链式存储 1.栈的顺序存储结构 3.1.2 栈的顺序存储结构及其基本运算的实现 栈有两种存储表示方法:顺序存储和链式存储 1.栈的顺序存储结构 栈的顺序存储结构简称为顺序栈。通常由一个一维数组和一个记录栈顶元素位置的变量组成。 2019/1/12

ElemType 为栈中元素的数据类型，可以根据需要而指定为某种具体的类型。 顺序栈的C语言描述如下： #define MaxSize <存储数据元素的最大个数> typedef struct { ElemType data[MaxSize]; int top; }STACK; ElemType 为栈中元素的数据类型，可以根据需要而指定为某种具体的类型。 data域:为一个一维数组，用于存储栈中元素。 top域:栈顶指针。取值范围为0～MaxSize-1。 top=-1表示栈空，top=MaxSize-1表示栈满。 2019/1/12

顺序栈的几种状态（最大长度MaxSize为4） 。 （a）当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值top=-1。 （b）表示在（a）基础上执行Push(S, ‘A’)后得到这种状态。 （c）又有三个元素B、C、D先后入栈，此时栈顶元素的下标值top=3。栈已满。 （d）表示在（c）状态下，执行一次Pop(S，x)运算得到。 （e）表示在（d）状态下，执行三次Pop(S，x)运算得到。此时栈顶下标值top=-l，又变成栈空状态 2019/1/12

2．基本运算在顺序存储结构的实现 初始化栈InitStack(S) 压栈Push(S,x) void InitStack(STACK *S) { S->top=-1; } 压栈Push(S,x) int Push(STACK *S,ElemType x) {if(S->top==MaxSize-1){ printf("\n Stack is full!"); return 0; } S->top++; S->data[S->top]=x; return 1; } 2019/1/12

出栈Pop(S,x) int Pop(STACK *S,ElemType *x) { if(Empty(S)){ printf("\n Stack is free!"); return 0; } *x=S->data[S->top]; S->top--; return 1; 2019/1/12

取栈顶元素GetTop(S,x) 判栈空Empty(S) int GetTop(STACK *S, ElemType *x) { if(Empty(S)){ printf("\n Stack is free!"); retrn 0; } *x=S->data[S->top]; return 判栈空Empty(S) int Empty(STACK *S) { return (S->top==-1?1:0);} 2019/1/12

两个栈共享大小为m的内存空间时，分配方法的示意图如下 3．栈的共享存储单元 两个栈共享大小为m的内存空间时，分配方法的示意图如下 两个栈的共享存储单元可用C语言描述如下： #define MaxSize <共享存储单元的最大长度> typedef struct{ ElemType data[MaxSize]; int top[2]; }STACK; 2019/1/12

（1）两个栈共享存储单元的压栈算法 int Push(STACK *S,ElemType x,int k) { if(S->top[0]+1==S->top[1]){ printf("\n stack is full!"); return 0; } if(k==0){ S->top[0]++; S->data[S->top[0]]=x;} else{ S->top[1]--; S->data[S->top[1]]=x; return 1; 2019/1/12

（2）两个栈共享存储单元的出栈算法 int Pop(STACK *S,int k,ElemType *x) { if((k==0)&&(S->top[0]==-1)){ printf("\n stack is free!"); return 0; } if((k==1)&&(S->top[1]==MaxSize)){ printf("\n stack is free!"); return 0; } if(k==0){ *x=S->data[S->top[0]];S->top[0]--; } else{ *x=S->data[S->top[1]];S->top[1]++; } return 1; 2019/1/12

栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈 3.1.3 栈的链式存储结构及其基本运算的实现 1.栈的链式存储结构 栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈 链栈结构示意图 链栈的C语言描述如下： typedef struct snode { //定义链栈结点类型 ElemType data; struct snode *next; }LinkSTACK; LinkSTACK *top; 2019/1/12

链栈的几种状态 : 2019/1/12

void InitStack(LinkSTACK **top) 2．基本运算在链式存储结构的实现 栈初始化 void InitStack(LinkSTACK **top) { *top=(LinkSTACK*)malloc(sizeof(LinkSTACK)); (*top)->next=NULL; } 2019/1/12

压栈运算 判断栈空 int Push(LinkSTACK **top,ElemType x) { LinkSTACK *s; s=(LinkSTACK *)malloc(sizeof(LinkSTACK)); s->data=x; s->next=(*top)->next; (*top)->next=s; return 1; } 判断栈空 int Empty(LinkSTACK **top) { return ((*top)->next==NULL?1:0);} 2019/1/12

出栈运算 int Pop(LinkSTACK **top,ElemType *x) { LinkSTACK *s; if(Empty(top)){ printf("\n stack is free!"); return 0; } s=(*top)->next; *x=s->data; (*top)->next=s->next; free(s); return 1; 2019/1/12

取栈顶元素 int GetTop(LinkSTACK **top,ElemType *x) { if(Empty(top)){ printf("\n stack is free!"); return 0; } *x=(*top)->next->data; return 1; 2019/1/12

3.2 栈的应用 “算符优先法” 的基本思想： （1）操作数栈置为空栈，表达式起始符“#”为运算符栈的栈底元素。 （2）从左到右扫描表达式，依次读入表达式中每个字符。若所读字符为“#”，且操作符的栈顶元素也为“#”时，则输出操作数栈中的栈顶数据，即为运算的结果，结束处理。否则，进行下面处理。 （3）若为操作数，入操作数栈；若为操作符，则要将当前操作符和操作符栈中的栈顶操作符进行优先级比较。 2019/1/12

① 如果当前操作符的优先级大于栈顶操作符的优先级，则将当前操作符压人操作符栈中；转第(2)步。 ② 如果当前操作符的优先级等于栈顶操作符的优先级，则将当前操作符栈顶的操作符出栈。转第(2)步。 ③ 如果当前操作符的优先级小于栈顶操作符的优先级，将当前操作符栈顶的操作符出栈。并从操作数栈中顺次出栈两个操作数（先退出作为运算符的右操作数，后退出作为运算符的左操作数）。用刚出栈的操作符对两个操作数进行计算求值，将所得值压入操作数栈中。转第(3)步。 2019/1/12

下图展示了算术表达式3×（7-2）求值的动态过程 2019/1/12

(25+x) ×(a×(a+b)+b) 25 x+a a b+×b+× 中缀表达式转换为等价的后缀表达式 中缀表达式 等价后缀表达式 0.3／(5×2+1) 0.3 5 2×1+/ 16-9×(4+3) 16 9 4 3+×- 2×(x+y)/(1-x) 2 x y +×1 x-/ (25+x) ×(a×(a+b)+b) 25 x+a a b+×b+× 2019/1/12

3.3 栈与递归 递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多问题的算法设计。在计算机内部，通过栈来实现递归算法。所以递归是栈的一个实际应用。 2019/1/12

采用递归算法求解正整数n的阶乘n! 数学定义 求n的阶乘的递归函数算法如下: long fact(int n) { long f; if(n==0) f=1; else f=n*fact(n-1); return f; } 2019/1/12

进行fact(4)调用的系统栈的变化情况 2019/1/12

函数fact(4)的递归调用过程的执行流程 2019/1/12

3.4 队列 3.4.1 队列的定义和运算 1．队列的定义 队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。 特点：队列中数据元素的入队和出队过程是按照“先进先出” 的原则进行的。因此，队列又称为“先进先出”的线性表，简称FIFO表。 2019/1/12

队列SQ是否为空。若为空返回1，否则返回0。 2．队列的基本运算 队列初始化InitQueue(SQ) 设置一个空队列SQ。 入队列EnQueue(SQ，x) 将x插入到队列SQ的队尾。 出队OutQueue(SQ，x) 将队头元素赋给x，并删除队头元素。 取队头元素GetHead(SQ，x) 由x返回队头结点的值。 判队列空Empty (SQ) 队列SQ是否为空。若为空返回1，否则返回0。 2019/1/12

队列有两种存储表示方法:顺序存储和链式存储 1．队列的顺序存储结构 队列的顺序存储结构简称顺序队。 3.4.2 队列的顺序存储结构及其基本运算的实现 队列有两种存储表示方法:顺序存储和链式存储 1．队列的顺序存储结构 队列的顺序存储结构简称顺序队。 顺序队是用一维数组依次存放队列中的元素和分别指示队列的首端和队列的尾端的两个变量组成。这两个变量分别称为“队头指针”和“队尾指针”。 顺序队列的数据类型定义如下 #define MaxSize < 队列的最大容量> typedef struct{ ElemType data[MaxSize]; int front,rear; }SQUEUE; 2019/1/12

顺序队列（ MaxSize=5 ）的几种状态 （a）表示空队列， rear=front=0。 （b）元素A入队后， rear=1，front=0。 （c）B，C依次入队后， rear=3，front=0。 （d）A，B，C依此出队后, rear=front=3。 （e）D入队后,rear=4, front=3。 （f）D出队后，rear=front=4。 2019/1/12

（a）表示空队列， rear= front=0。 （b）元素A入队后， rear=1， front=0。 如图所示是具有五个存储单元的循环队列 （a）表示空队列， rear= front=0。 （b）元素A入队后， rear=1， front=0。 （c）B，C，D依次入队后， rear=4， front=0。 （d）A出队后, front=1 ,rear=4。 （e）B，C，D出队后, rear= front=4。 2019/1/12

2．基本运算顺序队列的实现 队列初始化 入队列 void InitQueue(SQUEUE *SQ) { SQ->rear=SQ->front=0;} 入队列 int EnQueue(SQUEUE *SQ,ElemType x) { if((SQ->rear+1)%MaxSize==SQ->front){ printf("\n Queue is full!"); return 0;} SQ->rear=(SQ->rear+1)%MaxSize; SQ->data[SQ->rear]=x; return 1;} 2019/1/12

出队 判队列空 int OutQueue(SQUEUE *SQ,ElemType *x) { if(Empty(SQ)){ printf("\n Queue is free"); return 0; } SQ->front=(SQ->front+1)%MaxSize; *x=SQ->data[SQ->front]; return 1; 判队列空 int Empty(SQUEUE *SQ) { return(SQ->rear==SQ->front)?1:0;} 2019/1/12

队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。 3.4.3队列的链式存储结构及其基本运算的实现 1. 队列的链式存储结构 队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。 链队结构示意图 2019/1/12

链队的数据类型定义如下 ： typedef struct qnode{ //链队结点的类型 ElemType data; struct qnode *next; }QTYPE; typedef struct qptr{ //链队指针类型 QTYPE *front,*rear; }SQUEUE; SQUEUE LQ; 2019/1/12

链队运算指针变化情况 2019/1/12

2．基本运算链队的实现 队列初始化 void InitQueue(SQUEUE *LQ) { QTYPE *p; p=(QTYPE *)malloc(sizeof(QTYPE)); p->next=NULL; LQ->front= LQ->rear=p; } 2019/1/12

入队列 判队空 int EnQueue(SQUEUE *LQ,ElemType x) { QTYPE *s; s=(QTYPE *)malloc(sizeof(QTYPE)); s->data=x; s->next=LQ->rear->next; LQ->rear->next=s; LQ->rear=s; return 1; } 判队空 int Empty(SQUEUE *LQ) { return(LQ->front==LQ->rear?1:0);} 2019/1/12

出队列 int OutQueue(SQUEUE *LQ,ElemType *x) { QTYPE *p; if(Empty(LQ)){ printf("\n Queue is free!"); return 0;} p=LQ->front->next; *x=p->data; LQ->front->next=p->next; if(LQ->front->next==NULL) LQ->rear=LQ->front; free(p); return 1; } 2019/1/12

int GetHead(SQUEUE *LQ,ElemType *x) { if(Empty(LQ)){ 取队头元素 int GetHead(SQUEUE *LQ,ElemType *x) { if(Empty(LQ)){ printf("\n Queue is free!"); return 0; } *x=LQ->front->next->data; return 1; 2019/1/12