2024年4月11日发(作者：)

第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

得到序列

p

1

，

p

2

，…，

p

n

(它是输入序列的一个全排

列)，则在输出序列中不可能出现下列情形：存在着

i

<

j

<

k

，使得

p

j

<

p

k

<

p

i

。

解：如果

i

<

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

的输出序列。

4.当函数

f

递归调用自身时，函数

f

内定义的局部变量在函数

f

的2次调用期间是否占用同一数据

区？为什么？

解：函数

f

递归调用自身时，函数

f

内定义的局部变量在函数

f

的2次调用期间不占用同一数据区。

每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。

5.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值。

解：循环队列的数据结构略。

typedef struct{

ElemType *elem;

int front;

1

第3章 栈与队列

int rear;

}SqQueue,Q;

（1）初始状态: ==0;

（2）队列空: ==0;

（3）队列满: =(+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