数据结构第03章

第3章堆栈和队列主要知识点堆栈堆栈应用队列优先级队列11.

定义一、堆栈的基本概念是一种特殊的线性表，限定只能在表的一端进行插入和删除操作的线性表。特点：后进先出。栈顶和栈底：堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。3.1

堆栈2图3-1火车调度模型（a）车轨设置（b）驶入（c）驶出堆栈的功能和火车调度装置的功能类同，如图3-1所示：3堆栈的基本概念（续）与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。3.存储结构4.运算规则5.实现方式

2.逻辑结构基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等等。4栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶

/top;表头(即a1端)称为栈底/base例如：栈S=(a０,a2,a3,……….,an-1,an

)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a0称为栈底元素强调：插入和删除都只能在表的一端（栈顶）进行！注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。5例1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取

运算规则：后进先出(LIFO)“进”＝插入=压入“出”＝删除=弹出6例2一个栈的输入序列为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种可能性。7例3一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？解：

43512不可能实现，主要是其中的12顺序不能实现；

12345的输出可以实现，每压入一数便立即弹出即可。8二、堆栈抽象数据类型数据集合：{a0,a1,…,an-1｝

ai的数据类型为DataType操作集合：(1)StackInitiate(S)初始化堆栈S(2)StackNotEmpty(S)堆栈S非空否

(3)StackPush(S,x)入栈(4)StackPop(S,d)出栈(5)StackTop(S,d)取栈顶数据元素

9三、堆栈的顺序表示和实现1、顺序（堆）栈顺序存储结构的堆栈。2、顺序栈的存储结构

它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示当前栈顶位置。a0a1……an-1顺序栈S

ai……栈底栈顶top10存储结构示意图如下图所示：

其中：stack：为顺序堆栈存放数据元素的数组；MaxStackSize：为stack的最大存储单元个数；top：为堆栈的当前栈顶位置。用C语言定义为：typedef

struct{DataTypestack[MaxStackSize];

inttop;}SeqStack;…a4a3a2a1a001234Top=5栈顶栈底Stack

MaxStackSize-111a0a1……an-1顺序栈S

ai……问：顺序表和顺序栈的操作有何区别？表头表尾低地址高地址写入：S[i]=ai读出：e=S[i]压入(PUSH):S[top++]=an弹出(POP):e=S[--top]低地址高地址S[i]a0a1

aian-1

……顺序表S

……

an以线性表S=(a0,a1,….,an-2,an-1)为例栈底base栈顶top前提：一定要预设栈顶指针top栈顶top12栈为空的条件：top=0;栈满的条件：top=MaxStackSize;a0a1……an-1顺序栈S

ai……低地址高地址an栈底base栈顶top入栈口诀：堆栈指针top“先压后加”:S[top++]=an出栈口诀：堆栈指针top“先减后弹”:e=S[--top]13问：为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。下面用例子来帮助理解堆栈：14voidtest(int*sum){intx;scanf(“%d”,&x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}断点地址入栈例1

阅读下列递归过程，说明其功能。输入x1≠0输入x5＝0输入x2输入x3输入x4输出sum＝0输出sum＝0+x4输出sum＝x4+x3输出sum＝x4+x3+x2输出sum＝x4+x3+x2+x1注意：最先输入的数据

x1

最后才被累加程序功能：对键盘输入数据求和，直到输入0结束153、顺序栈的操作实现(1)初始化栈voidStackInitiate(SeqStack*S) /*初始化顺序堆栈S*/{ S->top=0; /*定义初始栈顶下标值*/ }16(2)判栈非空否

int

StackNotEmpty(SeqStackS)/*判顺序堆栈S非空否，非空则返回1，否则返回0*/{

if(S.top<=0) return0; elsereturn1;}17(3)入栈int

StackPush(SeqStack*S,DataTypex)/*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0*/{ if(S->top>=MaxStackSize) {

printf("堆栈已满无法插入!\n"); return0; } else{ S->stack[S->top]=x; S->top++;return1;}}18(4)出栈int

StackPop(SeqStack*S,DataType*d)/*弹出顺序堆栈S的栈顶数据元素值到参数d，出栈成功则返回1，否则返回0*/{ if(S->top<=0) { printf("堆栈已空无数据元素出栈!\n"); return0; } else { S->top--;*d=S->stack[S->top]; return1; }}19(5)取栈顶数据元素int

StackTop(SeqStackS,DataType*d)/*取顺序堆栈S的当前栈顶数据元素值到参数d，成功则返回1，否则返回0*/{if(S.top<=0) { printf("堆栈已空!\n"); return0; } else{ *d=S.stack[S.top-1];return1; }}20例：用堆栈存放（A，B，C，D）AACBABAtop

顺序栈入栈函数的核心语句：S->stack[S->top]=x; S->top++;toptoptoptop低地址L高地址MBCD21例：从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD顺序栈出栈函数的核心语句：S->top--;*d=S->stack[S->top];注：DataType*d；

SeqStack*S；22测试主程序：任务：建立一个顺序堆栈，首先依次输入数据元素1,2,3,......,10，然后依次出栈堆栈中的数据元素并显示。假设该顺序堆栈的数据元素个数在最坏情况下不会超过100个。

#include<stdio.h>#defineMaxStackSize100 typedef

int

DataType; #include"SeqStack.h" voidmain(void){

SeqStack

myStack;

inti,x;23

StackInitiate(&myStack); for(i=0;i<10;i++)

StackPush(&myStack,i+1)

StackTop(myStack,&x)

printf("当前栈顶数据元素为：%d\n",x);

printf("依次出栈的数据元素序列如下：\n"); while(StackNotEmpty(myStack)) { StackPop(&myStack,&x);

printf("%d",x); } }输出结果如下：当前栈顶数据元素为：10依次出栈的数据元素序列如下：1098765432124四、堆栈的链式表示和实现1、链栈的存储结构

以头指针为栈顶，在头指针处插入或删除.栈顶栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈ha0a1an-2an-1nextdata链栈中每个结点由两个域构成：data域和next域，其定义为：typedef

struct

snode{DataTypedata;

structsnode*next;}LSNode;252、链式堆栈的操作实现 （1）初始化StackInitiate(head)voidStackInitiate(LSNode**head){ *head=(LSNode*)malloc(sizeof(LSNode)); (*head)->next=NULL;}（2）非空否StackNotEmpty(head)int

StackNotEmpty(LSNode*head){ if(head->next==NULL)return0; elsereturn1;}26(3)入栈voidStackPush(LSNode*head,DataTypex){LSNode*p; p=(LSNode*)malloc(sizeof(LSNode)))p->data=x;

p->next=head->next; /*新结点链入栈顶*/

head->next=p;

/*新结点成为新的栈顶*/}27(4)出栈int

StackPop(LSNode*head,DataType*d){ LSNode*p=head->next; if(p==NULL) { printf("堆栈已空出错！");

return0; }

head->next=p->next; /*删除原栈顶结点*/ *d=p->data; /*原栈顶结点元素赋予d*/ free(p); /*释放原栈顶结点内存空间*/

return1;}28（5）取栈顶数据元素StackTop(head,d)int

StackTop(LSNode*head,DataType*d){

LSNode*p=head->next; if(p==NULL) {

printf("堆栈已空出错！");

return0; }

*d=p->data; return1;}29（6）撤消动态申请空间Destroy(*head)voidDestroy(LSNode*head){

LSNode*p,*p1;

p=head; while(p!=NULL) { p1=p; p=p->next; free(p1); }}

30在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，可不设头结点链栈。一般不会出现栈满情况；除非没有空间导致malloc分配失败。链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。几点说明:311.括号匹配问题（书P55）

假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。

设计思路：用栈暂存左括号括号匹配有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号；（4）左右括号匹配正确。3.2堆栈应用32voidExpIsCorrect(charexp[],intn)//判断有n个字符的字符串exp左右括号是否配对正确{SeqStack

myStack;

inti; charc;

StackInitiate(&myStack);for(i=0;i<n;i++){if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))

StackPush(&myStack,exp[i]); elseif(exp[i]==')'&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c=='(')

StackPop(&myStack,&c); 33elseif(exp[i]==')'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='('){printf("左右括号配对次序不正确！\n"); return;}elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='[')

StackPop(&myStack,&c); elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='['){printf("左右括号配对次序不正确！\n");return; }34elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='{')

StackPop(&myStack,&c);

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='{'){printf("左右括号配对次序不正确！\n");return;}elseif(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}'))&&!StackNotEmpty(myStack)){printf("右括号多于左括号！\n");return;}}

//for语句结束35if(StackNotEmpty(myStack))

printf("左括号多于右括号！\n");else

printf("左右括号匹配正确！\n");}362.表达式计算问题表达式计算是编译系统中的基本问题，其实现方法是堆栈的一个典型应用。在编译系统中，要把便于人理解的表达式翻译成能正确求值的机器指令序列，通常需要先把表达式变换成机器便于理解的形式，这就要变换表达式的表示序列。假设计算机高级语言中的一个算术表达式为:A+(B-C/D)*E这种表达式称为中缀表达式，编译系统对其处理的方法是转成满足四则运算规则的相应的后缀表达式即为:ABCD/-E*+

其运算次序为：T1=CD/；T2=BT1-；

T3=T2E*；T4=AT3+。37后缀表达式的