栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表不相同的两类重要的抽象数据类型。本章除了讨论栈和队列的定义、表示方法和实现外，还将给出一些应用的例子。

3.1 栈和队列的定义和特点

3.1.1　栈的定义和特点

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。

假设栈S = (a1, a2, …, an)，则称a1为栈底元素，an为栈顶元素。栈中元素按a1, a2, …, an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图3.1（a）所示。因此，栈又称为后进先出（Last In First Out，LIFO）的线性表，它的这个特点可用图3.1（b）所示的铁路调度站形象地表示。

在日常生活中，还有很多类似栈的例子。例如，洗干净的盘子总是逐个往上叠放在已经洗好的盘子上面，而用时从上往下逐个取用。栈的操作特点正是上述实际应用的抽象。在程序设计中，如果需要按照保存数据时相反的顺序来使用数据，则可以利用栈来实现。

3.1.2　队列的定义和特点

和栈相反，队列（queue）是一种先进先出（First In First Out，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾（rear），允许删除的一端则称为队头（front）。假设队列为q = (a1, a2,…, an)，那么，a1就是队头元素，an则是队尾元素。队列中的元素是按照a1, a2,…, an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a1, a2,…, an − 1都离开队列之后，an才能退出队列。图3.2所示为队列的示意图。

队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出做输出操作。凡是申请输出的作业都从队尾进入队列。

3.2 案例引入

案例3.1：数制的转换。

十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：

N = (N div d) × d + N mod d（其中，div为整除运算，mod为求余运算）

假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。上述计算过程是从低位到高位顺序产生八进制数的各个数位；而输出过程应从高位到低位进行，恰好和计算过程相反，因而我们可以使用栈来解决这个问题。在计算过程中依次将得到的余数压入栈中，计算完毕后，再依次弹出栈中的余数就是数制转换的结果。

案例3.2：括号匹配的检验。

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［(［］［］)］等为正确的格式，［（］或（［（））或（（）］）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，显然第二个括号的期待急迫性高于第一个括号，此时第一个括号“［”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号“）”的出现。类似地，因等来的是第三个括号“［”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号。在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依次类推。可见，这个处理过程恰与栈的特点相吻合。每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。

案例3.3：表达式求值。

表达式求值是程序设计语言编译中的一个最基本问题，其实现是栈应用的又一个典型例子。“算符优先法”，是一种简单直观、广为使用的表达式求值算法。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。算符优先法就是根据算术四则运算规则确定的运算优先关系，实现对表达式的编译或解释执行的。

在表达式计算中先出现的运算符不一定先运算，具体运算顺序是需要通过运算符优先关系的比较，确定合适的运算时机，而运算时机的确定是可以借助栈来完成的。将扫描到的不能进行运算的运算数和运算符先分别压入运算数栈和运算符栈中，在条件满足时再分别从栈中弹出进行运算。

上述3个应用实例都是借助栈的后进先出的特性来处理问题的，在日常生活中，符合先进先出特性的应用更为常见。

案例3.4：舞伴问题。

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

先入队的男士或女士应先出队配成舞伴，因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构。

从上面的应用案例可以看出，不论是借助栈还是队列来解决问题，最基本的操作都是“入”和“出”。对于栈，在栈顶插入元素的操称作“入栈”，删除栈顶元素的操作称作“出栈”；对于队列，在队尾插入元素的操称作“入队”，在队头删除元素的操称作“出队”。和线性表一样，栈和队列的存储结构也包括顺序和链式两种。

本章后续章节将依次给出不同存储结构表示的栈和队列的基本操作，并介绍栈的一个非常重要的应用--在程序设计语言中来实现递归，借助栈的基本操作，读者可以深刻理解递归的处理机制。本章最后将利用栈和队列给出上述四个案例的具体实现。

3.3 栈的表示和操作的实现

3.3.1　栈的类型定义

栈的基本操作除了入栈和出栈外，还有栈的初始化、栈空的判定，以及取栈顶元素等。下面给出栈的抽象数据类型定义：

ADT Stack｛

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系：R={＜ai-1,ai＞|ai-1,ai∈D,i=2,…,n｝

约定an端为栈顶，a1端为栈底。

基本操作：

InitStack(&S)

操作结果：构造一个空栈S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：栈S被销毁。

ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈。

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回true，否则返回false。

StackLength(S)

初始条件：栈S已存在。

操作结果：返回S的元素个数，即栈的长度。

GetTop(S)

初始条件：栈S已存在且非空。

操作结果：返回S的栈顶元素，不修改栈顶指针。

Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

StackTraverse(S)

初始条件：栈S已存在且非空。

操作结果：从栈底到栈顶依次对S的每个数据元素进行访问。

}ADT Stack

本书在以后各章中引用的栈大多为如上定义的数据类型，栈的数据元素类型在应用程序内定义。

和线性表类似，栈也有两种存储表示方法，分别称为顺序栈和链栈。

3.3.2　顺序栈的表示和实现

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常习惯的做法是：以top = 0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C语言作描述语言时，如此设定会带来很大不便，因此另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时，表示空栈。

图 3.3 所示为顺序栈中数据元素和栈指针之间的对应关系。

由于顺序栈的插入和删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多，以下给出顺序栈部分操作的实现。

1．初始化

顺序栈的初始化操作就是为顺序栈动态分配一个预定义大小的数组空间。

算法3.1　顺序栈的初始化

【算法步骤】

① 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
② 栈顶指针top初始为base，表示栈为空。
③ stacksize置为栈的最大容量MAXSIZE

【算法描述】

Status InitStack(SqStack &S)
{//构造一个空栈S
S.base=new SElemType[MAXSIZE]； //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base; //top初始为base，空栈
S.stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
return OK;
}

2．入栈

入栈操作是指在栈顶插入一个新的元素。

算法3.2　顺序栈的入栈

【算法步骤】

① 判断栈是否满，若满则返回ERROR。
② 将新元素压入栈顶，栈顶指针加1。

【算法描述】

Status Push(SqStack &S，SElemType e)
{//插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize) return ERROR； //栈满
*S.top++=e； //元素e压入栈顶，栈顶指针加1
return OK；
}

3．出栈

出栈操作是将栈顶元素删除。

算法3.3　顺序栈的出栈

【算法步骤】

① 判断栈是否空，若空则返回ERROR。
② 栈顶指针减1，栈顶元素出栈。

【算法描述】

Status Pop(SqStack &S,SElemType &e)
{删除S的栈顶元素，用e返回其值
if(S.top==S.base) return ERROR; //栈空
e=*--S.top; //栈顶指针减1，将栈顶元素赋给e
return OK;
}

4．取栈顶元素

当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。

算法3.4　取顺序栈的栈顶元素

【算法描述】

SElemType GetTop(SqStack S)
{//返回S的栈顶元素，不修改栈顶指针
if(S.top！=S.base) //栈非空
return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
}

由于顺序栈和顺序表一样，受到最大空间容量的限制，虽然可以在“满员”时重新分配空间扩大容量，但工作量较大，应该尽量避免。因此在应用程序无法预先估计栈可能达到的最大容量时，还是应该使用下面介绍的链栈。

3.3.3　链栈的表示和实现

链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示，如图3.4所示。链栈的结点结构与单链表的结构相同，在此用StackNode表示，定义如下：

//- - - - - 链栈的存储结构- - - - -
typedef struct StackNode
{
ElemType data;
struct StackNode next;
}StackNode,LinkStack;

由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便附加一个头结点。

下面给出链栈部分操作的实现。

1．初始化

链栈的初始化操作就是构造一个空栈，因为没必要设头结点，所以直接将栈顶指针置空即可。

算法3.5　链栈的初始化

【算法描述】

Status InitStack(LinkStack &S)
{//构造一个空栈S，栈顶指针置空
S=NULL;
return OK;
}

2．入栈

和顺序栈的入栈操作不同的是，链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间，如图3.5所示。

算法3.6　链栈的入栈

【算法步骤】

① 为入栈元素e分配空间，用指针p指向。
② 将新结点数据域置为e。
③ 将新结点插入栈顶。
④ 修改栈顶指针为p。

【算法描述】

Status Push(LinkStack &S, SElemType e)
{//在栈顶插入元素e
p=new StackNode; //生成新结点
p->data=e; //将新结点数据域置为e
p->next=S; //将新结点插入栈顶
S=p; //修改栈顶指针为p
return OK;
}

3．出栈

和顺序栈一样，链栈在出栈前也需要判断栈是否为空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间，如图3.6所示。

算法3.7　链栈的出栈

【算法步骤】

① 判断栈是否为空，若空则返回ERROR。
② 将栈顶元素赋给e。
③ 临时保存栈顶元素的空间，以备释放。
④ 修改栈顶指针，指向新的栈顶元素。
⑤ 释放原栈顶元素的空间。

【算法描述】

Status Pop(LinkStack &S,SElemType &e)
{//删除S的栈顶元素，用e返回其值
if(S==NULL) return ERROR; //栈空
e=S->data; //将栈顶元素赋给e
p=S; //用p临时保存栈顶元素空间，以备释放
S=S->next; //修改栈顶指针
delete p; //释放原栈顶元素的空间
return OK;
}

4．取栈顶元素

与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变。

算法3.8　取链栈的栈顶元素

【算法描述】

SElemType GetTop(LinkStack S)
{//返回S的栈顶元素，不修改栈顶指针
if(S！=NULL) //栈非空
return S->data; //返回栈顶元素的值，栈顶指针不变
}

3.4 栈与递归

栈有一个重要应用是在程序设计语言中实现递归。递归是算法设计中最常用的手段，它通常把一个大型复杂问题的描述和求解变得简洁和清晰。因此递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归方法更加合适。为使读者增强理解和设计递归算法的能力，本节将介绍栈在递归算法的内部实现中所起的作用。

3.4.1　采用递归算法解决的问题

所谓递归是指，若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。在以下三种情况下，常常使用递归的方法。

1．定义是递归的

有很多数学函数是递归定义的。

采取“分治法”进行递归求解的问题需要满足以下三个条件。

（1）能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，并且这些处理对象更小且变化有规律。
（2）可以通过上述转化而使问题简化。
（3）必须有一个明确的递归出口，或称递归的边界。

“分治法”求解递归问题算法的一般形式为：

void p(参数表)
{
if(递归结束条件成立)可直接求解; //递归终止的条件
else p(较小的参数); //递归步骤
}

可见，上述阶乘函数和Fibonacci数列的递归过程均与此一般形式相对应。

2．数据结构是递归的

某些数据结构本身具有递归的特性，则它们的操作可递归地描述。

对于递归的数据结构，相应算法采用递归的方法来实现特别方便。链表的创建和链表结点的遍历输出都可以采用递归的方法。算法3.9是从前向后遍历输出链表结点的递归算法，调用此递归函数前，参数p指向单链表的首元结点，在递归过程中，p不断指向后继结点，直到p为NULL时递归结束。显然，这个问题满足上述给出的采用“分治法”进行递归求解的问题需要满足的三个条件。

算法3.9　遍历输出链表中各个结点的递归算法

【算法步骤】

① 如果p为NULL，递归结束返回。
② 否则输出p->data，p指向后继结点继续递归。

【算法描述】

void TraverseList(LinkList p)
{
if(p==NULL) return; //递归终止
else
{
cout<data<next); //p指向后继指点继续递归
}
}

在递归算法中，如果当递归结束条件成立，只执行return操作时，“分治法”求解递归问题算法的一般形式可以简化为：

void p(参数表)
{
if(递归结束条件不成立)
p(较小的参数);
}

因此，算法3.9可以简化为：

void TraverseList(LinkList p)
{
if(p)
{
cout<data<next);
} }

后面章节要介绍的广义表、二叉树等也是典型的具有递归特性的数据结构，其相应算法也可采用递归的方法来实现。

3．问题的解法是递归的

还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单。

3.4.2　递归过程与递归工作栈

一个递归函数，在函数的执行过程中，需多次进行自我调用。那么，这个递归函数是如何执行的？先看任意两个函数之间进行调用的情形。

与汇编语言程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需通过栈来进行。

通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：

（1）将所有的实参、返回地址等信息传递给被调用函数保存；
（2）为被调用函数的局部变量分配存储区；
（3）将控制转移到被调函数的入口。

而从被调用函数返回调用函数之前，系统也应完成3件工作：

（1）保存被调函数的计算结果；
（2）释放被调函数的数据区；
（3）依照被调函数保存的返回地址将控制转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。

一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入“下一层”，即第i + 1层。反之，退出第i层递归应返回至“上一层”，即第i − 1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个工作记录，其中包括所有的实参、所有的局部变量，以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”。

下面以上图所示的阶乘函数Fact(4)为例，介绍递归过程中递归工作栈和活动记录的使用。主函数调用Fact(4)，当函数运行结束后，控制返回到RetLoc1，在此处n被赋为24（即4!）：

               void main( )
               {
                  long n;            //调用Fact (4)时记录进栈
                  n=Fact(4);        //返回地址RetLoc1在赋值语句
   RetLoc1
               }

为说明方便起见，将阶乘函数算法改写为：

                  long Fact(long n )
                  {    
                     long temp;
                     if (n==0) return 1;        //活动记录退栈
                     else temp=n*Fact(n-1);        //活动记录进栈
                                                              //返回地址RetLoc2在计算语句
            RetLoc2
                     return temp;                //活动记录退栈
                }

这里暂忽略局部变量temp的入栈和出栈情况。RetLoc2是递归调用Fact (n-1)的返回地址，当Fact(n-1)结束后，返回到RetLoc2，在此处计算n*(n-1)!，然后将结果赋给临时变量temp。

主函数执行后依次启动了5个函数调用。图3.10所示为每次函数调用时活动记录的进栈情况。主程序外部调用Fact(4)的活动记录在栈底，Fact (1)调用Fact (0)进栈的活动记录在栈顶。

递归结束条件出现于函数Fact(0)的内部，执行Fact(0)引起了返回语句的执行。退出栈顶的活动记录，返回地址返回到上一层Fact(1)的调用递归处RetLoc2，继续执行语句temp=1*1，接着执行return temp又引起新的退栈操作。此退栈过程直至Fact(4)执行完毕后，将控制权转移给main为止，其过程如图3.11所示。

3.4.3　递归算法的效率分析

1．时间复杂度的分析

在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析可以转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问题，而递归方程的形式多种多样，其求解方法也不一而足。迭代法是求解递归方程的一种常用方法，其基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端（即方程的解）的估计。

下面以阶乘的递归函数Fact(n)为例，说明通过迭代法求解递归方程来计算时间复杂度的方法。

设Fact(n)的执行时间是T(n)。此递归函数中语句if(n==0) return 1;的执行时间是O(1)，递归调用Fact(n-1)的执行时间是T(n-1)，所以else return n*Fact(n-1);的执行时间是O(1)+ T(n-1)。其中，设两数相乘和赋值操作的执行时间为O(1)，则对某常数C、D有如下递归 方程：

设n>2，利用上式对T(n-1)展开，即在上式中用n-1代替n得到
T(n-1)=C+T(n-2)
再代入T(n)=C+T(n-1)中，有
T(n)=2C+T(n-2)
同理，当n>3时有
T(n)=3C+T(n-3)
依次类推，当n>i时有
T(n) =iC+T(n-i)
最后，当i=n时有
T(n)=nC+T(0)=nC+D
求得递归方程的解为：T(n)=O(n)

采用这种方法计算Fibonacci数列和Hanoi塔问题递归算法的时间复杂度均为O(2n)。

2．空间复杂度的分析

递归函数在执行时，系统需设立一个“递归工作栈”存储每一层递归所需的信息，此工作栈是递归函数执行的辅助空间，因此，分析递归算法的空间复杂度需要分析工作栈的大小。

对于递归算法，空间复杂度

S(n) = O(f (n))

其中，f(n)为“递归工作栈”中工作记录的个数与问题规模n的函数关系。

根据这种分析方法不难得到，前面讨论的阶乘问题、Fibonacci数列问题、Hanoi塔问题的递归算法的空间复杂度均为O(n)。

3.4.4　利用栈将递归转换为非递归的方法

通过上述讨论，可以看出递归程序在执行时需要系统提供隐式栈这种数据结构来实现，对于一般的递归过程，仿照递归算法执行过程中递归工作栈的状态变化可直接写出相应的非递归算法。这种利用栈消除递归过程的步骤如下。

（1）设置一个工作栈存放递归工作记录（包括实参、返回地址及局部变量等)。
（2）进入非递归调用入口（即被调用程序开始处）将调用程序传来的实在参数和返回地址入栈（递归程序不可以作为主程序，因而可认为初始是被某个调用程序调用)。
（3）进入递归调用入口：当不满足递归结束条件时，逐层递归，将实参、返回地址及局部变量入栈，这一过程可用循环语句来实现—模拟递归分解的过程。
（4）递归结束条件满足，将到达递归出口的给定常数作为当前的函数值。
（5）返回处理：在栈不空的情况下，反复退出栈顶记录，根据记录中的返回地址进行题意规定的操作，即逐层计算当前函数值，直至栈空为止—模拟递归求值过程。

通过以上步骤，可将任何递归算法改写成非递归算法。但改写后的非递归算法和原来比较起来，结构不够清晰，可读性差，有的还需要经过一系列的优化，这里不再举例详述，具体示例参见5.5.1节中二叉树中序遍历的非递归算法。

由于递归函数结构清晰，程序易读，而且其正确性容易得到证明，因此，利用允许递归调用的语言（如C语言）进行程序设计时，给用户编制程序和调试程序带来很大方便。因为对这样一类递归问题编程时，不需用户自己而由系统来管理递归工作栈。

3.5 队列的表示和操作的实现

3.5.1　队列的类型定义

队列的操作与栈的操作类似，不同的是，删除是在表的头部（即队头）进行。

下面给出队列的抽象数据类型定义：

ADT Queue {

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R={＜ai−1,ai＞|ai−1,ai∈D,i=2,…,n}

约定其中a1端为队列头，an端为队列尾。

基本操作：

InitQueue(＆Q)

操作结果：构造一个空队列Q。

DestroyQueue(＆Q)

初始条件：队列Q已存在。

操作结果：队列Q被销毁，不再存在。

ClearQueue(＆Q)

初始条件：队列Q已存在。

操作结果：将Q清为空队列。

QueueEmpty(Q)

初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回true，否则返回false。

QueueLength(Q)

初始条件：队列Q已存在。

操作结果：返回Q的元素个数，即队列的长度。

GetHead(Q)

初始条件：Q为非空队列。

操作结果：返回Q的队头元素。

EnQueue(＆Q,e)

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。

DeQueue(＆Q,＆e)

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。

QueueTraverse(Q)

初始条件：Q已存在且非空。

操作结果：从队头到队尾，依次对Q的每个数据元素访问。

}ADT Queue

和栈类似，在本书后面内容中引用的队列都是如上定义的队列类型，队列的数据元素类型在应用程序内定义。

3.5.2　循环队列—队列的顺序表示和实现

队列也有两种存储表示，顺序表示和链式表示。

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个整型变量front和rear分别指示队列头元素及队列尾元素的位置（后面分别称为头指针和尾指针）。

为了在C语言中描述方便起见，在此约定：初始化创建空队列时，令front = rear = 0，每当插入新的队列尾元素时，尾指针 rear增1；每当删除队列头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如图3.12所示。

假设当前队列分配的最大空间为6，则当队列处于图3.12（d）所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。

怎样解决这种“假溢出”问题呢？一个较巧妙的办法是将顺序队列变为一个环状的空间，如图3.13所示，称之为循环队列。 头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

在图3.14（a）中，队头元素是J5，在元素J6入队之前，在 Q.rear的值为5，当元素J6入队之后，通过“模”运算，Q.rear = (Q.rear +1)%6，得到Q.rear的值为0，而不会出现图3.12（d）的“假溢出”状态。

在图3.14（b）中，J7、J8、J9、J10相继入队，则队列空间均被占满，此时头、尾指针相同。

在图3.14（c）中，若J5和J6相继从图3.14（a）所示的队列中出队，使队列此时呈“空”的状态，头、尾指针的值也是相同的。

由此可见，对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。在这种情况下，如何区别队满还是队空呢？

通常有以下两种处理方法。

（1）少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队空和队满的条件是：

队空的条件：Q.front == Q.rear
队满的条件：(Q.rear + 1)%MAXQSIZE == Q.front

如图3.14（d）所示，当J7、J8、J9进入图3.14（a）所示的队列后，(Q.rear + 1)%MAXQSIZE的值等于Q.front，此时认为队满。

（2）另设一个标志位以区别队列是“空”还是“满”。具体描述参考本章习题中算法设计题的第（7）题，由读者自行设计完成。

下面给出用第一种方法实现循环队列的操作，循环队列的类型定义同前面给出的顺序队列的类型定义。

1．初始化

循环队列的初始化操作就是动态分配一个预定义大小为MAXQSIZE的数组空间。

算法3.11　循环队列的初始化

【算法步骤】

① 为队列分配一个最大容量为MAXSIZE的数组空间，base指向数组空间的首地址。
② 头指针和尾指针置为零，表示队列为空。

【算法描述】

Status InitQueue(SqQueue ＆Q)
{//构造一个空队列Q
Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间
if(!Q.base) exit(OVERFLOW); //存储分配失败
Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空
return OK;
}

2．求队列长度

对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。

算法3.12　求循环队列的长度

【算法描述】

int QueueLength(SqQueue Q)
{//返回Q的元素个数，即队列的长度
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

3．入队

入队操作是指在队尾插入一个新的元素。

算法3.13　循环队列的入队

【算法步骤】

① 判断队列是否满，若满则返回ERROR。
② 将新元素插入队尾。
③ 队尾指针加1。

【算法描述】

Status EnQueue(SqQueue ＆Q,QElemType e)
{//插入元素e为Q的新的队尾元素
if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1后等于头指针，表明队满
return ERROR;
Q.base[Q.rear]=e; //新元素插入队尾
Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1
return OK；
}

4．出队

出队操作是将队头元素删除。

算法3.14　循环队列的出队

【算法步骤】

① 判断队列是否为空，若空则返回ERROR。
② 保存队头元素。
③ 队头指针加1。

【算法描述】

Status DeQueue(SqQueue ＆Q,QElemType ＆e)
{//删除Q的队头元素，用e返回其值
if(Q.front==Q.rear) return ERROR; //队空
e=Q.base[Q.front]; //保存队头元素
Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1
return OK;
}

5．取队头元素

当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。

算法3.15　取循环队列的队头元素

【算法描述】

SElemType GetHead(SqQueue Q)
{//返回Q的队头元素，不修改队头指针
if(Q.front!=Q.rear) //队列非空
return Q.base[Q.front]; //返回队头元素的值，队头指针不变
}

由上述分析可见，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队。

3.5.3　链队—队列的链式表示和实现

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，如图3.15所示。一个链队显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。队列的链式存储结构表示如下：

//- - - - - 队列的链式存储结构- - - - -
typedef struct QNode
{
QElemType data;
struct QNode next;
}QNode, QueuePtr;
typedef struct
{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;

链队的操作即为单链表插入和删除操作的特殊情况，只是需进一步修改尾指针或头指针。下面给出链队初始化、入队、出队操作的实现。

1．初始化

链队的初始化操作就是构造一个只有一个头结点的空队，如图3.16（a）所示。

算法3.16　链队的初始化

【算法步骤】

① 生成新结点作为头结点，队头和队尾指针指向此结点。
② 头结点的指针域置空。

【算法描述】

Status InitQueue(LinkQueue ＆Q)
{//构造一个空队列Q
Q.front=Q.rear=new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点
Q.front->next=NULL; //头结点的指针域置空
return OK;
}

2．入队

和循环队列的入队操作不同的是，链队在入队前不需要判断队是否满，需要为入队元素动态分配一个结点空间，如图3.16（b）和（c）所示。

算法3.17　链队的入队

【算法步骤】

① 为入队元素分配结点空间，用指针p指向。
② 将新结点数据域置为e。
③ 将新结点插入到队尾。
④ 修改队尾指针为p。

【算法描述】

Status EnQueue(LinkQueue ＆Q,QElemType e)
{//插入元素e为Q的新的队尾元素
p=new QNode; //为入队元素分配结点空间，用指针p指向
p->data=e; //将新结点数据域置为e
p->next=NULL; Q.rear->next=p; //将新结点插入到队尾
Q.rear=p; //修改队尾指针
return OK;
}

3．出队

和循环队列一样，链队在出队前也需要判断队列是否为空，不同的是，链队在出队后需要释放出队头元素的所占空间，如图3.16（d）所示。

算法3.18　链队的出队

【算法步骤】

① 判断队列是否为空，若空则返回ERROR。
② 临时保存队头元素的空间，以备释放。
③ 修改队头指针，指向下一个结点。
④ 判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点。 ⑤ 释放原队头元素的空间。

【算法描述】

Status DeQueue(LinkQueue ＆Q,QElemType ＆e)
{//删除Q的队头元素，用e返回其值
if(Q.front==Q.rear) return ERROR; //若队列空，则返回ERROR
p=Q.front->next; //p指向队头元素
e=p->data; //e保存队头元素的值
Q.front->next=p->next; //修改头指针
if(Q.rear==p) Q.rear=Q.front; //最后一个元素被删，队尾指针指向头结点
delete p; //释放原队头元素的空间
return OK;
}

需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。

4．取队头元素

与循环队列一样，当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。

算法3.19　取链队的队头元素。

【算法描述】

SElemType GetHead(LinkQueue Q) {//返回Q的队头元素，不修改队头指针
if(Q.front!=Q.rear) //队列非空
return Q.front->next->data; //返回队头元素的值，队头指针不变
}

3.6 案例分析与实现

在3.2节我们引入了3个有关栈应用的案例和一个有关队列应用的案例。本节对这四个案例作进一步的分析，然后分别利用栈和队列的基本操作给出案例中相关算法的具体实现。

案例3.1：数制的转换。

【案例分析】

当将一个十进制整数N转换为八进制数时，在计算过程中，把N与8求余得到的八进制数的各位依次进栈，计算完毕后将栈中 的八进制数依次出栈输出，输出结果就是待求得的八进制数。

【案例实现】

在具体实现时，栈可以采用顺序存储表示也可以采用链式存储表示。

算法3.20　数制的转换

【算法步骤】

① 初始化一个空栈S。
② 当十进制数N非零时，循环执行以下操作：

• 把N与8求余得到的八进制数压入栈S；
• N更新为N与8的商。

③ 当栈S非空时，循环执行以下操作：

• 弹出栈顶元素e；
• 输出e。

【算法描述】

void conversion(int N)
{//对于任意一个非负十进制数，打印输出与其等值的八进制数
InitStack(S); //初始化空栈S
while(N) //当N非零时,循环
{
Push(S,N%8); //把N与8求余得到的八进制数压入栈S
N=N/8; //N更新为N与8的商
}
while(!StackEmpty(S)) //当栈S非空时，循环
{
Pop(S,e); //弹出栈顶元素e
cout<<e; //输出e
}
}

【算法分析】

显然，该算法的时间和空间复杂度均为O(log8n)。

这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈的操作是单调的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不是更简单吗？但仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。

在实际利用栈的问题中，入栈和出栈操作大都不是单调的，而是交错进行的。下面的案例3.2和3.3都属于这种情况。

案例3.2：括号匹配的检验。

【案例分析】

检验算法借助一个栈，每当读入一个左括号，则直接入栈，等待相匹配的同类右括号；每当读入一个右括号，若与当前栈顶的左括号类型相同，则二者匹配，将栈顶的左括号出栈，直到表达式扫描完毕。

在处理过程中，还要考虑括号不匹配出错的情况。例如，当出现(( )[ ]))这种情况时，由于前面入栈的左括号均已和后面出现的右括号相匹配，栈已空，因此最后扫描的右括号不能得到匹配；出现[([ ])这种错误，当表达式扫描结束时，栈中还有一个左括号没有匹配；出现(( )]这种错误显然是栈顶的左括号和最后的右括号不匹配。

【案例实现】

算法3.21　括号的匹配

【算法步骤】

① 初始化一个空栈S。
② 设置一标记性变量flag，用来标记匹配结果以控制循环及返回结果，1表示正确匹配，0表示错误匹配，flag初值为1。
③ 扫描表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作：

• 若ch是左括号“[”或“(”，则将其压入栈；
• 若ch是右括号“)”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“(”，则正确匹配，否则错误匹配，flag置为0；
• 若ch是右括号“]”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“[”，则正确匹配，否则错误匹配，flag置为0。

④ 退出循环后，如果栈空且flag值为1，则匹配成功，返回true，否则返回false。

【算法描述】

Status Matching()
{//检验表达式中所含括号是否正确匹配，如果匹配，则返回true，否则返回false
//表达式以“# 结束
InitStack(S); //初始化空栈
flag=1; //标记匹配结果以控制循环及返回结果
cin>>ch; //读入第一个字符
while(ch!='#'&&flag) //假设表达式以“#”结尾
{
switch(ch)
{
case '['||'(': //若是左括号，则将其压入栈
Push(S,ch);
break;
case ')': //若是“)”，则根据当前栈顶元素的值分情况考虑
if(!StackEmpty(S)&&GetTop(S)=='(')
Pop(S,x); //若栈非空且栈顶元素是“(”，则正确匹配
else flag=0; //若栈空或栈顶元素不是“(”，则错误失败
break;
case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑
if(!StackEmpty(S)&&GetTop(S)=='[')
Pop(S,x); //若栈非空且栈顶元素是“[”，则正确匹配
else flag=0; //若栈空或栈顶元素不是“[”，则错误匹配
break;
} //switch
cin>>ch; //继续读入下一个字符
} //while
if(StackEmpty(S)&&flag) return true; //匹配成功
else return false; //匹配失败
}

【算法分析】

此算法从头到尾扫描表达式中每个字符，若表达式的字符串长度为n，则此算法的时间复杂度为O(n)。算法在运行时所占用的辅助空间主要取决于S栈的大小，显然，S栈的空间大小不会超过n，所以此算法的空间复杂度也同样为O(n)。

案例3.3：表达式求值。

【案例分析】

任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的，统称它们为单词。一般地，操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。为了叙述的简洁，在此仅讨论简单算术表达式的求值问题，这种表达式只含加、减、乘、除4种运算符。读者不难将它推广到更一般的表达式上。

下面把运算符和界限符统称为算符。

我们知道，算术四则运算遵循以下3条规则：

（1）先乘除，后加减；
（2）从左算到右；
（3）先括号内，后括号外。

根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符1和2之间的优先关系，至多是下面3种关系之一：

表3.1定义了算符之间的这种优先关系。

由规则（1），先进行乘除运算，后进行加减运算，所以有“+”＜“”；“+”＜“/”；“”＞“+”；“/”＞“+”等。

由规则（2），运算遵循左结合性，当两个运算符相同时，先出现的运算符优先级高，所以有“+”＞“+”；“−”＞“−”；“”＞“”；“/”＞“/”。

由规则（3），括号内的优先级高，+、−、*和/为1时的优先性均低于“（”但高于“）”。

表中的“(”=“)”表示当左右括号相遇时，括号内的运算已经完成。为了便于实现，假设每个表达式均以“#”开始，以“#”结束。所以“#”=“#”表示整个表达式求值完毕。“)”与“(”、“#”与“)”以及“(”与“#”之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨论中，我们暂假定所输入的表达式不会出现语法错误。

【案例实现】

为实现算符优先算法，可以使用两个工作栈，一个称做OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。

算法3.22　表达式求值

【算法步骤】

① 初始化OPTR栈和OPND栈，将表达式起始符“#”压入OPTR栈。
② 扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时，则循环执行以下操作：

• 若ch不是运算符，则压入OPND栈，读入下一字符ch；
• 若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做不同的处理：
• 若是小于，则ch压入OPTR栈，读入下一字符ch；
• 若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈；
• 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于括号匹配成功，然后读入下一字符ch。

③ OPND栈顶元素即为表达式求值结果，返回此元素。

【算法描述】

char EvaluateExpression()
{//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈
InitStack(OPND); //初始化OPND栈
InitStack(OPTR); //初始化OPTR栈
Push(OPTR，'#'); //将表达式起始符“#”压入OPTR栈
cin>>ch;
while(ch!='#'||GetTop(OPTR)!='#') //表达式没有扫描完毕或OPTR的栈顶元素不为“#”
{
if(!In(ch)){Push(OPND,ch);cin>>ch;} //ch不是运算符则进OPND栈
else
switch(Precede(GetTop(OPTR),ch)) //比较OPTR的栈顶元素和ch的优先级
{
case '<':
Push(OPTR,ch);cin>>ch; //当前字符ch压入OPTR栈，读入下一字符ch
break;
case '>':
Pop(OPTR,theta); //弹出OPTR栈顶的运算符
Pop(OPND,b);Pop(OPND,a); //弹出OPND栈顶的两个运算数
Push(OPND,Operate(a,theta,b)); //将运算结果压入OPND栈
break;
case '=': //OPTR的栈顶元素是“(”且ch是“)”
Pop(OPTR,x);cin>>ch; //弹出OPTR栈顶的“(”，读入下一字符ch
break;
} //switch
} //while
return GetTop(OPND); //OPND栈顶元素即为表达式求值结果
}

算法调用的三个函数需要读者自行补充完成。其中函数In是判定读入的字符ch是否为运算符，Precede是判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数，Operate为进行二元运算的函数。

另外需要特别说明的是，上述算法中的操作数只能是一位数，因为这里使用的OPND栈是字符栈，如果要进行多位数的运算，则需要将OPND栈改为数栈，读入的数字字符拼成数之后再入栈。读者可以改进此算法，使之能完成多位数的运算。

【算法分析】

同算法3.21一样，此算法从头到尾扫描表达式中每个字符，若表达式的字符串长度为n，则此算法的时间复杂度为O(n)。算法在运行时所占用的辅助空间主要取决于OPTR栈和OPND栈的大小，显然，它们的空间大小之和不会超过n，所以此算法的空间复杂度也同样为O(n)。

【例3.2】　算法表达式的求值过程。 利用算法3.22对算术表达式3*(7−2)进行求值，给出其求值的具体过程。 在表达式两端先增加“#”，改写为

#3*(7−2)#

具体操作过程如表3.2所示。

在高级语言的编译处理过程中，实际上不只是表达式求值可以借助栈来实现，高级语言中一般语法成分的分析都可以借助栈来实现，在编译原理后续课程中会涉及栈在语法、语义等分析算法中的应用。

算法3.23　舞伴问题

【算法步骤】

① 初始化Mdancers队列和Fdancers队列。
② 反复循环，依次将跳舞者根据其性别插入Mdancers队列或Fdancers队列。
③ 当Mdancers队列和Fdancers队列均为非空时，反复循环，依次输出男女舞伴的姓名。
④ 如果Mdancers队列为空而Fdancers队列非空，则输出Fdancers队列的队头女士的姓名。
⑤ 如果Fdancers队列为空而Mdancers队列非空，则输出Mdancers队列的队头男士的姓名。

【算法描述】

void DancePartner(Person dancer[],int num)
{//结构数组dancer中存放跳舞的男女，num是跳舞的人数。
InitQueue(Mdancers); //男士队列初始化
InitQueue(Fdancers); //女士队列初始化
for(i=0;i<num;i++) //依次将跳舞者根据其性别入队
{
p=dancer[i];
if(p.sex=='F') EnQueue(Fdancers,p); //插入女队
else EnQueue(Mdancers,p); //插入男队
}
cout<<"The dancing partners are:\n";
while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers))
{//依次输出男女舞伴的姓名
DeQueue(Fdancers,p); //女士出队
cout<<p.name<<" "; //输出出队女士姓名
DeQueue(Mdancers,p); //男士出队
cout<<p.name<<endl; //输出出队男士姓名
}
if(!QueueEmpty(Fdancers)) //女士队列非空，输出队头女士的姓名
{
p=GetHead(Fdancers); //取女士队头
cout<<"The first woman to get a partner is: "<< p.name<<endl;
}
else if(!QueueEmpty(Mdancers)) //男士队列非空，输出队头男士的姓名
{
p=GetHead(Mdancers) //取男士队头
cout<<"The first man to get a partner is: "<< p.name<<endl;
}
}

【算法分析】

若跳舞者人数总计为n，则此算法的时间复杂度为O(n)。空间复杂度取决于Mdancers队列和Fdancers队列的长度，二者长度之和不会超过n，因此空间复杂度也同样为O(n)。

队列在程序设计中也有很多应用，凡是符合先进先出原则的数学模型，都可以用队列。最典型的例子是操作系统中用来解决主机与外设之间速度不匹配问题或多个用户引起的资源竞争问题。

这方面的例子很多，在操作系统等后续课程中会涉及大量队列这种数据结构的应用。

在实际应用中，队列应用的例子更是常见，通常用以模拟排队情景。例如，拿汽车加油站来说，通常的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是在进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，总共需要设置的队列个数应该为加油车道数加上2。

3.7 小 结

本章介绍了两种特殊的线性表：栈和队列，主要内容如下。

（1）栈是限定仅在表尾进行插入或删除的线性表，又称为后进先出的线性表。栈有两种存储表示，顺序表示（顺序栈）和链式表示（链栈）。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判断栈满或栈空。
（2）队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）。队列的主要操作是进队和出队，对于顺序的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。
（3）栈和队列是在程序设计中被广泛使用的两种数据结构，其具体的应用场景都是与其表示方法和运算规则相互联系的。表3.3分别从逻辑结构、存储结构和运算规则3方面对二者进行了比较。

（4）栈有一个重要应用是在程序设计语言中实现递归。递归是程序设计中最为重要的方法之一，递归程序结构清晰，形式简洁。但递归程序在执行时需要系统提供隐式的工作栈来保存调用过程中的参数、局部变量和返回地址，因此递归程序占用内存空间较多，运行效率较低。

学习完本章后，要求掌握栈和队列的特点，熟练掌握栈的顺序栈和链栈的进栈和出栈算法，循环队列和链队列的进队和出队算法。要求能够灵活运用栈和队列设计解决实际应用问题，掌握表达式求值算法，深刻理解递归算法执行过程中栈的状态变化过程，便于更好地使用递归算法。