数据结构第3章 栈和队列

第3章栈和队列3.1栈

3.2队列

3.3应用数据结构第3章栈和队列本章学习目标理解栈的定义及其基本运算掌握顺序栈和链栈的各种操作实现理解队列的定义及其基本运算掌握循环队列和链队列的各种操作实现学会利用栈和队列解决一些问题数据结构第3章栈和队列栈和队列是两种重要的线性结构栈和队列是操作受限的线性表出进排队买票汉诺塔进出数据结构第3章栈和队列3.1栈3.1.1栈的基本概念栈：限制仅在表的一端进行插入和删除操作的线性表栈的操作特性：按先进后出(FILO)或后进先出(ＬIＦＯ)的原则

栈顶(top)：允许插入和删除的一端。约定top始终指向栈顶位置。栈底(bottom):不允许插入和删除的一端。

入栈顺序：

e0e1e2…en-2en-1

出栈顺序：

en-1en-2…e2e1e0

栈可以对序列实现求逆en-1e0e1en-2…进栈（Push）出栈（Pop）栈顶top栈底bottom

数据结构第3章栈和队列栈的基本运算：InitStack(s)初始化操作，初始化为空栈s。IsEmpty(s)判断栈空函数。如果s是空栈，返回“true”，否则返回“false”。IsFull(s)判断栈满函数。主要应用在顺序存储结构中，如果s栈满，返回“true”，否则返回“false”。Push(s，x)压栈操作。将元素x插入到栈s中，并使x成为新的栈顶元素。Pop(s)出栈函数。如果栈s非空，那么返回栈顶元素，并删除该栈顶元素，否则返回空值NULL。GetTop(s)获取栈顶元素。如果栈s非空，那么返回值为栈顶元素，否则返回空值NULL。EmptyStack(s)清空栈操作。将栈s中的所有元素清除掉，使之成为一个空栈。DestroyStack()销毁栈。释放栈占用的存储空间。数据结构第3章栈和队列栈有两种存储结构：顺序存储结构和链式存储结构。

3.1.2栈的顺序存储结构

顺序栈：顺序存储结构的栈。顺序栈：用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示栈顶指针：指示栈顶位置

ABACBA(a)空栈（b）元素A进栈（c）元素B、C进栈（d）出栈一次（e）出栈二次top-1toptoptoptop-14321043210432104321043210数据结构第3章栈和队列顺序栈类型定义：

#defineStackSize100/*顺序栈的初始分配空间*/typedefstruct{DataTypedata[StackSize];/*保存栈中元素*/inttop;/*栈指针*/}SeqStack;top为int型，取值范围为0--StackSize-1。top=-l表示栈空；top=StackSize-1表示栈满。栈的长度：栈顶指针top+1数据结构第3章栈和队列顺序栈的基本运算：(1)初始化栈运算功能：创建一个空栈，并将初始化栈顶下标top=-1。intInitStack(SeqStack*&sq){sq=(SeqStack*)malloc(sizeof(SeqStack));if(!sq){printf(“memoryisnotenough!”);return0;}sq->top=-1;return1；

}数据结构第3章栈和队列(2)进栈运算功能：栈顶指针加1，将进栈元素放进栈顶指针所指的位置上。

intPush(SeqStack*sq,DataTypex){if(sq->top==StackSize-1)/*栈满*/return0;else{sq->top++;sq->data[sq->top]=x;return1;}}数据结构第3章栈和队列(3)出栈运算功能：先将栈顶元素取出，然后将栈顶指针减1。intPop(SeqStack*sq,DataType&x){if(sq->top==-1)/*栈空*/return0;else{x=sq->data[sq->top];sq->top--;return1;}}数据结构第3章栈和队列(4)取栈顶元素运算功能：将栈中top处的元素取出赋给变量x。intGetTop(SeqStack*sq,DataType&x){if(sq->top==-1)/*栈空*/return0;else{x=sq->data[sq->top];return1;}}数据结构第3章栈和队列(5)判断栈空运算算法功能：若栈为空(top==-1)则返回值l，否则返回值0。intStackEmpty(SeqStack*sq){if(sq->top==-1)return1;elsereturn0;}数据结构第3章栈和队列3.1.3栈的链式存储结构链栈：栈的链式存储结构。第一个结点为栈顶结点优点：链式栈无栈满问题，空间可扩充特点：插入与删除仅在栈顶处执行…∧ls栈顶栈底datanext（栈顶指针）链栈的类型定义：typedefstructstnod{DataTypedata;/*存储结点数据*/structstnode*next;/*指针域*/}LinkStack;数据结构第3章栈和队列栈的基本运算算法：

(1)初始化栈运算功能：创建一个带头结点的链栈，头结点指针ls；用ls->next=NULL标识栈为空栈。

voidInitStack(LinkStack*&ls){ls=(LinkStack*)malloc(sizeof(LinkStack));ls->next=NULL;}数据结构第3章栈和队列(2)判断栈空运算功能：若栈为空则返回值1，否则返回值0。intStackEmpty(LinkStack*ls){if(ls->next==NULL)return1;elsereturn0;}数据结构第3章栈和队列

(3)进栈运算

voidPush(LinkStack*ls,DataTypex)

{LinkStack*p;p=(LinkStack*)malloc(Sizeof(LinkStack));p->data=x;p->next=ls->next;ls->next=p;}数据结构第3章栈和队列(4)出栈运算功能:将栈顶结点的data域值赋给x,然后删除该栈顶结点。

intPop(LinkStack*ls，DataType&x){LinkStack*p;if(ls->next==NULL)/*栈空，下溢出*/return0;else{p=ls->next;x=p->data;ls->next=p->next;free(p);return1;}}数据结构第3章栈和队列(5)取栈顶元素运算算法

功能：将栈顶结点的data域值赋给x。intGetTop(LinkStack*ls,DataType&x){if(ls->next==NULL)/*栈空，下溢出*/return0;else{x=ls->next->data;return1;}}数据结构第3章栈和队列3.2队列3.2.1队列的基本概念队列：限制插入操作只能在一端进行，而删除操作只能在另一端进行的线性表操作特性：按先进先出(FIFO)或后进后出(LILO)的原则。队首（front）：能进行删除的一端队尾（rear）：能进行插入操作的一端。出队入队队首（front）队尾（rear）数据结构第3章栈和队列队列的基本操作主要：1)InitQueue(Q)：构造一个空队列Q。2)QueueEmpty(Q)：判断队列是否为空。3)QueueLength(Q)：求队列的长度。4)GetHead(Q)：返回Q的队头元素，不改变队列状态。5)EnQueue(Q，x)：插入元素x为Q的新的队尾元素。6)DeQueue(Q)：删除Q的队头元素。7)C1earQueue(Q)：清除队列Q中的所有元素。数据结构第3章栈和队列队列有两种存储表示：顺序队列和链队列。3.2.2队列的链式存储结构…^front队首指针

队首

队尾rear队尾指针链队：链式存储结构的队列；为一个同时带有首指针和尾指针的单链表队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。数据结构第3章栈和队列链队的类型定义：

typedefstructQNode{DataTypedata;structQNode*next;}QType;/*链队中结点的类型*/typedefstructqptr{QType*front,*rear;}LinkQueue;/*链队类型*/队空的条件:lq->front==lq->next==NULL。数据结构第3章栈和队列链队基本运算算法：(1)初始化队列运算

功能：置队列lq的rear和front均为NULL。voidInitQueue(LinkQueue*&lq){lq=(LinkQuene*)malloc(sizeof(LinkQuene));lq->rear=lq->front=NULL;/*初始情况*/}数据结构第3章栈和队列(2)入队运算功能：创建一个新结点，将其链接到链队列的末尾，并由rear指向它。VoidEnQueue(LinkQueue*lq,DataTypex){QType*s;/*创建新结点，插入到链队的末尾*/s=(QType*)malloc(sizeof(QType));/*创建新结点，插入到链队的末尾*/s->data=x;s->next=NULL;if(lq->front==NULL&&lq->rear==NULL)/*空队*/lq->rear=lq->front=s;else{lq->rear->next=s;lq->rear=s;}}数据结构第3章栈和队列(3)出队运算功能：将front结点的data域值赋给x，并删除该结点。DataTypeDeQueue(LinkQueue*lq){QType*p;DataTypex;if(lq->front==NULL&&lq->rear==NULL)/*空队*/exit(-1);p=lq->front;x=p->data;if(lq->rear==lq->front)/*若原队列中只有一个结点，删除后队列变空*/lq->rear=lq->front=NULL;elselq->front=p->next;free(p);returnx;}数据结构第3章栈和队列(4)取队头元素运算功能：将front指向结点的data域值赋给xDataTypeGetHead(LinkQueue*lq){DataTypex;if(lq->front==NULL&&lq->rear==NULL)/*空队*/exit(-1);x=lq->front->data;returnx;}数据结构第3章栈和队列(5)判断队空运算算法功能：若链队为空，则返回1；否则返回0intQueueEmpty(LinkQueue*lq){if(lq->front==NULL&&lq->rear==NULL)return1;elsereturn0;}数据结构第3章栈和队列3.2.3循环队列顺序队列：顺序存储结构的队列，即用一组地址连续的存储单元依次存放队头到队尾的元素；顺序队列：实质是运算受限的顺序表；543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空队（b）a、b入队（c）a、b出队，c、d入队（d）假溢出数据结构第3章栈和队列3.2.3循环队列由于队列的队头和队尾的位置是变化的，设立两个指针front和rear，指针front队头，rear指示队尾下一个元素；每插入一新元素，rear增1，每删除一元素，front增1。front=rear=0表示空队列，rear=MAXSIZE表示队满。543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空队（b）a、b入队（c）a、b出队，c、d入队（d）假溢出数据结构第3章栈和队列543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空队（b）a、b入队（c）a、b出队，c、d入队（d）假溢出避免假溢出有两种办法：

1)每次一个元素出队，将整个队列向前移动一个位置。

2)采用循环队列：将顺序队列的数据区data[0～MAXSIZE-1]看成一个首尾相接的圆环，头尾指针的关系不变数据结构第3章栈和队列循环队列的类型定义：

#defineMAXSIZE100/*最大队列长度*/typedefstruct{datatypedata[MAXSIZE];/*存储队列的数据空间*/intfront;/*队头指针，若队列不空，则指向队头元素*/intrear;/*队尾指针，若队列不空，则指向队尾元素的下一个位置*/}SeqQueue;

rearfront0123e4e3数据结构第3章栈和队列循环队列特点

rearfront

0123(3)队空将头尾连接成一个环，形成循环队列。

rear(1)一般情况front0123e4e3

(2)队满

e3

e40123reare5rear=fronte6rear=frontfront数据结构第3章栈和队列在入队时，rear=（rear+1）%MAXSIZE。存储队列的数组就变为首尾相接的一个环，即为循环队列。在出队时，front=(front+1)%MAXSIZE，实现存储空间的首尾相接。判断队列“空”还是“满”的处理方法：一是另设一个标志位以区别队列的“空”和“满”；二是少用一个元素的空间，约定以“队头指针在队尾指针的下一位置(指环状的下一位置)上”作为队列“满”的标志。数据结构第3章栈和队列543210543210543210dcfedcgfrontrearrearfrontrearfront(a)正常情况（b）队满（c）队空

在循环队列中：若front=rear，则称为队空；若(rear+1)%maxsize=front,则称为队满。循环队列中能装入的元素个数为maxsize-1，即浪费一个存储单元，但是这样可以给操作带来较大方便。数据结构第3章栈和队列3．循环队列的基本操作(1)构造空队列intInitQueue(SeqQueue*&q){q=(SeqQueue*)malloc(sizeof(SeqQueue));

/*开辟一个足够大的存储队列空间*/if(!q)return0;q->front=q->rear=0;

/*将队列头尾指针置为零*/return1;}数据结构第3章栈和队列(2)判断队空intQueueEmpty(SeqQueue*q){return(q->front==q->rear);

/*如果队列为空，则返回1，否则返回0*/}数据结构第3章栈和队列(3)入队

intEnQueue(SeqQueue*q，DataTypex){if((q->rear+1)%MAXSIZE==q->front)

/*判断队列是否满*/{printf("\n循环队列满!”);returnFALSE;/*若队列满，则终止*/}q->data[q->rear]=x;/*将元素x入队*/q->rear=(q->rear+1)％MAXSIZE;/*修改队尾指针*/returnTRUE;}数据结构第3章栈和队列(4)出队

DataTypeDeQueue(SeqQueue*q){DataTypex;if(q->front==q->rear)/*判断队列是否空*/{printf("\n循环队列空!不能做删除操作!");returnFALSE;/*若队列空，则终止*/}x=q->data[q->front];/*将队头元素出队并赋给变量x*/q->front=(q->front+1)％MAXSIZE;/*修改队列头指针*/returnx;/*将被删除元素返回*/}数据结构第3章栈和队列3.3应用3.3.1栈的应用【例3.1】

设计一个算法，判断一个表达式中符号“(”与“)”、“[”与“]”、“{”与“}”是否匹配。若匹配，则返回1；否则返回0。设置一个栈st；用i扫描表达式exps，当遇到“(”、“[”、“{”时，将其进栈，遇到“}”、“]”、“)”时，判断栈顶是否是相匹配的括号。若不是，则退出扫描过程，返回0；否则直至exps扫描完毕为止；若top==-1，则返回1，否则返回0。数据结构第3章栈和队列#defineMax100intmatch(char*exps){charst[Max];inttop=-1,i=0;intnomatch=0;while(exps[i]!=’\0'&&nomatch==0){switch(exps[i]){case'(':top++;st[top]=exps[i];break;case'[':top++;t[top]=exps[i];break;case'{':top++;t[top]=exps[i];break;

case')':if(exps[top]=='(')top--;elsenomatch=l;break;case']':if(exps[top]==’]’)top--;elsenomatch=1;break;case'}':if(exps[top]==’{‘)top--;elsenomatch=l;break;}i++;}if(nomatch==0&&top==-1)

/*栈空且符号匹配则返回l*/return1;elsereturn0;/*否则返回0*/}数据结构第3章栈和队列【例3.2】数制转换问题。把一个非负十进制整数转换成n（2≤n≤35）进制数，其中各位的系数如果大于9的依次用大写英文字母A~Z表示。十进制整数x转换成n进制数的法则是：对x除n取余，直到整商为０为止，先得到的余数需要后输出。例如，十进制整数83转换成8进制数的过程如下图所示，结果为(123)8。数据结构第3章栈和队列Typedef****SeqStack；main(){ intx,n; SeqStack*stack; InitStack(stack);

/*初始化栈stack*/ do { printf("x="); scanf("%d",&x); printf("n="); scanf("%d",&n); }while(n<2||n>35||x<0);/*输入有效数据,x是十进制数,n是进制*/while(x)/*除n取余,余数保存在堆栈中*/

{ Push(stack,x%n); x/=n;} while(!ISEmpty(stack))/*依次出栈，直到栈空*/ { Pop(stack,&x); if(x<10) printf("%c",x+'0'); /*输出位的系数，范围’0’~’9’*/ else printf("%c",x+'A'-10); /*输出位的系数，范围’A’~’Z’*/ } printf("\n"); DestroyStack(stack);}数据结构第3章栈和队列【例3.3】利用一个栈逆置一个带头结点的单链表，已知head是带头结点的单链表(a1，a2，…，an)(其中n≥0)。说明如下：

typedefintDataType；

typedefstructnode{DataTypedata；

structnode*next；

}LinkList；

LinkList*head;请设计一个算法，利用一个顺序栈将上述单链表实现逆置利用一个顺序栈将单链表(a1，a2，…，an)(其中

n≥0)逆置为(an，an-l，…，a1)数据结构第3章栈和队列数据结构第3章栈和队列

解题思路：

1)建立一个带头结点的单链表head。

2)输出该单链表。

3)建立一个空栈s(顺序栈)。

4)依次将单链表的数据入栈。

5)依次将单链表的数据出栈，并逐个将出栈的数据存入单链表的数据域(自前向后）。

6)再输出单链表。数据结构第3章栈和队列/*利用顺序栈逆置单链表程序*/#include<stdio.h>#include<malloc.h>#definemaxsize100/*栈的最大元素数为100*/typedefintDataType;typedefstructnode/*定义单链表结点类型*/{DataTypedata;structnode*next;}LinkList;LinkList*head;/*定义单链表的头指针*/typedefstruct/*定义顺序栈*/{DataTyped[maxsize];inttop;}SeqStack;SeqStacks;/*定义顺序栈s，s是结构体变量，s是全局变量*/数据结构第3章栈和队列LinkList*CreatList()/*建立单链表*/{LinkList

*p,*q;intn=0;p=q=(LinkList

*)malloc(sizeof(LinkList

t));head=p;p->next=NULL;

/*头结点的数据域不存放任何东西*/p=(LinkList

*)malloc(sizeof(LinkList

));scanf("%d",&p->data);while(p->data!=-1)

/*输入-l表示链表结束*/

{n=n+1;q->next=p;q=p;p=(LinkList

*)malloc(sizeof(LinkList

));scanf("%d",&p->data);}

q->next=NULL;free(p)return(head);}数据结构第3章栈和队列voidprint(LinkList*head)

/*输出单链表*/{LinkList

*p;p=head->next;if(p==NULL)printf("Thisisanempty1ist．\n");else{do{printf("%6d",p->data);p=p->next;}while(p!=NULL);printf("\n");}}数据结构第3章栈和队列SeqStackInitStack()

/*构造一个空栈s*/{s.top=-1;returns;}数据结构第3章栈和队列intpush(SeqStack*s,DataTypex)/*入栈，此处s是指向顺序栈的指针*/{if((*s).top==maxsize-1)/*(*s).top即为s->top，下同*/{printf("栈已满，不能入栈!\n");return0;}

else{(*s).top++;/*栈顶指针上移*/(*s).d[(*s).top]=x;/*将x存入栈中*/returnx;}}数据结构第3章栈和队列DataTypepop(SeqStack*s)/*出栈，s是指向顺序栈的指针*/{DataTypey;if((*s).top==-1){printf("栈为空，无法出栈!\n");return0;}else{y=(*s).d[(*s).top];/*栈顶元素出栈，存入y中*/(*s).top--;/*栈顶指针下移*/returny;}}数据结构第3章栈和队列intStackEmpty(SeqStacks)/*判栈空，此处s是结构体变量*/{returns.top==-1;}intStackFull(SeqStacks)/*判栈满，此处s是结构体变量*/{returns.top==maxsize-1;}数据结构第3章栈和队列LinkList*backlinklist(LinkList*head)/*利用顺序栈s逆置单链表head*/{LinkList*p;p=head->next;initstack();while(p){push(&s,p->data);/*单链表的数据依次入栈s*/p=p->next;}p=head->next;while(!stackempty(s)){p->data=pop(&s);/*数据出栈依次存入单链表的数据域*/p=p->next;}return(head);}数据结构第3章栈和队列voidmain(){linklist*head;head=creatlist();print(head);head=backlinklist(head);print(head);}数据结构第3章栈和队列3.3.2队列的应用【例3．4】打印杨辉三角形是一个初等数学问题。系数表中的第i行有i+1个数，除了第1个和最后一个数为1外，其余的数则为上一行中位于其左、右的两数之和(如图3．10所示）。数据结构第3章栈和队列分析第

i行元素与第i+1行元素的关系目的是从前一行的数据可以计算下一行的数据数据结构第3章栈和队列从第i

行数据计算并存放第i+1行数据数据结构第3章栈和队列#defineMAXSIZE10/*定义队列的最大长度*/#include<stdio.h>typedefintdatatype;typedefstruct{intdata[MAXSIZE];intfront;intrear;}SeqQueue;数据结构第3章栈和队列SeqQueue*InitQueue(){SeqQueue*q;

q=(SeqQueue*)malloc(sizeof(SeqQueue));q->front=q->rear=0;returnq;}

数据结构第3章栈和队列voidEnQueue(SeqQueue*q,datatypex){if((q->rear+1)%MA