第3章习题答案

第3章 栈与队列

习题3

1.名词解释：栈、队列、循环队列。

解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。

队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最后插入的元素最先删除，故栈也称先进先出表。最先入队的元素最先删除，故队列也称先进先出表。

用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。

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得到序列p1，p2，…，pn(它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形：存在着i

解：如果ipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这说明，对于i

4.当函数f递归调用自身时，函数f内定义的局部变量在函数f的2次调用期间是否占用同一数据区？为什么？

解：函数f递归调用自身时，函数f内定义的局部变量在函数f的2次调用期间不占用同一数据区。每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。

5.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值。 解：循环队列的数据结构略。 typedef struct{ ElemType *elem; int front;

1

第3章 栈与队列

int rear; }SqQueue,Q;

（1）初始状态: Q.front=Q.rear=0; （2）队列空: Q.front=Q.rear=0;

（3）队列满: Q.front=(Q.rear+1)%MAXSIZE;

6.设一个双端队列，元素进入该队列的次序为1，2，3，4.求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。

解：既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是：4，2，3，1。

7.简述以下算法的功能。 (1)void algo1(Stack S){ int i,n,A[255]; n=0;

while(!StackEmpty(S)){n++;Pop(S,A[n]);}; for(i=1;i<=n;i++)Push(S,A[i]); }

(2)void algo2(Stack S,int e){ Stack T;int d;

InitStack(T);

while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);} while(!StackEmpty(T)){Pop(T,d);Push(S,d);} }

(3)void algo3(Queue &Q){//栈和队列的元素类型均为int Stack S;int d;

InitStack(T);

while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);} while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);} }

解：（1）将栈中元素逆置。 （2）将栈中的0元素删除。 （3）将队列中元素逆置。

8.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中不含字符@，且序列2是序列1的逆序列。

解：

2

第3章 栈与队列

int IsReverse(){//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 SqStack s; char c,x; InitStack(s);

while((c=getchar())!='&')Push(s,c); while((c=getchar())!='@'){ }

if(!StackEmpty(s))return 0; return 1; }

9.在火车调度站的入口处有n节硬席或软席车厢(分别以H和S表示)等待调度，试写一算法，输出对这n节车厢进行调度的操作(即入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。

解：typedef char SS[MAX];

void Train_arrange(SS &train){//这里用字符串train表示火车,'H'表示硬席,'S'表示软席 SqStack s; char *p,*q,c; p=train; q=train; InitStack(s); while(*p){ }

while(!StackEmpty(s)){ } }

10.试写出求递归函数F(n)的递归算法，并消除递归：

Pop(s,c);

*(q++)=c;//把'H'接在后部

if(*p=='H')Push(s,*p);//把'H'存入栈中 else *(q++)=*p; //把'S'调到前部 p++;

if(StackEmpty(s))return 0; Pop(s,x); if(x!=c)return 0;

3

第3章 栈与队列

n?0?n?1 F(n)???n?F(n/2)n?0解：

int F_recursive(int n,int &s){//递归算法 if(n<0) return ERROR; if(n==0) s=n+1; else{ }

return OK; }//F_recursive typedef struct { ElemType a; ElemType b; }node;

typedef struct { node *data; int top;//栈顶指针 int stacksize; }SqStack;

void F_nonrecursive(int n,int &s){//非递归算法 SqStack T; node x,t; if(n<0) exit(0); if(n==0) s=n+1; else {

F_recursive(n/2,s); s=n*s;

InitStack(T); while(n!=0){

x.a=n;x.b=n/2; Push(T,x); n=x.b;

}//while s=1;

4