《数据结构实用教程（C语言版）》课件第3章 栈和队列

第3章栈和队列本章主要介绍下列内容栈的概念、存储结构及其基本操作

队列的概念、存储结构及其基本操作栈与队列的应用举例本章目录

3.1栈1

3.2队列2

3.3栈和队列的应用举例3

3.4本章小结4结束3.1栈3.1.1栈的概念3.1.2栈的基本操作3.1.3顺序栈3.1.4链栈返回到总目录3.1.1

栈的概念例如，在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取，这种后进先出的线性结构称为栈（stack），栈又称为后进先出（lastinfirstout）的线性表，简称LIFO表。栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。插入元素又称为进栈，删除元素又称为出栈。允许进行插入和删除操作的一端称为栈顶（top），另一端称为栈底（bottom）。处于栈顶位置的数据元素称为栈顶元素，处于栈底位置的数据元素称为栈底元素。不含任何数据元素的栈称为空栈。

返回到本节目录假设有一个栈S=（a1，a2，…，an），栈中元素按a1，a2，…，an的次序进栈后，进栈的第一个元素a1为栈底元素，出栈的第一个元素an为栈顶元素，也就是出栈的操作是按后进先出的原则进行的，其结构如图3-1所示。图3-1栈结构示意图3.1.1

栈的概念返回到本节目录3.1.2栈的基本操作

栈除了在栈顶进行进栈与出栈外，还有初始化、判空等操作，常用的基本操作有：（1）初始化栈InitStack(S)。其作用是构造一个空栈S。（2）判断栈空EmptyStack(S)。其作用是判断是否是空栈，若栈S为空，则返回1；否则返回0。（3）进栈Push(S,x)。其作用是当栈不为满时，将数据元素x插入栈S中，使其为栈S的栈顶元素。（4）出栈Pop(S,x)。其作用是当栈S不为空时，将栈顶元素赋给x，并从栈S中删除当前栈顶元素。（5）取栈顶元素GetTop(S,x)。其作用是当栈S不为空时，将栈顶元素赋给x并返回，操作结果只是读取栈顶元素，栈S不发生变化。返回到本节目录3.1.3顺序栈

由于栈是操作受限制的线性表，因此与线性表类似，栈也有两种存储结构，即顺序存储结构和链式存储结构。1.顺序栈的定义栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素位置的变量来实现。顺序栈中栈顶指针与栈中数据元素的关系如图3-2所示。

图3-2顺序栈中栈顶指针与栈中数据元素的关系图

返回到本节目录2.顺序栈的类型定义#defineMAXLEN100/*顺序栈存储空间的总分配量*/typedefcharElemType;/*定义ElemType为char类型*/typedefstruct/*顺序栈存储类型*/{ElemTypedata[MAXLEN];/*存放顺序栈的数组*/inttop;/*记录栈顶元素位置的变量*/}SeqStack;顺序栈被定义为一个结构体类型，其中ElemType为栈元素的数据类型，可以根据需要而指定某种具体的类型。data为一个一维数组，用于存储栈中的数据元素，top为int类型，用于记录栈顶元素所在的位置。注：顺序栈的程序是由C语言描述，C语言的数组下标从0开始。3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（1）初始化栈操作首先创建一个空栈，并将栈顶下标top初始化为-1，算法描述见算法3.1。算法3.1voidInitStack(SeqStack*S){S->top=-1;/*初始化的顺序栈为空*/}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（2）判断栈空操作判断是否是空栈（即S->top==-1），若栈S为空，则返回1；否则返回0，算法描述见算法3.2。算法3.2intEmptyStack(SeqStack*S){if(S->top==-1)/*栈为空*/return1;elsereturn0;}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（3）进栈操作进栈操作的过程如图3-3所示。先判断栈S如图3-3（a）是否为满，若不满再将记录栈顶的下标变量top加1如图3-3（b），最后将进栈元素放进栈顶位置上如图3-3（c）所示，算法描述见算法3.3。图3-3进栈操作过程图

3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（3）进栈操作算法3.3intPush(SeqStack*S,ElemTypex){if(S->top==MAXLEN-1)/*栈为满*/{printf("栈满!");return0;}/*栈满不能进栈*/else/*栈不为满*/{S->top++;S->data[S->top]=x;return1;}}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（4）出栈操作出栈操作的过程如图3-4所示。先判断栈S如图3-4（a）是否为空，若不空将栈顶元素取出赋给指针变量*x，如图3-4（b）所示，然后将记录栈顶的下标变量top减1如图3-4（c）所示，算法描述见算法3.4。图3-4出栈操作过程图3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（4）出栈操作intPop(SeqStack*S,ElemType*x){if(EmptyStack(S))/*调用判空函数EmptyStack(S)，判断栈是否为空*/{printf("栈空!");return0;/*栈空不能出栈*/}else/*栈不为空*/{*x=S->data[S->top];S->top--;return1;}}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（5）取栈顶元素将栈顶元素赋给指针变量*x，操作结果只是读取栈顶元素，栈S不发生变化，算法描述见算法3.5。算法3.5intGetTop(SeqStack*S,ElemType*x){if(EmptyStack(S))/*调用判空函数EmptyStack(S)，判断栈是否为空*/{printf("栈空!");return0;}else/*栈不为空*/{*x=S->data[S->top];return1;}}3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现上述算法3.1-3.5为顺序栈的基本操作函数，读者可以对照执行主函数调用后的结果分析，进一步了解顺序栈的各种操作的过程实现。（6）设计主函数如下：main(){SeqStackS;ElemTypex;InitStack(&S);printf("依次进栈元素为：\n");printf("r元素进栈\n");Push(&S,'r');printf("a元素进栈\n");Push(&S,'a');printf("h元素进栈\n");Push(&S,'h');3.1.3顺序栈返回到本节目录3.顺序栈的基本操作实现（6）设计主函数如下：printf("c元素进栈\n");Push(&S,'c');GetTop(&S,&x);printf("栈顶元素为：%c\n",x);printf("出栈序列为：");while(!EmptyStack(&S)){Pop(&S,&x);printf("%c",x);}printf("\n");}3.1.3顺序栈上述程序的执行结果如下：依次进栈元素为：r元素进栈a元素进栈h元素进栈c元素进栈栈顶元素为：c出栈序列为：char

返回到本节目录1.链栈的定义用链式存储结构实现的栈称为链栈，链栈与不带头结点单链表组织形式相似，因为栈的主要操作是在栈顶进行插入与删除操作，显然将链表的第一个结点作为栈顶是最方便的，因此，没有必要如单链表那样为了操作方便附加一个头结点，通常链栈表示如图3-5所示。图3-5链栈结构示意图3.1.4链栈返回到本节目录2.链栈的类型定义与单链表的类型定义相同，在此用LinkStack命名。链栈的类型定义如下：typedefcharElemType;/*定义ElemType为char类型*/typedefstructnode/*链栈存储类型*/{ElemTypedata;/*定义结点的数据域*/structnode*next;/*定义结点的指针域*/}LinkStack;3.1.4链栈返回到本节目录3.链栈的基本操作实现（1）初始化栈操作首先创建一个空栈，将链栈类型的变量S=NULL标识为空栈，算法描述见算法3.6。算法3.6LinkStack*InitStack(){LinkStack*S;S=NULL;/*初始化栈为空*/returnS;}3.1.4链栈返回到本节目录3.链栈的基本操作实现（2）判断栈空操作判断是否是空栈（即S==NULL），若栈S为空，则返回1；否则返回0，算法描述见算法3.7。算法3.7intEmptyStack(LinkStack*S){if(S==NULL)/*栈为空*/return1;elsereturn0;}3.1.4链栈返回到本节目录3.链栈的基本操作实现（3）进栈操作先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下：将新结点p的指针域指向原栈顶S（执行语句p->next=S）。将栈顶S指向新结点p（执行语句S=p）。进栈操作的过程如图3-6所示，算法描述见算法3.8。注：进栈操作的①与②语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。图3-6进栈操作过程图3.1.4链栈返回到本节目录3.链栈的基本操作实现（3）进栈操作算法3.8LinkStack*Push(LinkStack*S,ElemTypex){LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));/*生成新结点*/p->data=x;/*将x放入新结点的数据域*/p->next=S;/*将新结点插入链表表头之前*/S=p;/*新结点作为栈顶*/returnS;/*返回栈顶S*/}3.1.4链栈返回到本节目录3.链栈的基本操作实现（4）出栈操作先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下：结点p指针域指向原栈顶S（执行语句p=S）。栈顶S指向其的下一个结点（执行语句S=S->next）释放p结点空间（执行语句free(p)）。出栈的过程如图3-7所示，算法描述见算法3.9。图3-7出栈操作过程图3.1.4链栈返回到本节目录3.链栈的基本操作实现（4）出栈操作LinkStack*Pop(LinkStack*S,ElemType*x){LinkStack*p;if(EmptyStack(S))/*调用判空函数EmptyStack(S)，判断栈是否为空*/{printf("栈空!");returnNULL;}/*栈空不能出栈*/

else/*栈不为空*/{*x=S->data;/*栈顶元素取出赋给x*/p=S;/*p结点指向原栈顶S*/S=S->next;/*原栈顶S指向其下一个结点*/free(p);/*释放原栈顶空间*/returnS;}/*返回栈顶S*/}3.1.4链栈返回到本节目录3.链栈的基本操作实现（5）取栈顶元素将栈顶元素赋给指针变量*x，操作结果只是读取栈顶元素，栈S不发生变化，算法描述见算法3.10。intGetTop(LinkStack*S,ElemType*x){if(EmptyStack(S))/*调用判空函数EmptyStack(S)，判断栈是否为空*/{printf("栈空!");return0;}else/*栈不为空*/{*x=S->data;/*栈顶元素赋给变量x*/return1;}}3.1.4链栈返回到本节目录3.链栈的基本操作实现上述算法3.6-3.10为链栈的基本操作函数，读者可以对照执行主函数调用后的结果分析，进一步了解链栈的各种操作的过程实现。（6）设计主函数如下：main(){LinkStack*S;ElemTypex;S=InitStack();printf("依次进栈元素为：\n");printf("r元素进栈\n");S=Push(S,'r');printf("a元素进栈\n");S=Push(S,'a');printf("h元素进栈\n");S=Push(S,'h');3.1.4链栈返回到本节目录3.链栈的基本操作实现（6）设计主函数如下：printf("c元素进栈\n");S=Push(S,'c');GetTop(S,&x);printf("栈顶元素为：%c\n",x);printf("出栈序列为：");while(!EmptyStack(S)){S=Pop(S,&x);printf("%c",x);}printf("\n");}上述程序的执行结果与顺序栈对应程序的执行结果相同。3.1.4链栈返回到本节目录3.2队列3.2.1队列的概念3.2.2队列的基本操作3.2.3顺序队列3.2.4循环队列3.2.5链队列返回到总目录例如，在日常生活中的排队上车，排队的规则是不允许“插队”。后来的人需站在队尾，每次总是队头先上车。这种先进先出的规则应用在数据结构中称为队列（queue），队列又称为先进先出（firstinfirstout）的线性表，简称FIFO表。队列也是一种特殊的线性表。与栈不同，其插入操作限定在线性表的一端进行，删除操作限定在线性表的另一端进行，队列插入操作又称为入队，删除操作又称为出队，允许进行插入的一端称为队尾（rear），允许进行删除的一端称为队头（front）。处于队头位置的数据元素称为队头元素。处于队尾位置的数据元素称为队尾元素。不含任何数据元素的队列称为空队。3.2.1队列的概念返回到本节目录假设有一个队列Q=(a1，a2，…，an），队列中元素按a1，a2，…，an的次序入队后，入队的第一个元素a1为队头元素，最后一个元素an为队尾元素，队列的操作是按先进先出的原则进行的，其结构如图3-8所示。图3-8队列结构示意图

3.2.1队列的概念返回到本节目录3.2.2队列的基本操作队列的除了在队头进行出队和队尾进行入队外，还有初始化、判空等操作，常用的基本操作有：（1）初始化队列InitQueue(Q)。其作用是构造一个空队列Q。（2）判断队列空EmptyQueue(Q)。其作用是判断是否是空队列，若队列Q为空，则返回1；否则返回0。（3）入队EnQueue(Q,x)。其作用是当队列不为满时，将数据元素x插入队列Q的队尾，使其为队列Q的队尾元素。（4）出队DeQueue(Q,x)。其作用是当队列Q不为空时，将队头元素赋给x，并从队列Q中删除当前队头元素，而其后继元素成为队头元素。（5）取队头元素GetFront(Q,x)。其作用是当队列Q不为空时，将队头元素赋给x并返回，操作结果只是读取队头元素，队列Q不发生变化。返回到本节目录由于队列是操作受限制的线性表，因此与线性表类似，队列也有两种存储结构，即顺序存储结构和链式存储结构。1.顺序队列的定义队列的顺序存储结构称为顺序队列。类似于顺序表的类型定义，顺序队列用一个一维数组和两个分别指向队头元素与队尾元素的变量来实现。3.2.3顺序队列

返回到本节目录2.顺序队列的类型定义#defineMAXSIZE100/*顺序队列存储空间的总分配量*/typedefcharElemType;/*定义ElemType为char类型*/typedefstruct/*顺序队列存储类型*/{ElemTypedata[MAXSIZE];/*存放顺序队列的数组*/intfront;/*记录队头元素位置的变量*/intrear;/*记录队尾元素位置的变量*/}SeqQueue;3.2.3顺序队列返回到本节目录顺序队列中的几种状态如图3-9所示。图3-9顺序队列中的几种状态假设图3-9中的最大存储空间为MAXSIZE=6，可以看出，当队列初始化时front=rear=-1，队列为空如图3-9（a）所示；当rear=MAXSIZE-1=5时，再加入新元素，数组越界而导致程序发生异常的错误，如图3-9（e）所示。但此队列为空或有剩余存储单元，我们将这种现象称为“假溢出”。如何解决“假溢出”现象？请见3.2.4节循环队列。3.2.3顺序队列返回到本节目录1.循环队列的定义将顺序存储队列的元素的一维数组首尾相接，形成一个环状。如图3-10所示。我们将这种形式表示的队列称为循环队列。循环队列仍然是顺序队列结构，只是逻辑上和前面的顺序队列有所不同。图3-10（a）中队头与队尾指针指向同一位置时为空队，非空队时如图3-10（b）中队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队列的队尾元素位置。图3-10循环队列示意图3.2.4循环队列

返回到本节目录3.2.4循环队列假设队列开辟的数组单元数为MAXSIZE，它的数组下标在0～MAXSIZE-1之间，若使队头或队尾增1，可以利用取模运算实现。即front=(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;【例3.1】图3-10（b）所示的循环队列示意图最大空间为MAXSIZE=8，数组下标为0～7之间，求a5元素入队的位置。解：入队队尾指针增1当前队尾指针：rear=7;入队后队尾指针：rear=(rear+1)%MAXSIZE=0;返回到本节目录3.2.4循环队列因此，a5元素入队后对应的下标为0。a5元素入队后结果如图3-11所示。图3-11图3-10（b）中a5元素入队后循环队列示意图返回到本节目录3.2.4循环队列2.循环队列中队空和队满的条件【例3.2】图3-10（b）所示的循环队列示意图，a5、a6、a7、a8元素依次入队后，其队列如图3-12所示。图3-12所示图中a1、a2、a3、a4、a5、a6、a7、a8元素依次出队后，其队列如图3-13所示。图3-12图3-10（b）中a5、a6、a7、a8元素依次入队后循环队列示意图返回到本节目录3.2.4循环队列2.循环队列中队空和队满的条件图3-13图3-12中a1、a2、a3、a4、a5、a6、a7、a8元素依次出队后循环队列示意图循环队列解决了顺序队列的“假溢出”现象，但新的问题出现了，队满的条件不再是rear==MAXSIZE-1，而是front==rear和队空的条件相同了。解决方法：损失一个单元不用，即当循环队列中元素的个数是MAXSIZE-1时就认为队列已满，这样循环队列的队满条件就变成：(rear+1)%MAXSIZE==front。队空条件不变仍是：front==rear。返回到本节目录3.2.4循环队列2.循环队列中队空和队满的条件【例3.3】图3-10（b）所示的循环队列示意图，a5、a6、a7元素依次入队后队满，其队列如图3-14所示。图3-14图3-10（b）中a5、a6、a7元素依次入队后队满的循环队列示意图返回到本节目录3.2.4循环队列3.循环队列的基本操作实现（2）判断队列空操作判断是否是空队列（即Q->front==Q->rear），若队列Q为空，则返回1；否则返回0，算法描述见算法3.12。算法3.12intEmptyQueue(SeqQueue*Q){if(Q->front==Q->rear)/*队列为空*/return1;elsereturn0;}返回到本节目录3.2.4循环队列3.循环队列的基本操作实现

（3）入队操作入队操作的过程如图3-15所示。先判断队列Q如图3-15（a）否已满，若不满再将队中的记录队尾的下标变量rear加1如图3-15（b）所示，最后将入队元素x放进队尾位置上如图3-15（c）所示，算法描述见算法3.13。返回到本节目录图3-15入队操作的过程图3.2.4循环队列3.循环队列的基本操作实现算法3.13intEnQueue(SeqQueue*Q,ElemTypex){if((Q->rear+1)%MAXSIZE==Q->front)/*队列为满*/{printf("队满!");return0;/*队满不能入队*/}else/*队不为满*/{Q->rear=(Q->rear+1)%MAXSIZE;/*队尾指针增1*/Q->data[Q->rear]=x;return1;}}

返回到本节目录3.2.4循环队列3.循环队列的基本操作实现（4）出队操作出队操作的过程如图3-16所示。先判断队列Q如图3-16（a）否为空，若不空再将队中的记录队头的下标变量front加1后将队头元素取出赋给*x，如图3-16（b）所示，出队后如图3-16（c）所示，算法描述见算法3.14。返回到本节目录图3-16出队操作的过程图3.2.4循环队列3.循环队列的基本操作实现算法3.14intDeQueue(SeqQueue*Q,ElemType*x){if(EmptyQueue(Q))/*调用判空函数EmptyQueue(Q)，判断队列是否为空*/{printf("队空!");return0;/*队空不能出队*/}else/*队不为空*/{Q->front=(Q->front+1)%MAXSIZE;/*队头指针增1*/*x=Q->data[Q->front];return1;}}返回到本节目录3.2.4循环队列3.循环队列的基本操作实现（5）取队头元素将队头元素赋给指针变量*x，操作结果只是读取队头元素，队列Q不发生变化，算法描述见算法3.15。算法3.15intGetFront(SeqQueue*Q,ElemType*x){if(EmptyQueue(Q))/*调用判空函数EmptyQueue(Q)，判断队列是否为空*/{printf("队空!");return0;}else/*队不为空*/{*x=Q->data[(Q->front+1)%MAXSIZE];return1;}}返回到本节目录3.2.4循环队列3.循环队列的基本操作实现上述算法3.11-3.15为循环队列的基本操作函数，读者可以对照执行主函数调用后的结果分析，进一步了解循环队列的各种操作的过程实现。（6）设计主函数如下：main(){SeqQueueQ;ElemTypex;InitQueue(&Q);printf("依次入队元素为：\n");printf("q元素入队\n");EnQueue(&Q,'q');printf("u元素入队\n");EnQueue(&Q,'u');printf("e元素入队\n");EnQueue(&Q,'e');printf("u元素入队\n");EnQueue(&Q,'u');返回到本节目录3.2.4循环队列3.循环队列的基本操作实现（6）设计主函数如下：printf("e元素入队\n");EnQueue(&Q,'e');GetFront(&Q,&x);printf("队头元素为：%c\n",x);printf("出队序列为：");while(!EmptyQueue(&Q)){DeQueue(&Q,&x);printf("%c",x);}printf("\n");}返回到本节目录依次入队元素为：q元素进栈u元素进栈e元素进栈u元素进栈e元素进栈队头元素为：q出队序列为：queue上述程序的执行结果如下：3.2.5链队列1.链队列的定义用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。队列中元素的结构和前面单链表中的结点的结构一样。为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点，通常链队列表示如图3-17所示。返回到本节目录图3-17链队列示意图3.2.5链队列2.链队列的类型定义与单链表的类型定义相同，链队列的类型定义如下：typedefcharElemType;/*定义ElemType为char类型*/typedefstructqnode/*链队列存储类型*/{ElemTypedata;/*定义结点的数据域*/structqnode*next;/*定义结点的指针域*/}LinkList;typedefstruct{LinkList*front,*rear;/*定义队列的头指针和尾指针*/}LinkQueue;LinkQueue类型说明中的两个分量均为指针变量且封装在一起，分别为链队列的队头指针和队尾指针。返回到本节目录3.2.5链队列3.链队列的基本操作实现（1）初始化队列操作链队列的初始化即构造一个仅包含头结点的空链队列Q，算法描述见算法3.16。算法3.16LinkQueue*InitQueue(){LinkQueue*Q;/*由队列头指针指向初始化头结点*/Q->front=(LinkList*)malloc(sizeof(LinkList));Q->front->next=NULL;Q->front=Q->rear;/*初始化时队尾指针也指向队头指针*/returnQ;}返回到本节目录3.2.5链队列3.链队列的基本操作实现（2）判断链队列空操作判断是否是空队列（即Q->front==Q->rear），若链队列Q为空，则返回1；否则返回0，算法描述见算法3.17。算法3.17intEmptyQueue(LinkQueue*Q){if(Q->front==Q->rear)/*链队列为空*/return1;elsereturn0;}返回到本节目录3.2.5链队列3.链队列的基本操作实现（3）入队操作先创建一个新结点p，其data域值为x，指针域为空，则入队操作步骤如下：将新结点插入队尾，队尾指针域Q->rear->next指向新结点p（执行语句Q->rear->next=p）。将队尾Q->rear指向新结点p（执行语句Q->rear=p）。入队操作的过程如图3-18所示，算法描述见算法3.18。返回到本节目录图3-18入队操作过程图注：由于链队列本身没有容量限制，因此，在进行入队操作时不用考虑队满情况。3.2.5链队列3.链队列的基本操作实现（3）入队操作算法3.18voidEnQueue(LinkQueue*Q,ElemTypex){LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));/*生成新结点*/p->data=x;/*将x放入新结点的数据域*/p->next=NULL;Q->rear->next=p;/*将新结点插入链队列之后*/Q->rear=p;/*队尾指针指向队尾元素*/}返回到本节目录3.2.5链队列3.链队列的基本操作实现（4）出队操作队头指针是指向队头元素的前一个结点，先将结点p指向队头元素，并将队头元素值取出赋给*x，则删除操作步骤如下：将队头指针的指针域指向原队头元素的下一元素（新队头）的地址如图3-19（a）所示，（执行语句Q->front->next=p->next）。当原队列中仅有一个元素时如图3-19（b）所示，出队后队尾指针指向对头指针（执行语句Q->rear=Q->front）释放p结点空间（执行语句free(p)）。返回到本节目录3.2.5链队列3.链队列的基本操作实现（4）出队操作出队的过程如图3-19所示，算法描述见算法3.19。返回到本节目录图3-19链队列出队操作过程图3.2.5链队列3.链队列的基本操作实现（4）出队操作算法3.19voidDeQueue(LinkQueue*Q,ElemType*x){

LinkList*p;if(EmptyQueue(Q))/*调用判空函数EmptyQueue(Q)，判断队列是否为空*/printf("队空不能出队!");else/*队不为空*/{p=Q->front->next;/*p指向队头元素*/*x=p->data;/*队头元素取出赋给x*/Q->front->next=p->next;/*队头指针的指针域存放新队头元素的地址*/if(p->next==NULL)/*队列中只含有一个元素出队*/Q->rear=Q->front;/*出队后队尾指针指向队头指针，此时队空*/free(p);/*释放原队头结点空间*/}}返回到本节目录3.2.5链队列3.链队列的基本操作实现（5）取队头元素将队头元素赋给指针变量*x，操作结果只是读取队头元素，链队列Q不发生变化，算法描述见算法3.20。算法3.20intGetFront(LinkQueue*Q,ElemType*x){if(EmptyQueue(Q))/*调用判空函数EmptyQueue(Q)，判断队列是否为空*/{printf("队空!");return0;}else/*队不为空*/{*x=Q->front->next->data;/*队头元素赋给变量x*/return1;}}返回到本节目录3.2.5链队列3.链队列的基本操作实现上述算法3.16-3.20为链队列的基本操作函数，读者可以对照执行主函数调用后的结果分析，进一步了解链队列的各种操作的过程实现。（6）设计主函数如下：main(){LinkQueue*Q;ElemTypex;Q=InitQueue();printf("依次入队元素为：\n");printf("q元素入队\n");EnQueue(Q,'q');printf("u元素入队\n");EnQueue(Q,'u');printf("e元素入队\n");EnQueue(Q,'e');返回到本节目录3.2.5链队列3.链队列的基本操作实现（6）设计主函数如下：printf("u元素入队\n");EnQueue(Q,'u');printf("e元素入队\n");EnQueue(Q,'e');GetFront(Q,&x);printf("队头元素为：%c\n",x);printf("出队序列为：");while(!EmptyQueue(Q)){DeQueue(Q,&x);printf("%c",x);}printf("\n");}上述程序的执行结果与循环队列对应程序的执行结果相同。返回到本节目录3.3栈和队列的应用举例

1.栈的应用由于栈的“后进先出”的特点，在数据处理中有着广泛的应用，进制转换就是利用栈做一个辅助的数据结构进行求解的典型示例。【例3.4】使用展转相除法将一个非负十进制整数值转换成二进制数值。即用该十进制数值除以2，并保留其余数，重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。返回到总目录3.3栈和队列的应用举例

1.栈的应用如：(121)10=(1111001)2，其展转相除的过程如图3-20所示。返回到总目录图3-20十进制数121转换二进制的过程图3.3栈和队列的应用举例

1.栈的应用十进制转换为二进制完整算法描述见算法3.21。算法3.21/**************各种常量及结构体类型定义**************/#defineMAXLEN100/*顺序栈存储空间的总分配量*/typedefcharElemType;/*定义ElemType为char类型*/typedefstruct/*顺序栈存储类型*/{ElemTypedata[MAXLEN];/*存放顺序栈的数组*/inttop;/*记录栈顶元素位置的变量*/}SeqStack;返回到总目录3.3栈和队列的应用举例

1.栈的应用/***************栈的初始化函数******************/voidInitStack(SeqStack*S){S->top=-1;/*初始的顺序栈为空*/}/****************栈的判空函数*****************/intEmptyStack(SeqStack*S){if(S->top==-1)/*栈为空*/return1;elsereturn0;}返回到总目录3.3栈和队列的应用举例

1.栈的应用/**************进栈函数**********************/intPush(SeqStack*S,ElemTypex){if(S->top==MAXLEN-1)/*栈为满*/{printf("栈满溢出!");return0;/*栈满不能进栈*/}else/*栈不为满*/{S->top++;S->data[S->top]=x;return1;}}返回到总目录3.3栈和队列的应用举例

1.栈的应用/******************出栈函数******************/intPop(SeqStack*S,ElemType*x){if(EmptyStack(S))/*调用判空函数EmptyStack(S)，判断栈是否为空*/{printf("栈空!");return0;/*栈空不能出栈*/}else/*栈不为空*/{*x=S->data[S->top];S->top--;return1;}}返回到总目录3.3栈和队列的应用举例

1.栈的应用/**************进制转换函数******************/voidD_B(SeqStack*S,ElemTypex){while(x){Push(S,x%2);/*余数入栈*/x/=2;/*被除数data整除以2，得到新的被除数*/}printf("转换后的二进制为：\n");while(!EmptyStack(S)){Pop(S,&x);/*依次从栈中弹出每一个余数并输出*/printf("%d",x);}}返回到总目录3.3栈和队列的应用举例

1.栈的应用/******************主函数******************/main(){SeqStackS;ElemTypex;InitStack(&S);printf("请输入十进制正整数为:\n");scanf("%d",&x);/*输入十进制正整数*/D_B(&S,x);/*调用进制转换函数*/}返回到总目录3.3栈和队列的应用举例

2.队列的应用由于队列的“先进先出”的特点，在实际程序设计也有非常广泛的用途。在此举一个用队列打印杨辉三角的例子来说明其使用方法。【例3.5】打印杨辉三角如图3-21所示。返回到总目录图3-21杨辉三角3.3栈和队列的应用举例

2.队列的应用由图3-21可看出杨辉三角形的特点：即每一行的第一个元素和最后一个元素均为1，其它位置上的数字是其上一行中与之相邻的两个整数之和。所以在打印过程中，第i行上的元素要由第i-1行中的元素来生成。因此，可以利用循环队列实现打印杨辉三角形的过程。在循环队列中依次存放第i-1行上的元素，然后逐个出队并打印，同时生成第i行元素并入队。在整个过程中，杨辉三角中元素的入队顺序如图3-22所示。返回到总目录图3-22杨辉三角入队过程图3.3栈和队列的应用举例

2.队列的应用打印杨辉三角前N行元素完整算法描述见算法3.22。注：打印杨辉三角的最大行数一定要小于循环队列的MAXSIZE-1值。算法3.22/**************各种常量及结构体类型定义**************/#defineMAXSIZE100/*队列存储空间的总分配量*/typedefintElemType;/*定义ElemType为char类型*/typedefstruct/*队列存储类型*/{ElemTypedata[MAXSIZE];/*存放队列的数组*/intfront;/*记录队头元素位置的变量*/intrear;/*记录队尾元素位置的变量*/}SeqQueue;返回到总目录3.3栈和队列的应用举例

2.队列的应用/******************初始化循环队列函数******************/voidInitQueue(SeqQueue*Q){Q->front=Q->rear=0;/*指针初始化*/}/*********************判空队列函数********************/intEmptyQueue(SeqQueue*Q){if(Q->front==Q->rear)/*队列为空*/return1;elsereturn0;}返回到总目录3.3栈和队列的应用举例

2.队列的应用/***********************入队函数**********************/intEnQueue(SeqQueue*Q,ElemTypex){if((Q->rear+1)%MAXSIZE==Q->front)/*队列为满*/{printf("队满!");return0;/*队满不能入队