第3章++栈和队列+课后习题答案

第三章栈和队列作业1、若按教材P44页图3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？（2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到？（写出进栈和出栈的栈操作序列）。

123、132、213、231、321输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

2、试证明：若借助栈由输入序列1、2……n得到的输出序列为p1、p2……p n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着，i〈j〈k使p j<p k<p i如果i<j，则对于p i<p j情况，说明p i在p j入栈前先出栈。

而对于p i>p j的情况，则说明要将p j压到p i之上，也就是在p j出栈之后p i才能出栈。

这就说明，对于i<j<k，不可能出现p j<p k<p i的输出序列。

换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。

3、按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节3--2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D-E ↑F4、试编写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列，序列1和序列2中不包含字符‘&’，序列1是序列2的逆序列。

习题三栈和队列一单项选择题1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/22．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。

A 可能是2B 一定是2C 可能是1D 一定是13. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 64.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（）A.2B. 3C. 5D.65. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。

A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD. top[1]=top[2]6. 执行完下列语句段后，i值为：（）int f(int x){ return ((x>0) ? x* f(x-1):2);}int i ;i =f(f(1));A．2 B. 4 C. 8 D. 无限递归7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。

A. 3,2,4,1,1；(*^(+*-B. 3,2,8；(*^-C. 3,2,4,2,2；(*^(-D. 3,2,8；(*^(-8. 用链接方式存储的队列，在进行删除运算时（）。

第三章栈和队列(参考答案)// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 11 32 4 23 14 3 4 2 11 3 42 234 11 4 32 2 43 1设入栈序列元素数为n，则可能的出栈序列数为C2n n=(1/n+1)*(2n!/(n!)2)3.2 证明：由j<k和p j<p k说明p j在p k之前出栈，即在k未进栈之前p j已出栈，之后k进栈，然后p k出栈；由j<k和p j>p k说明p j在p k之后出栈，即p j被p k压在下面，后进先出。

由以上两条，不可能存在i<j<k使p j<p k<p i。

也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。

3.3 void sympthy(linklist *head, stack *s)//判断长为n的字符串是否中心对称{ int i=1; linklist *p=head->next;while (i<=n/2) // 前一半字符进栈{ push(s,p->data); p=p->next; }if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点while (p && p->data==pop(s)) p=p->next;if (p==null) printf(“链表中心对称”)；else printf(“链表不是中心对称”)；} // 算法结束3.4int match()//从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;//初始化栈sscanf(“%c”,&ch);while (ch!=’#’) //’#’是表达式输入结束符号switch (ch){ case ’(’: push(s,ch); break;case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}pop(s);}if (!empty(s)) printf(“括号不配对”);else printf(“括号配对”);} // 算法结束3.5typedef struct // 两栈共享一向量空间{ ElemType v[m]; // 栈可用空间0—m-1int top[2] // 栈顶指针}twostack;int push(twostack *s,int i, ElemType x)// 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，// 本算法是入栈操作{ if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满else {switch (i){case 0: s->v[++(s->top)]=x; break;case 1: s->v[--(s->top)]=x; break;default: printf(“栈编号输入错误”); return(0);}return(1); // 入栈成功}} // 算法结束ElemType pop(twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作{ ElemType x;if (i!=0 && i!=1) return(0);// 栈编号错误else {switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top--];break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top++]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 退栈成功}} // 算法结束ElemType top (twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作{ ElemType x;switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top]; break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 取栈顶元素成功} // 算法结束3．6void Ackerman(int m,int n)// Ackerman 函数的递归算法{ if (m==0) return(n+1);else if (m!=0 && n==0) return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1))} // 算法结束3．7(1) linklist *init(linklist *q)// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出q->next=q;return (q);} // 算法结束(2) linklist *enqueue(linklist *q，ElemType x)// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出s->next=q->next; // 将元素结点s入队列q->next=s;q=s; // 修改队尾指针return (q);} // 算法结束(3) linklist *delqueue(linklist *q)//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法{ if (q==q->next) return (null); // 判断队列是否为空else {linklist *s=q->next->next; // s指向出队元素if (s==q) q=q->next; // 若队列中只一个元素，置空队列else q->next->next=s->next;// 修改队头元素指针free (s); // 释放出队结点}return (q);} // 算法结束。

习题31.名词解释：栈、队列、循环队列。

解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。

最后插入的元素最先删除，故栈也称后进先出表。

队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。

最后插入的元素最先删除，故栈也称先进先出表。

最先入队的元素最先删除，故队列也称先进先出表。

用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。

循环队列是解决“假溢出”的一种方法。

通常把一维数组看成首尾相接。

在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。

2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。

解：输入序列为1，2，3，4，5，6，不能得到4，3，5，6，1，2，其理由是：输出序列最后两个元素是1，2，前面四个元素（4，3，5，6）得到后，栈中元素剩下1，2，且2在栈顶，栈底元素1不可能在栈顶元素2出栈之前出栈。

得到序列1，3，5，4，2，6的过程是：1入栈并出栈；然后2和3依次入栈，3出栈，部分输出序列是1，3；紧接着4和5入栈，5，4和2依次出栈，此时输出序列为1，3，5，4，2；最后6入栈并出栈，得到最终结果序列是1，3，5，4，2，6。

3.试证明：若借助栈由输入序列1，2，…，n 得到序列1p ，2p ，…，n p (它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形：存在着i <j <k ，使得j p <k p <i p 。

解：如果i <j ，说明i p 在j p 入栈前先出栈。

而对于i p >j p 的情况，则说明要将j p 压到i p 之上，也就是在j p 出栈之后i p 才能出栈。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：第3章作业参考答案1.1,4,3,5,2)能，IOIIIOOIOO；(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。

*若借助栈由输入序列1,2, … , n得到输出序列为p1, p2, …, p n，则在输出序列中不可能出现这样的情形：存在着i<j<k使p j<p k<p i。

2. 借助栈T，删除栈S中元素值为k的元素。

4.//定义双向栈类template <class ElemType>//声明一个类模板class DSqStack{public: //双向栈类的各成员函数DSqStack(int m = 20XXXX0);~DSqStack();bool Empty(int i) const;ElemType & Top(int i) const;void Push(const ElemType &e,int i);void Pop(int i);private: //双向栈类的数据成员ElemType *base; //基地址指针int top[2]; //栈顶指针int size; //向量空间大小};//构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template <class ElemType>DSqStack <ElemType>::DSqStack(int m){top[0] = -1;top[1] = m;base = new ElemType[m];size = m;}//DSqStack//析构函数，将栈结构销毁。

template <class ElemType>DSqStack <ElemType>::~DSqStack(){if (base != NULL) delete[] base;}//~SqStack//判栈是否为空，若为空，则返回true，否则返回false。

一、选择题一、选择题1、栈中存取数据的原则（）、栈中存取数据的原则（）A 、先进先出B 、先进后出C 、后进后出D 、随意进出、随意进出2、队列中存取数据的原则（）、队列中存取数据的原则（） A 、先进先出 B 、后进先出 C 、先进后出 D 、随意进出、随意进出3、插入和删除只能在一端进行的线性表，称为（）、插入和删除只能在一端进行的线性表，称为（）A 、队列B 、循环队列C 、栈D 、循环栈、循环栈4、在栈中，出栈操作的时间复杂度为（）、在栈中，出栈操作的时间复杂度为（）A 、O （1）B 、O （log 2n ）C 、O （n ）D 、O （n 2）5、设长度为n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）（） A 、O （1） B 、O （log 2n ） C 、O （n ） D 、O （n 2）6、设长度为n 的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（）（） A 、O （1） B 、O （log 2n ） C 、O （n ） D 、O （n 2）7、一个线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）是（） A 、110 B 、108 C 、100 D 、1208、一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是（），则栈的不可能的输出序列是（）A 、edcbaB 、decbaC 、dceabD 、abcde9、若已知一个栈的入栈序列是1，2，3，……，n ，其输出序列是p1,p2,p3,……,pn ，若p1=n ，则pi 为（）为（）A 、iB 、n=iC 、n-i+1D 、不确定、不确定10、判断一个栈ST （最多元素m0）为空的条件是（））为空的条件是（）A 、ST->top==0B 、ST->top==-1C 、ST->top!=m0D 、ST->top==m0 11、判断一个栈ST （最多元素m0）为满的条件是（））为满的条件是（）A 、ST->top!=0B 、ST->top==0C 、ST->top!=m0D 、ST->top==m0 12、判断一个循环队列QU （最多元素为m0）为空的条件是（））为空的条件是（） A 、QU.front==QU.rear B 、QU.front!=QU.rearC 、QU.front==(QU.rear+1)%m0D 、QU.front!=(QU.rear+1)%m013、判断一个循环队列QU （最多元素为m0）为满的条件是（））为满的条件是（）A 、QU.front==QU.rearB 、QU.front!=QU.rearC 、QU.front==(QU.rear+1)%m0D 、QU.front!=(QU.rear+1)%m0 14、循环队列用数组存放其元素值A[0，m-1]，已知其头尾指针分别是rear 和front ，则当前队列的元素个数是（）队列的元素个数是（）A 、(rear-front+m)%mB 、rear-front+1C 、rear-front-1D 、rear-front 15、栈和队列的共同特点是（）、栈和队列的共同特点是（）A 、都是先进后出B 、都是先进先出、都是先进先出C 、只允许在端点处插入和删除D 、没有共同点、没有共同点二、填空题二、填空题1、设长度为n 的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（O(N)）和（O(1)）；若又设尾指针，则入队和出队操作的时间复杂度分别为（O(1)）和（O(1)）。

习题答案1.填空题（1）栈（2）队列（3）后进先出（4）先进先出2.选择题（1）A （2）C （3）D （4）D、A （5）C （6）B3.思考题（1）栈是一种运算受限制的线性表，其只允许在表的一端进行插入和删除操作，俗称堆栈。

允许进行操作的一端称为“栈顶”，而另一个固定端称为“栈底”，栈中的数据在进行入栈和出栈时，遵循后进先出的原则。

队列同样是一种运算受限制的线性表，是限制在两端进行插入和删除操作的线性表。

允许进行插入操作的一端称为“队尾”，而允许进行删除操作的一端称为“队头”，队列中的数据在进行入队和出队时，遵循先进先出的原则。

4.编程题（1）//入栈//参数1为栈顶指针（头结点指针），参数2为插入的数据int linkstack_push(linkstack_t *s, datatype_t value){linkstack_t *temp;//使用malloc函数为新插入的结点申请内存空间temp = (linkstack_t *)malloc(sizeof(linkstack_t));//为新插入的结点赋值temp->data = value;//用头插法实现入栈temp->next = s->next;s->next = temp;return 0;}//判断栈是否为空int linkstack_empty(linkstack_t *s){return s->next == NULL ? 1 : 0; //判断下一个结点是否为空}//出栈datatype_t linkstack_pop(linkstack_t *s){linkstack_t *temp;datatype_t value;if(linkstack_empty(s)){printf("linkstack empty\n");return -1;}//头删法表示出栈，后入先出temp = s->next;s->next = temp->next;//保存出栈的数据value = temp->data;//释放出栈的结点的内存空间free(temp);temp = NULL;//返回出栈的数据return value;}（2）//入队//参数1为存放队列头尾结点指针的结构体地址，参数2为新入队的数据int linkqueue_enter(linkqueue_t *lq, datatype_t value){ linknode_t *temp;//使用malloc函数为头结点申请内存空间temp = (linknode_t *)malloc(sizeof(linknode_t));//采用尾插法的设计思想temp->data = value; //为新结点赋值temp->next = NULL; //将新结点的指针指向NULLlq->rear->next = temp; //入队，将新结点加入队列尾部lq->rear = temp; //移动rear指针，指向新加入的结点 return 0;}//判断队列是否为空int linkqueue_empty(linkqueue_t *lq){//当front与rear指向同一个结点时，判断队列为空return lq->front == lq->rear ? 1 : 0;}//出队//从头结点开始删除，包括头结点datatype_t linkqueue_out(linkqueue_t *lq){linknode_t *temp;datatype_t value;if(linkqueue_empty(lq)){printf("linkqueue empty\n");return -1;}temp = lq->front; //获取删除结点//移动front指针到下一个结点lq->front = lq->front->next;//获取下一个结点的数据value = lq->front->data;free(temp); //释放需要删除结点的内存空间 temp = NULL; //避免出现野指针//返回结点数据return value;}。

第3章栈和队列习题参考答案第3章栈和队列一、基础知识题3.1有五个数依次进栈：1，2，3，4，5。

在各种出栈的序列中，以3，4先出的序列有哪几个。

（３在４之前出栈）。

【解答】34215 ，34251，345213.2铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。

【解答】输入序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？【解答】2和43.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？【解答】43.5循环队列的优点是什么，如何判断“空”和“满”。