第3章栈和队列

3.1本章知识体系1. 知识结构图

本章的知识结构如图3.1所示。

图3.1第3章知识结构图

2. 基本知识点(1) 栈、队列和线性表的异同。(2) 顺序栈的基本运算算法设计。(3) 链栈的基本运算算法设计。(4) 顺序队的基本运算算法设计。(5) 环形队列和非环形队列的特点。(6) 链队的基本运算算法设计。(7) 利用栈/队列求解复杂的应用问题。3. 要点归纳(1) 栈和队列的共同点是它们的数据元素都呈线性关系，且只允许在端点处插入和删除元素。(2) 栈是一种“后进先出”的数据结构，只能在同一端进行元素的插入和删除。(3) 栈可以采用顺序栈和链栈两类存储结构。(4) n个不同元素的进栈顺序和出栈顺序不一定相同。(5) 在顺序栈中通常用栈顶指针指向当前栈顶的元素。(6) 在顺序栈中用数组data［0..MaxSize-1］存放栈中元素，只能将一端作为栈底，另一端作为栈顶，通常的做法是将data［0］端作为栈底，data［MaxSize-1］端作为栈顶。用户也可以将data［MaxSize-1］端作为栈底，data［0］端作为栈顶，但不能将中间位置作为栈底或者栈顶。(7) 初始时栈顶指针top设置为-1，栈空的条件为top=-1，栈满的条件为top=MaxSize-1，元素x的进栈操作是top ; data［top］=x，出栈操作是x=data［top］; top--。这是经典做法，但不是的方法，如果初始时top设置为0，可以设置栈空的条件为top=0，栈满的条件为top=MaxSize，元素x的进栈操作是data［top］=x; top ，出栈操作是top--; x=data［top］。(8) 在顺序栈或链栈中，进栈和出栈操作不涉及栈中元素的移动。(9) 在链栈中，由于每个结点是单独分配的，通常不考虑上溢出问题。(10) 无论是顺序栈还是链栈，进栈和出栈运算的时间复杂度均为O(1)。(11) 队列是一种“先进先出”的数据结构，只能从一端插入元素，从另一端删除元素。(12) 队列可以采用顺序队和链队两类存储结构。(13) n个元素进队的顺序和出队顺序总是一致的。(14) 在顺序队中的元素个数可以由队头指针和队尾指针计算出来。(15) 环形队列也是一种顺序队，是通过逻辑方法使其首尾相连的，解决非环形队列的假溢出现象。(16) 在环形队列中，队头指针f指向队头元素的前一个位置，队尾指针r指向队尾元素，这是一种经典做法，但不是的方法，也可以让队头指针f指向队头元素。(17) 无论是顺序队还是链队，进队和出队运算的时间复杂度均为O(1)。(18) 在实际应用中，一般栈和队列都是用来存放临时数据的，如果先保存的元素先处理，应该采用队列； 如果后保存的元素先处理，应该采用栈。

3.2教材中的练习题及参考答案1. 有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中以元素C、D出栈(即C及时个且D第二个出栈)的次序有哪几个？答： 要使C及时个且D第二个出栈，应是A进栈，B进栈，C进栈，C出栈，D进栈，D出栈，之后可以有以下几种情况： (1) B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE； (2) B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA； (3) E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。所以可能的次序有CDBAE、CDBEA、CDEBA。2. 在一个算法中需要建立多个栈(假设3个栈或以上)时可以选用以下3种方案之一，试问这些方案相比各有什么优缺点？(1) 分别用多个顺序存储空间建立多个独立的顺序栈。(2) 多个栈共享一个顺序存储空间。(3) 分别建立多个独立的链栈。答： (1) 优点是每个栈仅用一个顺序存储空间时操作简单； 缺点是分配空间小了容易产生溢出，分配空间大了容易造成浪费，各栈不能共享空间。(2) 优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出； 缺点是当一个栈满时要向左、右查询有无空闲单元，如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时要查询空闲单元、移动元素和修改栈底、栈顶指针，这一过程计算复杂且十分耗时。(3) 优点是多个链栈一般不考虑栈的溢出； 缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。3. 在以下几种存储结构中哪个最适合用作链栈？(1) 带头结点的单链表。(2) 不带头结点的循环单链表。(3) 带头结点的双链表。答： 栈中元素之间的逻辑关系属线性关系，可以采用单链表、循环单链表和双链表之一来存储，而栈的主要运算是进栈和出栈。当采用(1)时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。当采用(2)时，前端作为栈顶，当进栈和出栈时首结点都发生变化，还需要找到尾结点，通过修改其next域使其变为循环单链表，算法的时间复杂度为O(n)。当采用(3)时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。但单链表和双链表相比，其存储密度更高，所以本题中最适合用作链栈的是带头结点的单链表。4. 简述以下算法的功能(假设ElemType为int类型)。

void fun(ElemType a［］,int n)

{int i;ElemType e;

SqStack st1,st2;

InitStack(st1);

InitStack(st2);

for (i=0;i

if (a［i］%2==1)

Push(st1,a［i］);

else

Push(st2,a［i］);

i=0;

while (!StackEmpty(st1))

{Pop(st1,e);

a［i ］=e;

}

while (!StackEmpty(st2))

{Pop(st2,e);

a［i ］=e;

}

DestroyStack(st1);

DestroyStack(st2);

}

答： 算法的执行步骤如下。(1) 扫描数组a，将所有奇数进到st1栈中，将所有偶数进到st2栈中。(2) 先将st1的所有元素(奇数元素)退栈，放到数组a中并覆盖原有位置的元素； 再将st2的所有元素(偶数元素)退栈，放到数组a中并覆盖原有位置的元素。(3) 销毁两个栈st1和st2。所以本算法的功能是利用两个栈将数组a中的所有奇数元素放到所有偶数元素的前面。例如ElemType a［］={1,2,3,4,5,6}，执行算法后数组a改变为{5,3,1,6,4,2}。5. 简述以下算法的功能(顺序栈的元素类型为ElemType)。

void fun(SqStack &st,ElemType x)

{SqStack tmps;

ElemType e;

InitStack(tmps);

while(!StackEmpty(st))

{Pop(st,e);

if(e!=x) Push(tmps,d);

}

while (!StackEmpty(tmps))

{Pop(tmps,e);

Push(st,e);

}

DestroyStack(tmps);

}

答： 算法的执行步骤如下。(1) 建立一个临时栈tmps并初始化。(2) 退栈st中的所有元素，将不为x的元素进栈到tmps中。(3) 退栈tmps中的所有元素，并进栈到st中。(4) 销毁栈tmps。所以本算法的功能是如果栈st中存在元素x，将其从栈中清除。例如，st栈中从栈底到栈顶为a、b、c、d、e，执行算法fun(st，'c')后，st栈中从栈底到栈顶为a、b、d、e。6. 简述以下算法的功能(栈st和队列qu的元素类型均为ElemType)。

bool fun(SqQueue &qu,int i)

{ElemType e;

int j=1;

int n=(qu->rear-qu->front MaxSize)%MaxSize;

if (jn) return false;

for (j=1;j

{deQueue(qu,e);

if (j!=i)

enQueue(qu,e);

}

return true;

}

答： 算法的执行步骤如下。(1) 求出队列qu中的元素个数n，参数i错误时返回假。(2) qu出队共计n次，除了第i个出队的元素以外，其他出队的元素立即进队。(3) 返回真。所以本算法的功能是删除qu中从队头开始的第i个元素。例如，qu中从队头到队尾的元素是a、b、c、d、e，执行算法fun(qu，2)后，qu中从队头到队尾的元素改变为a、c、d、e。7. 什么是环形队列？采用什么方法实现环形队列？答： 在用数组表示队列时把数组看成是一个环形的，即令数组中的及时个元素紧跟在最末一个单元之后就形成了一个环形队列。环形队列解决了非环形队列中出现的“假溢出”现象。通常采用逻辑上求余数的方法来实现环形队列，假设数组的大小为n，当元素下标i增1时采用i=(i 1)%n来实现。8. 环形队列一定优于非环形队列吗？在什么情况下使用非环形队列？答： 队列主要用于保存中间数据，而且保存的数据满足先产生先处理的特点。非环形队列可能存在数据假溢出现象，即队列中还有空间，可是队满的条件却成立了，为此改为环形队列，这样克服了假溢出现象。但并不能说环形队列一定优于非环形队列，因为环形队列中出队元素的空间可能被后来进队的元素覆盖，如果算法要求在队列操作结束后利用进队的所有元素实现某种功能，这样环形队列就不适合了，在这种情况下需要使用非环形队列，例如利用非环形队列求解迷宫路径就是这种情况。9. 假设以I和O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。(1) 在下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO(2) 通过对(1)的分析，设计一个算法判定所给的操作序列是否合法，若合法返回真，否则返回假(假设被判定的操作序列已存入一维数组中)。解： (1) 选项A、D均合法，而选项B、C不合法。因为在选项B中先进栈一次，立即出栈3次，这会造成栈下溢。在选项C中共进栈5次，出栈3次，栈的终态不为空。(2) 本题使用一个链栈来判断操作序列是否合法，其中str为存放操作序列的字符数组，n为该数组的字符个数(这里的ElemType类型设定为char)。对应的算法如下：

bool judge(char str［］,int n)

{int i=0; ElemType x;

LinkStNode ls;

bool flag=true;

InitStack(ls);

while (i

{if (str［i］=='I')//进栈

Push(ls,str［i］);

else if (str［i］=='O')//出栈

{if (StackEmpty(ls))

flag=false;//栈空时

else

Pop(ls,x);

}

else

flag=false;//其他值无效

i ;

}

if (!StackEmpty(ls)) flag=false;

DestroyStack(ls);

return flag;

}

10. 假设表达式中允许包含圆括号、方括号和大括号3种括号，编写一个算法判断表达式中的括号是否正确配对。解： 设置一个栈st，扫描表达式exp，当遇到'('、'［'或'{'时将其进栈； 当遇到')'时，若栈顶是'('，则继续处理，否则以不配对返回假； 当遇到'］'时，若栈顶是'［'，则继续处理，否则以不配对返回假； 当遇到'}'时，若栈顶是'{'，则继续处理，否则以不配对返回假。在exp扫描完毕后，若栈不空，则以不配对返回假； 否则以括号配对返回真。本题的算法如下：

bool Match(char exp［］,int n)

{LinkStNode ls;

InitStack(ls);

int i=0;

ElemType e;

bool flag=true;

while (i

{if (exp［i］=='(' | exp［i］=='［' | exp［i］=='{')

Push(ls,exp［i］);//遇到'('、'［'或'{',将其进栈

if (exp［i］==')')//遇到')',若栈顶是'(',继续处理,否则以不配对返回

{if (GetTop(ls,e))

{if (e=='(') Pop(ls,e);

else flag=false;

}

else flag=false;

}

if (exp［i］=='］')//遇到'］',若栈顶是'［',继续处理,否则以不配对返回

{if (GetTop(ls,e))

{if (e=='［') Pop(ls,e);

else flag=false;

}

else flag=false;

}

if (exp［i］=='}')//遇到'}',若栈顶是'{',继续处理,否则以不配对返回

{if (GetTop(ls,e))

{if (e=='{') Pop(ls,e);

else flag=false;

}

else flag=false;

}

i ;

}

if (!StackEmpty(ls)) flag=false;//若栈不空,则不配对

DestroyStack(ls);

return flag;

}

11. 设从键盘输入一序列的字符a1、a2、…、an。设计一个算法实现这样的功能： 若ai为数字字符，ai进队； 若ai为小写字母，将队首元素出队； 若ai为其他字符，表示输入结束。要求使用环形队列。解： 先建立一个环形队列qu，用while循环接收用户的输入，若输入数字字符，将其进队； 若输入小写字母，出队一个元素，并输出它； 若为其他字符，则退出循环。本题的算法如下：

void fun()

{ElemType a,e;

SqQueue qu;//定义队列指针

InitQueue(qu);

while (true)

{printf("输入a:");

scanf("%s",&a);

if (a>='0' && a

{if (!enQueue(qu,a))

printf("队列满,不能进队\n");

}

else if (a>='a' && a

{if (!deQueue(qu,e))

printf("队列空,不能出队\n");

else

printf("出队元素:%c\n",e);

}

else break;//为其他字符

}

DestroyQueue(qu);

}

12. 设计一个算法，将一个环形队列(容量为n，元素下标从0到n-1)的元素倒置。例如，图3.2(a)为倒置前的队列(n=10)，图3.2(b)为倒置后的队列。

图3.2一个环形队列倒置前后的状态

解： 使用一个临时栈st，先将qu队列中的所有元素出队并将其进栈st，直到队列空为止。然后初始化队列qu(队列清空)，再出栈st的所有元素并将其进队qu，销毁栈st。对应的算法如下：

void Reverse(SqQueue &qu)

{ElemType e;

SqStack st;

InitStack(st);

while (!QueueEmpty(qu))//队不空时出队并进栈

{deQueue(qu,e);

Push(st,e);

}

InitQueue(qu);//队列初始化

while (!StackEmpty(st))//栈不空时出栈并将元素入队

{Pop(st,e);

enQueue(qu,e);

}

DestroyStack(st);

}

13. 编写一个程序，输入n(由用户输入)个10以内的数，每输入i(0≤i≤9)就把它插入到第i号队列中，把10个队中的非空队列按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。解： 建立一个队头指针数组quh和队尾指针数组qut，quh［i］和qut［i］表示i号(0≤i≤9)队列的队头和队尾，先将它们的所有元素置为NULL。对于输入的x，采用尾插法将其链到x号队列中。然后按0~9编号的顺序把这些队列中的结点构成一个不带头结点的单链表，其首结点指针为head。输出单链表head的所有结点值并释放所有结点。对应的程序如下：

#include

#include

#define MAXQNode 10//队列的个数

typedef struct node

{int data;

struct node next;

} QNode;

void Insert(QNode quh［］,QNode qut［］,int x)//将x插入到相应队列中

{QNode s;

s=(QNode )malloc(sizeof(QNode));//创建一个结点s

s->data=x; s->next=NULL;

if (quh［x］==NULL)//x号队列为空队时

{quh［x］=s;

qut［x］=s;

}

else//x号队列不空队时

{qut［x］->next=s;//将s结点链到qut［x］所指的结点之后

qut［x］=s;//让qut［x］仍指向尾结点

}

}

void Create(QNode quh［］,QNode qut［］)//根据用户的输入创建队列

{int n,x,i;

printf("n:");

scanf("%d",&n);

for (i=0;i

{do

{printf("输入第%d个数:",i 1);

scanf("%d",&x);

} while (x10);

Insert(quh,qut,x);

}

}

void DestroyList(QNode &head)//释放单链表

{QNode pre=head,p=pre->next;

while (p!=NULL)

{

free(pre);

pre=p; p=p->next;

}

free(pre);

}

void DispList(QNode head)//输出单链表的所有结点值

{printf("\n输出所有元素:");

while (head!=NULL)

{printf("%d ",head->data);

head=head->next;

}

printf("\n");

}

QNode Link(QNode quh［］,QNode qut［］)//将非空队列链接起来并输出

{QNode head=NULL,tail;//总链表的首结点指针和尾结点指针

int i;

for (i=0;i

if (quh［i］!=NULL)//i号队列不空

{if (head==NULL)//若i号队列为及时个非空队列

{head=quh［i］;

tail=qut［i］;

}

else//若i号队列不是及时个非空队列

{tail->next=quh［i］;

tail=qut［i］;

}

}

tail->next=NULL;

return head;

}

int main()

{int i;

QNode head;

QNode quh［MAXQNode］,qut［MAXQNode］;//各队列的队头quh和队尾指针qut

for (i=0;i

quh［i］=qut［i］=NULL;//置初值空

Create(quh,qut);//建立队列

head=Link(quh,qut);//链接各队列产生单链表

DispList(head);//输出单链表

DestroyList(head);//销毁单链表

return 1;

}

3.3补充练习题及参考答案3.3.1单项选择题

1. 以下数据结构中元素之间为线性关系的是。

A. 栈B. 队列C. 线性表D. 以上都是答： D。2. 栈和队列的共同点是。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有其同点答： 栈和队列都是受限线性表，所谓“受限”指的是在端点处插入和删除元素，所以本题的答案为C。3. 经过以下栈运算后x的值是。

InitStack(s);Push(s，a);Push(s，b);Pop(s，x);GetTop(s，x);

A. aB. bC. 1D. 0答： A。4. 经过以下栈运算后StackEmpty(s)的值是。

InitStack(s);Push(s，a);Push(s，b);Pop(s，x);Pop(s，y)

A. aB