第3章-栈和队列数据结构

第三章栈和队列两种特殊的线性表回顾线性表 顺序存储的线性表 链表表示的线性表特点：插入和删除操作可以在表的任何位置进行。A123n12nL问题栈（LIFO）——LastInFirstOut队列（FIFO）——FirstInFirstOut问：对这些数据的操作与线性表有哪些相同和不同？答：都是线性结构的数据操作方式的差异134N2入口出口LIFO134N2出口入口FIFO3.1栈本节的主要内容：

1.栈的定义

2.堆栈的表示和实现

3.堆栈的操作方式

4.顺序栈和链栈的定义及其操作1.栈的抽象数据类型定义火车站的调度情况

一个有终结点火车道，每节车厢进出该车道的规则应该是怎样的呢？必须遵循LIFO

原则123进栈出栈栈：一个只能在栈顶进行插入和删除的线性表，其特征为LIFO

空栈：不含元素的空表

遵循LIFO(lastinfirstout)的线性表。 思考：按此规则，如果进栈的车厢序列为1，2，3，而且两侧铁道均为单向行驶道，那么它们出栈的顺序会有几种，分别是怎样排列的?抽象数据类型：

ADTStack{数据对象，数据关系同线性表

基本操作：

InitStack(&S),DestroyStock(&S),

ClearStack(&S),StackEmpty(S),

StackLength(&S),GetTop(S),Push(&S,e),Pop(&S,&e),

StackTraverse(S,visit())}

栈的表示和实现栈的表示：（1）顺序栈：栈的顺序存储

优点：处理方便；缺点：数组大小固定，易造成内存资源的浪费。（2）链栈：栈的动态存储

优点:能动态改变链表的长度，有效利用内存资源；缺点：处理较为复杂。问：TOP的作用是什么？顺序栈的表示和实现顺序表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedef

struct{

SElemType*base;

SElemType*top;

int

stacksize;}SqStack;

其中stacksize表示栈当前可以使用的最大容量。base为栈底，top为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）顺序栈的结构top指向压栈时下一个元素将要存放的位置。top减一指向弹栈时下一个元素的取值位置。栈空的条件：top=base栈满的条件：top-base>=stacksizetoptopbase空栈base非空非满栈topABCABCbase满栈DE基本操作的实现：初始化栈StatusInitStack(SqStack&S){//构造一个空栈

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack压栈:StatusPush(SqStack&S,SElemTypee){//元素e插入到栈中，成为新的栈顶

if(S.top-S.base>=S.stacksize)//栈满

{newbase=(SElemType*)realloc

(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!newbase)exit(OVERFLOW);elseS.base=newbase;S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;}//if*S.top++=e;returnOK;}//Push出栈:StatusPop(SqStack&S,SElemType&e){//从栈顶读取数据放入e内，栈中下一元素所在位置成为新的栈顶

if（S.top==S.base）returnERROR;//栈空

e=*--S.top;returnOK;}//Pop注意top的操作顺序和值的变化。压栈：valuetop;top++;

弹栈：top--;top->value;链栈的结构和表示定义栈结构Typedef

structstack_node{

Elemtypedata;

structstack_node*next;}LinkStack;LinkStack*stk;问：在这里为什么没有用到top指针？这样对栈结构的定义有否影响？1^728stk栈顶栈底链栈的操作入栈PUSH()StatusPUSH(LinkStack*stk,Elemtypex){

LinkStack*top; top=malloc(sizeof(LinkStack)); top->data=x; top->next=*stk; *stk=top;}问：在这里top指针的作用是什么？1^8stkxtop1^8stkxtop课堂练习：链栈的出栈操作取栈顶元素GETTOP()

3.2栈的应用举例1.数制转换10--〉2，逐步除二，得余取反序用算法实现求任意非负十进制数的八进制数 分析：每次除8，余数压栈，结束后依次出栈即可

voidconversion(){//非负十进制数转化为八进制数

InitStack(S);

scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while（！StackEmpty(s)）{pop(s,e);printf(“%d”,e);}}//conversion2.括号匹配算法{}[]（）的配对问题。

[(5+(2-6)+10)+6]*2（正确）

[(5+(2-6)+10]+6)*2（╳）

((5+2-6)+10)+6)*2（╳）判断的标准：

方法：见到左括号压栈，见到右括号弹栈，并和弹出的数据配对。编写算法：假设表达式结束符为#,试写出判断表达式是否正确的算法intMatchJudge(){//匹配返回1，不匹配返回0

InitStack(S);

scanf(“%c”,ch);while(ch!=“#”){if(ch==“(”||ch==“[”||ch==“{”)push(s,ch);if(ch==“)”||ch==“]”||ch==“}”）{ifStackEmpty(S)return0; pop(s,e);if(e与ch不匹配)return0;}

scanf(“%c”,ch);}//whileifStackEmpty(s)return1elsereturn0;}//MatchJudge算法：先乘除，后加减，括号先。（从左到右）算符优先算法：利用运算优先关系的规定来实现对表达式的编译或解释执行。（算符优先关系参看P53）比较两个表达式的计算过程：4＋2×15－10/5和4＋2×(15－10)/5分析：如何利用栈实现计算过程？设置两个工作栈：OPTR(运算符栈)和OPND(操作数栈)

OPND初始为空，OPTR栈底置“＃” 依次读入表达式中的字符： 操作数压OPND栈； 运算符：与OPTR栈顶元素比较优先级表达式求值问题OperandType

EvaluateExpression(){//算符优先算法求表达式的值

InitStack(OPTR);Push(OPTR,‘＃’)；//OPTR运算符栈

InitStack(OPND);c=getchar();//OPND操作数栈

while(c!=‘#’||GetTop(OPTR)!=‘#’){ if(!In(c,OP)){Push(OPND,c);c=getchar()}//操作数入栈OPND elseswitch(Precede(GetTop(OPTR),c)){ case’<’://栈顶运算符优先级低

Push(OPTR,c)；c=getchar();break; case’=’://去括号

Pop(OPTR,x);c=getchar();break; case’>’: //退栈并计算结果入栈 Pop(OPTR,theta); Pop(OPND,a);Pop(OPND,b); Push(OPND,Operate(a,theta,b));break; }//switch }//while returnGetTop(OPND);}//EvaluateExpression

表达式的前缀、中缀、后缀表示问题：对a+b的表示有：前缀+ab、中缀a+b、后缀ab+；各种表示方式对如a+b*c运算的优先次序的表示： 前缀+a*bc,中缀a+b*c,后缀abc*+编译中，需要将表达式化成前缀、后缀方式 例如#a+(b+(c/d-e))*f#转化为后缀的表示方法结果：abcd/e-+f*+课堂练习：写出a+(b+(c/d-e))*f的前缀、中缀、后缀表示。栈在递归调用中的作用递归函数：直接或间接调用自身的函数。递归的应用：递归定义的数学函数数据结构：二叉树、广义表，结构本生的递归性质用递归解决更简单的问题，如Hanoi塔问题。递归调用是一种显式的自嵌套调用，将大规模数据问题转化为小规模数据问题，调用时遵循“后调用先返回”的原则。系统在递归的实现上实际使用了栈为潜在的工具。3.3栈与递归的实现例：汉诺塔问题有XYZ三塔座，X上插有n个直径不同、由小到大的圆盘。要求借助Y将其全部移到Z上，按照原来的顺序叠放。移动规则：每次移动一个；任何时刻都是小盘在上，大盘在下。分析：当n=1时，直接移动即可；当n>=2时，首先将上面的n-1个圆盘移至Y，第n个放到Z；然后的问题就是n-1个圆盘的问题提示：虽然n-1个圆盘的问题与n个圆盘的问题相同，但规模变小。XYZ算法：voidhanoi(intn,charx,chary,charz){ 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.4

队列

队列：一个只能在队首进行删除、队尾进行插入的线性表，其特征为FIFO(先进先出)。关键基本操作：出队和入队

抽象数据类型：

ADTStack{数据对象，数据关系同线性表

基本操作：

InitQueue(&Q),DestroyQueue(&Q),

ClearQueue(&Q),QueueEmpty(Q),

QueueLength(&S),GetHead(S),

EnQueue(&Q,e),DeQueue(&S,&e),

QueueTraverse(Q,visit())}队列的表示和实现链式队列

typedef

struct

Qnode{

QElemTypedata;

struct

Qnode*next;}Qnode,*QueuePtr;

typedef

struct{

QueuePtrfront;

QueuePtrrear;}LinkQueue;课堂练习：链队列的操作入对列、出队列Q.frontQ.rear^链队列结构入队列：在队尾插入P=LinkQueue

malloc(sizeof(Qnode))P->next=NULL;Q.rear->next=p;Q.rear=P;出队列：在队头删除

r=Q.front->next; Q.front->next=r->next; free(r);Q.frontQ.rear^P顺序队列

#defineMAXQSIZE100

typedef

struct{

QElemType*base;

intfront;

intrear;}SqQueue;

其中base为连续空间首地址，front为队首，rear为队尾。为什么用循环队列来实现顺序队列？rearfront空队front非空非满队1rearABCC满队DECfront非空非满队2Drearrearfront顺序队列的结构——循环队列：空队：初始化队列时，两个指针rear＝front＝0入队：队尾插入元素，尾指针rear后移出队：队头删除元素，头指针