1、Chapter 3:栈、队列第三章 栈和队列3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值3.1 栈3.1.1栈的逻辑结构栈的逻辑结构 限定仅在表的一端进行插入与删除的线性表。也称作FILO-先进后出（First In Last Out）的线性表。ADT Stack 数据对象:D=ai|ai(-ElemSet,i=1,2,.,n,n=0 数据关系:R1=|ai-1,ai(-D,i=2,.,n 基本操作:InitStack(&S)构
2、造一个空栈S DestroyStack(&S)栈S存在则栈S被销毁 ClearStack(&S)栈S存在则清为空栈栈的抽象数据类型定义：StackEmpty(S)栈S存在则返回TRUE,否则FALSE StackLength(S)栈S存在则返回S的元素个数,即栈的长度 GetTop(S,&e)栈S存在且非空则返回S的栈顶元素 Push(&S,e)栈S存在则插入元素e为新的栈顶元素 Pop(&S,&e)栈S存在且非空则删除S的栈顶元素并用e返回其值 StackTraverse(S,visit()栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作
3、失败 ADT Stack栈的实例1-火车扳道站火车扳道站栈事例2-中断处理 中断1打断过程0，中断2打断中断1，中断3打断中断2 0过程0开始中断处理过程1中断处理过程2中断处理过程3断点1断点2断点33.1.2栈的顺序实现用一组连续的存贮空间存放栈元素 a1 a2 a n-1 a n栈顶 栈底顺序栈的类C语言定义 typedef struct SElemType*base;SElemType*top;/设栈顶栈底两指针的目的是便于判断栈是否为空 int StackSize;/栈的当前可使用的最大容量.SqStack;二、基本操作实现 栈初始化 Status InitStack(SqStack
4、&S)S.base=(SelemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INI_SIZE;return OK;/IniStack 栈清空 Status ClearStack(SqStack&S);S.top=S.base;/ClearStack 判断栈空 Status StackEmpty(SqStack S);if(S.top=S.base)return TRUE;else return FALSE;/StackEmpty 取栈
5、顶元素 Status GetTop(SqStack S,SElemType&e);if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;/GetTop 进栈 Status Push(SqStack&S,SElemType e);if(S.top-s.base=S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.s
6、tacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push 出栈 Status Pop(SqStack&S,SElemType&e);if(S.top=S.base)return ERROR;e=*-S.top;return OK;/Pop 顺序栈 “上溢”和“下溢”三、多栈共享存贮空间 若系统中使用若系统中使用n个栈，个栈，每个栈的最大尺寸每个栈的最大尺寸ni(i=1,2,n)，则则n个栈要预分配的总存贮容量为个栈要预分配的总存贮容量为 如果已知这如果已知这n个栈在任何时刻的总的存贮占用量均不会超过个栈在任何时刻的总的存贮占用量均不会超过N，且有且有
7、N 则可考虑令这则可考虑令这n个栈共享一块大小为个栈共享一块大小为N的存贮区，以节省存的存贮区，以节省存贮空间贮空间。niin1niin12栈共享存贮空间栈1栈2栈1底栈2底栈1顶栈2顶 对于两栈共享存贮空间，可以特殊处理，以避免移动元素。对于两栈共享存贮空间，可以特殊处理，以避免移动元素。方法是将两栈的栈底分别固定在存贮区的两底，两栈指针相向方法是将两栈的栈底分别固定在存贮区的两底，两栈指针相向增长增长3.1.3 栈的链式存贮结构PHead栈顶栈底Null链式栈的结点描述 Typedef struct Lnode ElemType data;struct Lnode*next;Lnode,*
8、LinkList;LinkLista1a2a3a4STop of stack =Front of Linked-list链式栈的基本操作void push(o)/insert o o.next=s.next;s.next=o void pop()/remove most recent item if s=Null printf(“pop fails-empty stack else a=s.data;s=s.next void top()/retrieve most recent item if s=null printf(“top fails-empty stack)else return
9、s.data;上溢问题3.2 栈应用之一：数制转换 将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1 结果为余数的逆序:102。void conversion()pSqStack S;SElemType e;int n;InitStack(&S);printf(Input a number to convert to OCT:n);scanf(%d,&n);if(n=0 数据关系:R1=|ai-1,ai(-D,i=2,.,n 基本操作：InitQueue(&Q)构造一个空队列Q Des
10、troyqueue(&Q)队列Q存在则销毁Q ClearQueue(&Q)队列Q存在则将Q清为空队列 QueueEmpty(Q)队列Q存在,若Q为空队列则返回TRUE,否则返回FALSE QueueLenght(Q)队列Q存在,返回Q的元素个数,即队列的长度 GetHead(Q,&e)Q为非空队列,用e返回Q的队头元素 EnQueue(&Q,e)队列Q存在,插入元素e为Q的队尾元素 DeQueue(&Q,&e)Q为非空队列,删除Q的队头元素,并用e返回其值 QueueTraverse(Q,vivsit()Q存在且非空,从队头到队尾,依次对Q的每个数据元素调用函数visit()。一旦visit(
11、)失败，则操作失败 ADT Queue二、链队列队列的链式表示和实现 用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。LinkedListItra1a2a3a4Q.frontFront of queueQ.rearBack of queue链队列表示和实现/存储表示 typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue&
12、Q)/构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;Status Destroyqueue(LinkQueue&Q)/队列Q存在则销毁Q while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;Status EnQueue(LinkQueue&Q,QElemType e)/队列Q存在,插入元素e为Q的队尾元素 p=(QueuePtr)
13、malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;Status DeQueue(LinkQueue&Q,QElemType&e)/Q为非空队列,删除Q的队头元素,并用e返回其值 if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;3.4.3队列的连续存贮结构一、非循环队
14、列 FrontrearcbaFront rear c b front rear front rear（c)a出队 (d)b,c出队，队为空实现 初始化:front=rear=0;进队：rear+;roomrear=x;出队:front+;x=roomfront;回送队头元素 队空：roomrear=roomfront;队满：rear=QueueSize-1;“伪满”。进队与出队操作结果的示意图空队（初态）a1、a2、a3相继进队后a1、a2相继出队a4进队a3、a4相继出队a5、a6相继进队（队已“满”）显然，若队空间为显然，若队空间为N个元素，则进行个元素，则进行N次进队操作后就会出现队满现
15、象，而不论这中次进队操作后就会出现队满现象，而不论这中间是否进行过出队操作，即出队操作所腾出的空位不能重复利用。这是一个十分严重的间是否进行过出队操作，即出队操作所腾出的空位不能重复利用。这是一个十分严重的问题，若不解决，无论分配多大的空间，也不能保证不发生溢出。所以，这种队列无实问题，若不解决，无论分配多大的空间，也不能保证不发生溢出。所以，这种队列无实用价值。用价值。解决这问题的方法是在发生假满时，移动队中元素，在尾部让出空位。但这解决这问题的方法是在发生假满时，移动队中元素，在尾部让出空位。但这种方法效率差，一种更好的方法是使用循环结构种方法效率差，一种更好的方法是使用循环结构这就是所谓
16、循环队列法。这就是所谓循环队列法。Array implementation,1st trialABCD?Erear=5entryfront=1ABCDE?DFErear=6entryfront=4DEFGWe cannot enqueue G because the rear has reached the end of the array.deQ A,B,C,then enQ F and G.Circular Array?EFD?124563?DFErear=6 1entryfront=4142563GentryIf we view the array as a circle,the cel
17、l after the 6th cell is the 1st cell.To implement queue,it is best to view arrays as circular structure.frontrearABCDEFG01789234560178923456ABCDEFGfrontrearCircular view of arrays.rearfrontcderear frontNeed to distinguish between full and empty cases:Empty case:rear=frontFull Case:(rear+1)MOD QueueS
18、ize=front Deliberate of one gap.Why?)cderearfrontReason:fpossible confusion withthe empty case.进队：(rear+)MOD QueueSize；/按模加roomrear=x;出队：(front+)MOD QueueSize；x=roomfront;/解决伪满循环队列#define MaxQsize 100 Typedef struct QElemType*base;int front;int rear;SqQueue;Status InitQueue(SqQueue&Q)Q.base=(ElemTyp
19、e*)malloc(MaxQsize*sizeof(ElemType);if(!Q.base)exit(Overflow);Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue&Q,QElemType e)if(Q.rear+1)%MaxQsize=Q.front)reture Error;/队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MaxQsize;reture OK;Status DeQueue(SqQueue&Q,QElemType&e)if(Q.front=Q.rear)return Error;/队列空 e=Q.baseQ.front;Q.front=(Q.front+1)%MaxQsize;return OK;
