第3章〓栈和队列 栈和队列是两种特殊的线性表。从数据逻辑结构角度看，栈和队列的元素均呈现一种线性关系； 从运算的角度看，栈和队列是操作受限的线性表。本章介绍栈和队列的概念、存储结构和基本运算的实现算法。 3.1栈 3.1.1栈的基本概念 栈是一种特殊的线性表，其特殊性体现在元素插入和删除运算上，它的插入和删除运算仅限定在表的某一端进行，不能在表中间和另一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作称为进栈(或入栈)，删除操作称为出栈(或退栈)。处于栈顶位置的数据元素称为栈顶元素。不含任何数据元素的栈称为空栈。 正是这种受限的元素插入和删除运算，使得栈表现出先进后出或者后进先出的特点。举一个例子进行说明，假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有5个人，分别编号为①~⑤，按编号的顺序依次进入此死胡同，如图3.1(a)所示。此时若编号为④的人要退出死胡同，必须等⑤退出后才可以。若①要退出，则必须等到⑤、④、③、②依次都退出后才行，如图3.1(b)所示。这里人进出死胡同的原则是先进去的后出来。 图3.1死胡同示意图 在该例中，死胡同就看作是一个栈，栈顶相当于死胡同口，栈底相当于死胡同的另一端，进、出死胡同可看作进栈、出栈操作。插入栈的示意图如图3.2所示。 栈的基本运算主要包括以下6种。 （1） 初始化栈InitStack(st)： 建立一个空栈st。 （2） 销毁栈DestroyStack(st)： 释放栈st占用的内存空间。 （3） 进栈Push(st，x)： 将元素x插入栈st中，使x成为栈st的栈顶元素。 （4） 出栈Pop(st，x)： 当栈st不空时，将栈顶元素赋给x，并从栈中删除当前栈顶元素。 （5） 取栈顶元素GetTop(st，x)： 若栈st不空，取栈顶元素x并返回1； 否则返回0。 （6） 判断栈空StackEmpty(st)： 判断栈st是否为空栈。 包含基本运算的栈如图3.3所示，其中，op1~op6表示上述6个基本运算。 图3.2栈的示意图 图3.3包含基本运算的栈 【例3.1】设一个栈的输入序列为a、b、c、d，借助一个栈(假设栈大小足够大)所得到的出栈序列不可能是。 A. a、b、c、dB. b、d、c、aC. a、c、d、bD. d、a、b、c a、b、c、d序列经过栈的情况如图3.4所示，根据栈的特点，很容易得出d、a、b、c是不可能的，因为d先出栈，说明a、b、c均已在栈中，按照进栈顺序，从栈顶到栈底的顺序应为c、b、a，出栈的顺序只能是d、c、b、a。所以不可能的出栈序列是D。 【例3.2】已知一个栈的进栈序列是1，2，3，…，n，其出栈序列是p1，p2，…，pn，若p1=n，则pi的值为。 A. iB. n-iC. n-i+1D. 不确定 p1=n，则出栈序列是唯一的，即为n，n-1，…，2，1,这样有pi+i=n+1,由此推出pi=n-i+1。本题答案为C。 【例3.3】元素a、b、c、d、e依次进入初始为空的栈中，假设栈大小足够大。若元素进栈后可停留、可立即出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的出栈序列个数是。 A. 3B. 4C. 5D. 6 若元素d第一个出栈，则a、b、c均在栈中，从栈顶到栈底的顺序应为c、b、a，如图3.5所示，此后合法的栈操作如下。 (1) e进栈，e出栈，c出栈，b出栈，a出栈，得到的出栈序列decba。 (2) c出栈，e进栈，e出栈，b出栈，a出栈，得到的出栈序列dceba。 (3) c出栈，b出栈，e进栈，e出栈，a出栈，得到的出栈序列dcbea。 (4) c出栈，b出栈，a出栈，e进栈，e出栈，得到的出栈序列dcbae。 以元素d开头的出栈序列个数为4，本题答案为B。 图3.4序列经过一个栈的情况 图3.5元素出栈的情况 3.1.2栈的顺序存储结构 栈是一种特殊的线性表，和线性表存储结构类似，栈也有两种存储结构： 顺序存储结构和链式存储结构。 栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组data和一个记录栈顶元素位置的变量top组成。习惯上将栈底放在数组下标小的那端，栈顶元素由栈顶指针top所指向。顺序栈类型声明如下。 #define MaxSize 100//顺序栈的初始分配空间大小 typedef struct {ElemType data［MaxSize］;//保存栈中元素，这里假设ElemType为char类型 int top;//栈顶指针 } SqStack; 在上述顺序栈定义中，ElemType为栈元素的数据类型，MaxSize为一个常量，表示data数组中最多可放的元素个数，data元素的下标范围为0~MaxSize-1。当top=-1时表示栈空； 当top=MaxSize-1时表示栈满。 图3.6说明了顺序栈st的几种状态(假设MaxSize=5)。图3.6(a)表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶指针top=-1。如果做出栈运算，则会“下溢出”。 图3.6顺序栈的几种状态 图3.6(b)表示栈中只含一个元素a，在图3.6(a)的基础上执行进栈运算Push(st,'a')可以得到这种状态。此时栈顶指针top=0。 图3.6(c)表示在图3.6(b)基础上又有两个元素b、c先后进栈，此时栈顶指针top=2。 图3.6(d)表示在图3.6(c)状态下执行一次Pop(st,x)运算得到。此时栈顶指针top=1。故b为当前的栈顶元素。 图3.6(e)表示在图3.6(d)状态下执行两次Pop(st,x)运算得到。此时栈顶指针top=-1，又变成栈空状态。 归纳起来，对于顺序栈st，其初始时置st.top=-1，它的4个要素如下。 （1） 栈空条件： st.top==-1。 （2） 栈满条件： st.top==MaxSize-1。 （3） 元素x进栈操作： st.top++； 将元素x存放在st.data［st.top］中。 （4） 出栈元素x操作： 取出栈元素x=st.data［st.top］； st.top--。 顺序栈的基本运算算法如下。 1. 初始化栈运算算法 其主要操作是设定栈顶指针top为-1，对应的算法如下。 void InitStack(SqStack &st)//st为引用型参数 { st.top=-1; } 2. 销毁栈运算算法 这里顺序栈的内存空间是由系统自动分配的，在不再需要时由系统自动释放其空间。对应的算法如下。 void DestroyStack(SqStack st) {} 3. 进栈运算算法 其主要操作是： 栈顶指针加1，将进栈元素存放在栈顶处。对应的算法如下。 int Push(SqStack &st,ElemType x) {if (st.top==MaxSize-1)//栈满上溢出返回0 return 0; else {st.top++; st.data［st.top］=x; return 1;//成功进栈返回1 } } 4. 出栈运算算法 其主要操作是： 先将栈顶元素取出，然后将栈顶指针减1。对应的算法如下。 int Pop(SqStack &st,ElemType &x)//x为引用型参数 {if (st.top==-1)//栈空返回0 return 0; else {x=st.data［st.top］; st.top--; return 1;//成功出栈返回1 } } 5. 取栈顶元素运算算法 其主要操作是： 将栈顶指针top处的元素取出赋给变量x，top保持不动。对应的算法如下。 int GetTop(SqStack st,ElemType &x)//x为引用型参数 {if (st.top==-1)//栈空返回0 return 0; else {x=st.data［st.top］; return 1;//成功取栈顶元素返回1 } } 6. 判断栈空运算算法 其主要操作是： 若栈为空(top==-1)则返回值1，否则返回值0。对应的算法如下。 int StackEmpty(SqStack st) {if (st.top==-1) return 1;//栈空返回1 else return 0;//栈不空返回0 } 提示： 将顺序栈类型声明和栈基本运算函数存放在SqStack.cpp文件中。 当顺序栈的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序栈的各种运算的实现过程。 #include "SqStack.cpp"//包含前面的顺序栈基本运算函数 int main() {SqStack st;//定义一个顺序栈st ElemType e; printf("初始化栈st＼n"); InitStack(st); printf("栈%s＼n",(StackEmpty(st)==1?"空":"不空")); printf("a进栈＼n");Push(st,'a'); printf("b进栈＼n");Push(st,'b'); printf("c进栈＼n");Push(st,'c'); printf("d进栈＼n");Push(st,'d'); printf("栈%s＼n",(StackEmpty(st)==1?"空":"不空")); GetTop(st,e); printf("栈顶元素:%c＼n",e); printf("出栈次序:"); while (!StackEmpty(st))//栈不空循环 {Pop(st,e);//出栈元素e并输出 printf("%c ",e); } printf("＼n"); DestroyStack(st); } 图3.7程序执行结果 上述程序的执行结果如图3.7所示。 【例3.4】若一个栈用数组data［1..n］存储(n为一个大于2的正整数)，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是。 A. top++;data［top］=x;B. data［top］=x;top++; C. top--;data［top］=x;D. data［top］=x;top--; 一个栈中栈元素是向一端伸展的，即从栈底向栈顶方向伸展。这里初始栈顶指针top为n+1，说明data［n］端作为栈底，在进栈时top应递减，由于不存在data［n+1］的元素，所以在进栈时应先将top递减，再将x放在top处。本题答案为C。 3.1.3栈的链式存储结构 栈的链式存储结构是采用某种链表结构，栈的链式存储结构简称为链栈。这里采用单链表作为链栈，如图3.8所示，该单链表是不带头结点的，通过首结点指针ls唯一标识整个单链表。同时，单链表的首结点就是链栈的栈顶结点(图中首结点值为an表示最后进栈的元素是an)，所以ls也作为栈顶指针，栈中的其他结点通过next域链接起来，栈底结点的next域为NULL。因链栈本身没有容量限制，所以不必考虑栈满的情况，这是链栈相比顺序栈的一个优点。 图3.8链栈示意图 链栈的类型定义如下。 typedef struct node {ElemType data;//结点值，假设ElemType为char类型 struct node *next;//指针域 } LinkStack; 归纳起来，链栈ls初始时ls=NULL，其4个要素如下。 （1） 栈空条件： ls==NULL。 （2） 栈满条件： 不考虑。 （3） 元素x进栈操作： 创建存放元素x的结点p，将其插入栈顶位置上。 （4） 出栈元素x操作： 置x为栈顶结点的data域，并删除该结点。 链栈的基本运算算法如下。 1. 初始化栈运算算法 其主要操作是： 置s为NULL标识栈为空栈。对应的算法如下。 void InitStack(LinkStack *&ls)//ls为引用型参数 { ls=NULL; } 2. 销毁栈运算算法 链栈的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间，与单链表销毁算法类似，只是这里链栈是不带头结点的。对应的算法如下。 void DestroyStack(LinkStack *&ls) {LinkStack *pre=ls,*p; if (pre==NULL) return;//考虑空栈的情况 p=pre->next; while (p!=NULL) {free(pre);//释放pre结点 pre=p;p=p->next;//pre、p同步后移 } free(pre);//释放尾结点 } 3. 进栈运算算法 其主要操作是： 先创建一个新结点p，其data域值为x； 然后将该结点插入开头作为新的栈顶结点。对应的算法如下。 int Push(LinkStack *&ls,ElemType x)//ls为引用型参数 {LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack)); p->data=x;//创建结点p用于存放x p->next=ls;//插入p结点作为栈顶结点 ls=p; return 1； } 4. 出栈运算算法 其主要操作是： 将栈顶结点(ls所指结点)的data域值赋给x，然后删除该栈顶结点。对应的算法如下。 int Pop(LinkStack *&ls,ElemType &x)//ls为引用型参数 {LinkStack *p; if (ls==NULL) //栈空,下溢出返回0 return 0; else//栈不空时出栈元素x并返回1 {p=ls;//p指向栈顶结点 x=p->data;//取栈顶元素x ls=p->next;//删除结点p free(p);//释放p结点 return 1; } } 说明： 尽管链栈操作时不考虑上溢出，但仍然需要考虑出栈操作时的下溢出。 5. 取栈顶元素运算算法 其主要操作是： 将栈顶结点(即ls所指结点)的data域值赋给x。对应的算法如下。 int GetTop(LinkStack *ls,ElemType &x) {if (ls==NULL)//栈空,下溢出时返回0 return 0; else//栈不空,取栈顶元素x并返回1 {x=ls->data; return 1; } } 6. 判断栈空运算算法 其主要操作是： 若栈为空(即ls==NULL)则返回值1，否则返回值0。对应的算法如下。 int StackEmpty(LinkStack *ls) {if (ls==NULL) return 1; else return 0; } 提示： 将链栈结点类型声明和链栈基本运算函数存放在LinkStack.cpp文件中。 当链栈的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序栈的各种运算的实现过程。 #include "LinkStack.cpp"//包含前面的链栈基本运算函数 int main() {ElemType e; LinkStack *st;//定义一个链栈st printf("初始化栈st＼n"); InitStack(st); printf("栈%s＼n",(StackEmpty(st)==1?"空":"不空")); printf("a进栈＼n");Push(st,'a'); printf("b进栈＼n");Push(st,'b'); printf("c进栈＼n");Push(st,'c'); printf("d进栈＼n");Push(st,'d'); printf("栈%s＼n",(StackEmpty(st)==1?"空":"不空")); GetTop(st,e); printf("栈顶元素:%c＼n",e); printf("出栈次序:"); while (!StackEmpty(st))//栈不空循环 {Pop(st,e);//出栈元素e并输出 printf("%c ",e); } printf("＼n"); DestroyStack(st); } 上述程序的执行结果如图3.7所示。 【例3.5】以下各链表均不带有头结点，其中最不适合用作链栈的链表是。 A. 只有表尾指针没有表头指针的循环单链表 B. 只有表头指针没有表尾指针的循环单链表 C. 只有表头指针没有表尾指针的循环双链表 D. 只有表尾指针没有表头指针的循环双链表 由于各链表均不带有头结点，这里表头指针就是首结点指针。采用一种链表作为链栈时，通常将链表首结点处作为栈顶。一个链表适不适合作为链栈，就看它是否能够高效地实现栈的基本运算，而栈的主要操作是进栈和出栈。 考虑选项A，只有表尾指针没有表头指针的循环单链表，假设表尾指针为rear，它指向循环单链表的尾结点，如图3.9所示。元素x进栈的操作是： 创建存放x的结点p，将结点p插入在rear结点之后作为栈顶结点，不改变rear； 出栈的操作是： 删除rear结点之后的结点。两种操作的时间复杂度均为O(1)。 图3.9只有表尾指针没有表头指针的循环单链表 考虑选项B，只有表头指针没有表尾指针的循环单链表，假设表头指针为first，它指向循环单链表的首结点，如图3.10所示。元素x进栈的操作是： 创建存放x的结点p，将结点p插入在first结点之前，即p->next=first，first=p，但还要将其改变为循环单链表，而尾结点需要遍历所有结点找到，遍历的时间为O(n)，所以进栈操作的时间复杂度为O(n)； 出栈的操作是： 删除first结点，删除后仍然需要将其改变为循环单链表，所以出栈操作的时间复杂度为O(n)。两种操作的时间复杂度均为O(n)。 图3.10只有表头指针没有表尾指针的循环单链表 考虑选项C和D，由于都是循环双链表，可以通过表头结点直接找到尾结点，在插入和删除后改为循环双链表的时间均为O(1)，所以它们的进栈和出栈操作的时间复杂度都是O(1)。 比较起来，只有表头指针没有表尾指针的循环单链表作为链栈时，进栈和出栈操作的时间性能最差。本题答案为B。 3.1.4栈的应用示例 在较复杂的数据处理过程中，通常需要保存多个临时产生的数据，如果先产生的数据后进行处理，那么需要用栈来保存这些数据。本节通过几个经典示例说明栈的应用方法，并且算法中均采用顺序栈，实际上采用链栈完全相同。 【例3.6】假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。 (1) 下面所示的序列中哪些是合法的？ A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO (2) 通过对(1)的分析，设计一个算法利用链栈的基本运算判定操作序列str是否合法。若合法返回1； 否则返回0。 (1) A、D均合法，而B、C不合法。因为在B中，先进栈一次，立即出栈两次，这会造成栈下溢。在C中共进栈5次，出栈3次，栈的终态不为空。 归纳起来，一个操作序列是合法的，当且仅当其中所有I的个数与O的个数相等，而且任何前缀中I的个数大于或等于O的个数。 (2) 本例用一个顺序栈st来判断操作序列是否合法，其中，str为存放操作序列的字符数组，n为该数组的元素个数。对应的算法如下。 #include "Sqstack.cpp"//包含前面的顺序栈基本运算函数 int Judge(char str［ ］,int n) {int i; ElemType x; SqStack st;//定义一个顺序栈st InitStack(st);//栈初始化 for (i=0;ifront==NULL或lq->rear==NULL(这里采用lq->front==NULL的队空条件)。一般情况下，链队是不会出现队满的情况的。归纳起来，链队lq的4个要素如下。 （1） 队空条件： lq->front==NULL。 （2） 队满条件： 不考虑(因为每个结点是动态分配的)。 （3） 进队操作： 创建结点p，将其插入队尾，并由lq->rear指向它。 （4） 出队操作： 删除队头结点。 在链队上实现队列基本运算算法如下。 1. 初始化队列运算算法 其主要操作是： 创建链队结点，并置该结点的rear和front均为NULL。对应的算法如下。 void InitQueue(LinkQueue *&lq)//lq为引用型参数 {lq=(LinkQueue *)malloc(sizeof(LinkQueue)); lq->rear=lq->front=NULL;//初始时队头和队尾指针均为空 } 2. 销毁队列运算算法 链队的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间。在销毁队列lq时，先像释放单链表一样释放队中所有数据结点，然后释放链队结点lq。对应的算法如下。 void DestroyQueue(LinkQueue *&lq) {QType *pre=lq->front,*p; if (pre!=NULL)//非队空的情况 {if (pre==lq->rear)//只有一个数据结点的情况 free(pre);//释放pre结点 else//有两个或多个数据结点的情况 {p=pre->next; while (p!=NULL) {free(pre);//释放pre结点 pre=p; p=p->next;//pre、p同步后移 } free(pre);//释放尾结点 } } free(lq);//释放链队结点 } 3. 进队运算算法 其主要操作是： 创建一个新结点s，将其链接到链队的末尾，并由rear指向它。对应的算法如下。 int EnQueue(LinkQueue *&lq,ElemType x) //lq为引用型参数 {QType *s; s=(QType *)malloc(sizeof(QType));//创建新结点s，插入链队的末尾 s->data=x;s->next=NULL; if (lq->front==NULL)//原队为空队的情况 lq->rear=lq->front=s;//front和rear均指向s结点 else//原队不为队空的情况 {lq->rear->next=s;//将结点s链到队尾 lq->rear=s;//rear指向它 } return 1; } 4. 出队运算算法 其主要操作是： 将front指向结点的data域值赋给x，并删除该结点。对应的算法如下。 int DeQueue(LinkQueue *&lq,ElemType &x)//lq,x均为引用型参数 {QType *p; if (lq->front==NULL)//原队为队空的情况 return 0; p=lq->front;//p指向队头结点 x=p->data;//取队头元素值 if (lq->rear==lq->front)//若原队列中只有一个结点,删除后队列变空 lq->rear=lq->front=NULL; else//原队有两个或以上结点的情况 lq->front=lq->front->next; free(p); return 1; } 5. 取队头元素运算算法 其主要操作是： 将front指向结点的data域值赋给x。对应的算法如下。 int GetHead(LinkQueue *lq,ElemType &x)//x为引用型参数 {if (lq->front==NULL)//原队为队空的情况 return 0; x=lq->front->data; return 1; } 6. 判断队空运算算法 其主要操作是： 若链队为空，则返回1； 否则返回0。对应的算法如下。 int QueueEmpty(LinkQueue *lq) {if (lq->front==NULL) return 1;//队空返回1 else return 0;//队不空返回0 } 提示： 将链队结点类型声明及其基本运算函数存放在LinkQueue.cpp文件中。 当链队的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会链队的各种运算的实现过程。 #include "LinkQueue.cpp"//包含前面的链队基本运算函数 int main() {LinkQueue *lq;//定义一个链队lq ElemType e; printf("初始化队列＼n"); InitQueue(lq); printf("队%s＼n",(QueueEmpty(lq)==1?"空":"不空")); printf("a进队＼n");EnQueue(lq,'a'); printf("b进队＼n");EnQueue(lq,'b'); printf("c进队＼n");EnQueue(lq,'c'); printf("d进队＼n");EnQueue(lq,'d'); printf("队%s＼n",(QueueEmpty(lq)==1?"空":"不空")); GetHead(lq,e); printf("队头元素:%c＼n",e); printf("出队次序:"); while (!QueueEmpty(lq))//队不空循环 {DeQueue(lq,e);//出队元素e printf("%c ",e);//输出元素e } printf("＼n"); DestroyQueue(lq); } 上述程序的执行结果如图3.18所示。 【例3.16】若使用不带头结点的循环链表来表示队列，lq是这样的链表中尾结点指针，如图3.21所示。试基于此结构给出队列的相关运算算法。 图3.21用循环单链表表示链队 这里使用的循环链表不带头结点，lq始终指向队尾结点，lq->next即为队头结点。当lq==NULL时队列为空，lq->next==lq表示队列中只有一个结点。队列的相关运算算法如下。 typedef struct node {ElemType data;//数据域 struct node *next;//指针域 } QNode;//链队中数据结点类型 //---初始化队列运算算法--- void InitQueue(QNode *&lq) {lq=NULL; } //----销毁链队---- void DestroyQueue(QNode *&lq) {QNode *pre,*p; if (lq!=NULL) {if (lq->next==lq)//原队中只有一个结点 free(lq); else//原队中有两个或以上的结点 {pre=lq; p=pre->next; while (p!=lq) {free(pre); pre=p; p=p->next;//pre和p同步后移 } free(pre);//释放最后一个结点 } } } //----进队运算算法---- void EnQueue(QNode *&lq,ElemType x) {QNode *s; s=(QNode *)malloc(sizeof(QNode)); s->data=x;//创建存放x的结点s if (lq==NULL)//原队为队空的情况 {lq=s; lq->next=lq;//构成循环单链表 } else//原队不空,结点s插到队尾,并由lq指向它 {s->next=lq->next; lq->next=s; lq=s;//lq指向结点s } } //-----出队运算算法----- int DeQueue(QNode *&lq,ElemType &x) {QNode *s; if (lq==NULL) return 0;//原队为队空的情况 if (lq->next==lq)//原队只有一个结点 {x=lq->data; free(lq); lq=NULL; } else//原队有两个或以上的结点,删除队头结点 {s=lq->next;//将结点lq之后的结点s删除 x=s->data; lq->next=s->next; free(s); } return 1; } //----取队头元素运算算法---- int GetHead(QNode *lq,ElemType &x) {if (lq==NULL) return 0;//原队为队空的情况 x=lq->next->data; return 1; } //----判断队空运算算法---- int QueueEmpty(QNode *lq) {if (lq==NULL) return 1;//队空返回1 else return 0;//队不空返回0 } 【例3.17】以下各种不带头结点的链表中最不适合用作链队的是。 A. 只带队首指针的非循环双链表B. 只带队首指针的循环双链表 C. 只带队尾指针的循环双链表D. 只带队尾指针的循环单链表 队列最基本的运算是进队和出队。链队的队头和队尾分别在链表的前、后端，即进队在链尾进行，出队在链首进行。 对于选项A的只带队首指针的非循环双链表，在末尾插入一个结点(进队)的时间复杂度为O(n)，其他选项的链表完成同样操作的时间复杂度均为O(1)，所以相比较而言，选项A的存储结构最不适合用作链队。本题答案为A。 3.2.4队列的应用示例 在较复杂的数据处理过程中，通常需要保存多个临时产生的数据，如果先产生的数据先进行处理，那么需要用队列来保存这些数据。下面通过一个典型示例说明队列的应用。 【例3.18】设计一个程序，反映病人到医院看病、排队看医生的过程。 (1) 设计存储结构。 病人排队看医生采用先到先看的方式，所以要用到一个队列。由于病人人数具有较大的不确定性，这里采用一个带头结点的单链表作为队列的存储结构。为了简单，病人通过其姓名来唯一标识。例如，有Smith、John和Mary三个病人依次排队的病人队列如图3.22所示。 图3.22病人队列 病人链队结点类型如下。 typedef struct {QType *front;//指向队头病人结点 QType *rear;//指向队尾病人结点 } LQueue;//病人链队类型 病人链队中的结点类型如下。 typedef struct Lnode {char data［10］;//存放患者姓名 struct Lnode *next;//指针域 } QType;//链队中结点类型 (2) 设计运算算法。 在病人队列设计好后，设计相关的基本运算算法，如队列初始化、进队和出队等，这些算法如下。 //---初始化队列运算算法--- void InitQueue(LQueue *&lq) {lq=(LQueue *)malloc(sizeof(LQueue)); lq->rear=lq->front=NULL;//初始时队头和队尾指针均为空 } //----销毁链队---- void DestroyQueue(LQueue *&lq) {QType *pre=lq->front,*p; if (pre!=NULL)//非队空的情况 {if (pre==lq->rear)//只有一个数据结点的情况 free(pre);//释放pre结点 else//有两个或多个数据结点的情况 {p=pre->next; while (p!=NULL) {free(pre);//释放pre结点 pre=p; p=p->next;//pre、p同步后移 } } free(pre);//释放尾结点 } free(lq);//释放链队结点 } //----进队运算算法---- void EnQueue(LQueue *&lq,char x［ ］) {QType *s; s=(QType *)malloc(sizeof(QType)); //创建新结点，插入链队的末尾 strcpy(s->data,x);s->next=NULL; if (lq->front==NULL)//原队为队空的情况 lq->rear=lq->front=s;//front和rear均指向s结点 else//原队不为队空的情况 {lq->rear->next=s;//将结点s链到队尾 lq->rear=s;//rear指向结点s } } //-----出队运算算法----- int DeQueue(LQueue *&lq,char x［ ］) {QType *p; if (lq->front==NULL)//原队为队空的情况 return 0; p=lq->front;//p指向队头结点 strcpy(x,p->data);//取队头元素值 if (lq->rear==lq->front)//若原队列中只有一个结点,删除后队列变空 lq->rear=lq->front=NULL; else//原队有两个或以上结点的情况 lq->front=lq->front->next; free(p); return 1; } //----判断队空运算算法---- int QueueEmpty(LQueue *lq) {if (lq->front==NULL) return 1;//队空返回1 else return 0;//队不空返回0 } //----输出队中所有元素的算法---- int DispQueue(LQueue *lq) {QType *p; if (QueueEmpty(lq)) return 0; //队空返回0 else {p=lq->front; while (p!=NULL) {printf("%s ",p->data); p=p->next; } printf("＼n"); return 1;//队不空返回1 } } (3) 设计主函数。 然后设计如下主函数通过简单的提示性菜单方式来操作各个功能。 int main() {int sel,flag=1; char name［10］; LQueue *lq;//定义一个病人队列 InitQueue(lq);//初始化病人队列 while (flag==1) //未下班时循环执行 {printf("1:排队 2:看医生 3:查看排队 0:下班 请选择:"); scanf("%d",&sel);//选择一项操作 switch(sel) { case 0://医生下班 if (!QueueEmpty(lq)) printf(">>请排队的患者明天就医＼n"); DestroyQueue(lq); flag=0; break; case 1://一个病人排队 printf(">>输入患者姓名:"); scanf("%s",name); EnQueue(lq,name); break; case 2://一个病人看医生 if (!DeQueue(lq,name)) printf(">>没有排队的患者＼n"); else printf(">>患者%s看医生＼n",name); break; case 3://查看目前病人排队情况 printf(">>排队患者:"); if (!DispQueue(lq)) printf(">>没有排队的患者＼n"); break; } } } (4) 执行结果。 本程序的一次执行结果如图3.23所示。 图3.23看病程序的一次执行结果 小结 (1) 栈和队列的共同点是，它们的数据元素都呈线性关系，且只允许在端点处插入和删除元素。 (2) 栈是一种“后进先出”或者“先进后出”的数据结构，只能在一端进行元素的插入和删除。 (3) 栈可以采用顺序栈和链栈两类存储结构。 (4) n个不同元素的进栈顺序和出栈顺序不一定相同。 (5) 在顺序栈中，通常用栈顶指针指向栈顶元素，栈顶指针类型为int类型。 (6) 在顺序栈中，进栈和出栈操作仅改变栈顶元素不涉及栈中其他元素的移动。 (7) 无论是顺序栈还是链栈，进栈和出栈运算的时间复杂度均为O(1)。 (8) 队列是一种“先进先出”或者“后进后出”的数据结构，只能从一端插入元素，另一端删除元素。 (9) 队列可以采用顺序队和链队两类存储结构。 (10) n个元素进队的顺序和出队顺序总是一致的。 (11) 顺序队中的元素个数可以由队头指针和队尾指针计算出来。 (12) 循环队列也是一种顺序队，是通过逻辑方法使其首尾相连，解决非循环队列的假溢出现象。 (13) 无论是顺序队还是链队，进队和出队运算的时间复杂度均为O(1)。 (14) 在算法设计中通常用栈或者队列保存临时数据，如果先保存的元素先处理，采用队列； 如果后保存的元素先处理，采用栈。 练习题 上机实验题 华为的专利 专利的质量与数量是企业创新能力和核心竞争能力的体现。据国家知识产权局知识产权发展研究中心公布的数据显示，在当前全球声明的21万余件5G标准专利中，中国声明的专利占比近40%，排名世界第一，其中华为公司5G标准专利族6500余项，占比14%，位居全球首位。在全球申请专利的约3.8万项6G技术中，中国以35%的占有率居首位，而其中大部分专利都是华为申请的。