第3章栈和队列3.1栈栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。3.1.1栈的定义栈的儿种基本运算如下（1）初始化栈InitStack(&s)：构造一个空栈s。(2）销毁栈ClearStack(&s)：释放栈s占用的存储空间。(3）求栈的长度StackLength(s)：返回栈s中的元素个数。(4）判断栈是否为空StackEmpty(s)：若栈s为空，则返回真：否则返回假。3.1.2栈的顺序存储结构及其基本运算实现假设栈的元素个数最大不超过正整数MaxSize.所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:typedefstructElemType data[MaxSize];/*栈指针*/inttop;SqStack:在顺序栈中实现栈的基本运算算法（1）初始化栈initStack(&s)建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下：void InitStack(SqStack *&s)1s-(SqStack *)malloc(sizeof(SqStack));s->top=-1;(2)销毁栈ClearStack(&s)释放栈s占用的存储空间。对应算法如下：voidClearStack(SqStack*&s)tfree(s);1(3）求栈的长度StackLength(s)返回栈s中的元素个数.即栈指针加1的结果。对应算法如下：int StackLength(SqStack *s)return(s->top+1);3（4）判断栈是否为空StackEmpty(s)栈S为空的条件是s->top==-1。对应算法如下：int StackEmpty(SqStack *s)24
24 第 3 章 栈和队列 3.1 栈 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称 为栈顶。 栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。 表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。 3.1.1 栈的定义 栈的几种基本运算如下: (1) 初始化栈 InitStack(&s):构造一个空栈 s。 (2) 销毁栈 ClearStack(&s):释放栈 s 占用的存储空间。 (3) 求栈的长度 StackLength(s):返回栈 s 中的元素个数。 (4) 判断栈是否为空 StackEmpty(s):若栈 s 为空,则返回真；否则返回假。 3.1.2 栈的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数 MaxSize, 所有的元素都具有同一数据类型 ElemType,则可用下列方式来定义栈类型 SqStack: typedef struct { ElemType data[MaxSize]； int top； /*栈指针*/ } SqStack； 在顺序栈中实现栈的基本运算算法: (1) 初始化栈 initStack(&s) 建立一个新的空栈 s,实际上是将栈顶指针指向-1 即可。对应算法如下: void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } (2) 销毁栈 ClearStack(&s) 释放栈 s 占用的存储空间。对应算法如下: void ClearStack(SqStack *&s) { free(s); } (3) 求栈的长度 StackLength(s) 返回栈 s 中的元素个数,即栈指针加 1 的结果。对应算法如下: int StackLength(SqStack *s) { return(s->top+1); } (4) 判断栈是否为空 StackEmpty(s) 栈 S 为空的条件是 s->top==-1。对应算法如下: int StackEmpty(SqStack *s)
return(s->top==-1))(5)进栈Push(&s,e)在栈不满的条件下，先将栈指针增1,然后在该位置上插入元素e。对应算法如下：intPush(SqStack*&s,ElemTypee)if(s->top=-MaxSize-1) return 0;/*栈满的情况，即栈上溢出*/s->top++;s->data[s->top]=e;return l;(6)出栈Pop(&s,&e)在栈不为空的条件下，先将栈顶元素赋给e.然后将栈指针减1。对应算法如下intPop(SqStack*&s,ElemType&e)if(s->top=--1) return 0;/*栈为空的情况，即栈下溢出*e=s->data[s->top];s->top--;return l;(7）取栈顶元素GetTop(s)在栈不为空的条件下，将栈顶元素赋给e。对应算法如下：intGetTop(SqStack*s,ElemType&e)fif(s->top=--1)returnO:/*栈为空的情况，即栈下溢出*/e=s->data[s->top];return l;1(8）显示栈中元素DispStack(s)从栈顶到栈底顺序显示栈中所有元素。对应算法如下：voidDispStack(SqStack*s)tint i,for (i=s->top;i>=0,i--)printf("%c ",s->data[i]);printf("In");e3.1.3栈的链式存储结构及其基本运算的实现采用链式存储的栈称为链栈，这里采用单链表实现。链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的，下图是头结点为*Ihead的链栈，第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是al、a2、*、an。25
25 { return(s->top==-1); } (5) 进栈 Push(&s,e) 在栈不满的条件下,先将栈指针增 1,然后在该位置上插入元素 e。对应算法如下: int Push(SqStack *&s,ElemType e) { if (s->top==MaxSize-1) return 0; /*栈满的情况,即栈上溢出*/ s->top++; s->data[s->top]=e; return 1; } (6) 出栈 Pop(&s,&e) 在栈不为空的条件下,先将栈顶元素赋给 e,然后将栈指针减 1。对应算法如下: int Pop(SqStack *&s,ElemType &e) { if (s->top==-1) return 0; /*栈为空的情况,即栈下溢出*/ e=s->data[s->top]; s->top-; return 1; } (7) 取栈顶元素 GetTop(s) 在栈不为空的条件下,将栈顶元素赋给 e。对应算法如下: int GetTop(SqStack *s,ElemType &e) { if (s->top==-1) return 0; /*栈为空的情况,即栈下溢出*/ e=s->data[s->top]; return 1; } (8) 显示栈中元素 DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对应算法如下: void DispStack(SqStack *s) { int i; for (i=s->top;i>=0;i-) printf("%c ",s->data[i]); printf("\n"); } 3.1.3 栈的链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头 进行的,下图是头结点为*lhead 的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结 点。栈中元素自栈顶到栈底依次是 a1、a2、.、an
链栈中数据结点的类型LiStack定义如下：typedef struct linknode/*数据域*/ElemType data,，/*指针域*/struct linknode *next,LiStack,在链栈中，栈的基本运算算法如下：(1）初始化栈initStack(&s)建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。对应算法如下：voidInitStack(LiStack*&s)s=(LiStack *)malloc(sizeof(LiStack));s->next-NULL,1(2）销毁栈ClearStack(&s)释放栈s占用的全部存储空间。对应算法如下voidClearStack(LiStack*&s) LiStack *p=s->next,while (p!=NULL) free(s);s=p;p=p->next,33(3）求栈的长度StackLength(s)从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下：int StackLength(LiStack *s)int i=0;LiStack *p;p=s->next;while (p!=NULL)i++;p=p->next,?return(i),3(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s->next==NULL,即单链表中没有数据结点。对应算法如下int StackEmpty(LiStack *s)1return(s->next=--NULL);^s26
26 链栈中数据结点的类型 LiStack 定义如下: typedef struct linknode { ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ } LiStack; 在链栈中,栈的基本运算算法如下: (1) 初始化栈 initStack(&s) 建立一个空栈 s。实际上是创建链栈的头结点,并将其 next 域置为 NULL。对应算法 如下: void InitStack(LiStack *&s) { s=(LiStack *)malloc(sizeof(LiStack)); s->next=NULL; } (2) 销毁栈 ClearStack(&s) 释放栈 s 占用的全部存储空间。对应算法如下: void ClearStack(LiStack *&s) { LiStack *p=s->next; while (p!=NULL) { free(s); s=p; p=p->next; } } (3) 求栈的长度 StackLength(s) 从第一个数据结点开始扫描单链表,用 i 记录访问的数据结点个数,最后返回 i 值。对 应算法如下: int StackLength(LiStack *s) { int i=0; LiStack *p; p=s->next; while (p!=NULL) { i++;p=p->next; } return(i); } (4) 判断栈是否为空 StackEmpty(s) 栈 S 为空的条件是 s->next==NULL,即单链表中没有数据结点。对应算法如下: int StackEmpty(LiStack *s) { return(s->next==NULL); } ^ s
(5)进栈Push(&s,e)将新数据结点插入到头结点之后。对应算法如下：void Push(LiStack *&s,ElemType e)tLiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p->data=e;p->next=s->next/*插入*p结点作为第一个数据结点*/s->next=p,1(6)出栈Pop(&s,&e)在栈不为空的条件下，将头结点后继数据结点的数据域赋给e,然后将其删除。对应算法如下：intPop(LiStack*&s,ElemType&e)LiStack*p;if(s->next--NULL)return0；/*栈空的情况*//*p指向第一个数据结点*/p=s->next,e=p->data,s->next-p->next;free(p);return l;3(7）取栈顶元素GetTop(s)在栈不为空的条件下，将头结点后继数据结点的数据域赋给e。对应算法如下：intGetTop(LiStack*s,ElemType&e)/*栈空的情况*/if (s->next=--NULL) return 0,e=s->next->data,return l;（8）显示栈中元素DispStack(s)从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下：void DispStack(LiStack *s)LiStack *p=s->next,while (p!=NULL)printf("%c",p->data)p=p->next;printf("\n"),3.1.4栈的应用例子1.表达式求值2.求解迷宫问题27
27 (5) 进栈 Push(&s,e) 将新数据结点插入到头结点之后。对应算法如下: void Push(LiStack *&s,ElemType e) { LiStack *p; p=(LiStack *)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; /*插入*p 结点作为第一个数据结点*/ s->next=p; } (6) 出栈 Pop(&s,&e) 在栈不为空的条件下,将头结点后继数据结点的数据域赋给 e,然后将其删除。对应算 法如下: int Pop(LiStack *&s,ElemType &e) { LiStack *p; if (s->next==NULL) return 0; /*栈空的情况*/ p=s->next; /*p 指向第一个数据结点*/ e=p->data; s->next=p->next; free(p); return 1; } (7) 取栈顶元素 GetTop(s) 在栈不为空的条件下,将头结点后继数据结点的数据域赋给 e。对应算法如下: int GetTop(LiStack *s,ElemType &e) { if (s->next==NULL) return 0; /*栈空的情况*/ e=s->next->data; return 1; } (8) 显示栈中元素 DispStack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下: void DispStack(LiStack *s) { LiStack *p=s->next; while (p!=NULL) { printf("%c ",p->data); p=p->next; } printf("\n"); } 3.1.4 栈的应用例子 1. 表达式求值 2. 求解迷宫问题
求迷宫问题就是求出从入口到出口的路径。在求解时，通常用的是“穷举求解”的方法即从入口出发，顺某一方向向前试探若能走通，则继续往前走：否则沿原路退回，换一个方向再继续试探直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回（称为回溯），需要用一个后进先出的栈来保存从入口到当前位置的路径。3.2.1队列的定义3.2.2队列的顺序存储结构及其基本运算的实现在循环队列中，实现队列的基本运算算法如下(1）初始化队列InitQueue(&q)构造一个空队列q。将front和rear指针均设置成初始状态即0值。对应算法如下：void InitQueue(SqQueue *&q)q=(SqQueue *)malloc (sizeof(SqQueue);q->front=q->rear=0;1(2）销毁队列ClearQueue(&q)释放队列q占用的存储空间。对应算法如下：void ClearQueue(SqQueue *&q)1free(q);(3）判断队列是否为空QueueEmpty(q)若队列q满足q->front==q->rear条件,则返回1：否则返回0。对应算法如下：intQueueEmpty(SqQueue*g)1return(q->front-=q->rear);入队列enQueue(q,e)(4)在队列不满的条件下，先将队尾指针rear循环增1然后将元素添加到该位置。对应算法如下：intenQueue(SqQueue*&q,ElemTypee)1if(q->rear+1)%MaxSize==q->front)/*队满*/returnO,q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;return I;1(5）出队列deQueue(q,e)在队列q不为空的条件下,将队首指针front循环增1,并将该位置的元素值赋给e。对应算法如下：intdeQueue(SqQueue*&q,ElemType&e)1if(q->front==q->rear）/*队空*return O;28
28 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方 法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方 向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回 (称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 3.2.1 队列的定义 3.2.2 队列的顺序存储结构及其基本运算的实现 在循环队列中,实现队列的基本运算算法如下: (1) 初始化队列 InitQueue(&q) 构造一个空队列 q。将 front 和 rear 指针均设置成初始状态即 0 值。对应算法如下: void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0; } (2) 销毁队列 ClearQueue(&q) 释放队列 q 占用的存储空间。对应算法如下: void ClearQueue(SqQueue *&q) { free(q); } (3) 判断队列是否为空 QueueEmpty(q) 若队列 q 满足 q->front==q->rear 条件,则返回 1；否则返回 0。对应算法如下: int QueueEmpty(SqQueue *q) { return(q->front==q->rear); } (4) 入队列 enQueue(q,e) 在队列不满的条件下,先将队尾指针 rear 循环增 1,然后将元素添加到该位置。对应算法 如下: int enQueue(SqQueue *&q,ElemType e) { if ((q->rear+1)%MaxSize==q->front) /*队满*/ return 0; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return 1; } (5) 出队列 deQueue(q,e) 在队列 q 不为空的条件下,将队首指针 front 循环增 1,并将该位置的元素值赋给 e。对 应算法如下: int deQueue(SqQueue *&q,ElemType &e) { if (q->front==q->rear) /*队空*/ return 0;