第4章 栈和队列

1、第四章 栈与队列本章主要内容n 栈的概念、存储结构及其基本操作n 栈的应用n队列的概念、存储结构及其基本操作n队列的应用n递归4.1 4.1 栈栈n栈的定义n栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。n进行插入和删除的称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，称为栈底。a1, a2, a3, ., an 插入和删除端插入和删除端栈的特点栈的特点n后进先出（后进先出（Last In First Out），简称为），简称为LIFO线性表。线性表。 n举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先

2、拿走最上面的那只碗，而最后拿出最下面的那只碗。 n举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。 n顺序栈 用顺序存储实现的栈称为顺序栈。分配一块连续的存储空间存放栈中的元素，栈底位置固定设置在数组的任何一端（一般在下标为0的一端），栈顶是随着插入和删除变化的，用一个变量指明栈顶的位置（实际上是栈顶元素的下一个位置），存储结构如图所示。栈的C+实现typedef int DataType; /这里以整型为栈的数据类型class SeqStackprivate: DataType *base;/栈底指针 DataType *top;/栈顶指针始终指向

3、栈顶元素的后一个位置 int size;/栈的大小public: SeqStack(int stacksize=100) base=new DataType stacksize; top=base; /指向栈顶元素的后一位置 size=stacksize; ; /构造了一个空栈,默认大小为100个单元 SeqStack() delete base; top=NULL;base=NULL; ; /销毁一个已存在的栈 int Empty_Stack(); /判断栈是否为空 int Push_Stack(DataType e); /将元素e插入栈顶 int Pop_Stack(DataType &e

4、);/从栈顶删除一个元素到e中返回 int GetTop_Stack(DataType &e); /从栈顶取一个元素到e中返回;/顺序栈类顺序栈的成员函数的实现 （1）判断栈是否为空 算法思想：判断top是否小于等于base，小于等于则为空栈，返回1，否则返回0。 int SeqStack:Empty_Stack() /判断顺序栈是否为空 return(top=base);（2）入栈操作 算法思想：首先判断栈是否已满，若满则失败，返回0；否则，由于栈的top指向栈顶元素的后一个位置，将入栈元素赋到top的位置，再将top+1指向新的位置，成功返回1。 int SeqStack:Push_Sta

5、ck(DataType e) if(top-basebase) /判断栈是否为空 top-; e=*top; return 1; else return 0;（4）取栈顶元素操作 算法思想：首先判断栈是否为空，若空则失败，返回0；否则，由于栈的top指向栈顶元素的后一位置，返回top-1所指单元的值，栈不发生变化。 int SeqStack:GetTop_Stack(DataType &e) if(topbase) /判断栈是否为空 e=*(top-1); return 1; else return 0;链栈的成员函数的实现 栈也可以用链式存储方式实现。一般链栈用单链表表示，其结点结构与单链表

6、的结构相同，即结点为：typedef int DataType; /这里以整型为栈的数据类型 class StackNode /定义链栈的结点public: DataType data; StackNode *next; StackNode() next=NULL; ; ; 链栈的存储示意图链栈的类定义class LinkStackprivate: StackNode *top;public: LinkStack() top=NULL; ; /构造一个新的空栈 LinkStack() /销毁一个已存在的栈 StackNode *p; while(top) /销毁栈中所有元素 p=top; to

7、p=top-next; delete p; top=NULL; /栈顶指针赋空表示为空栈 ; int Empty_Stack();/判断栈是否为空 int Push_Stack(DataType e);/将元素e插入栈顶 int Pop_Stack(DataType &e);/从栈顶删除一个元素到e中返回 int GetTop_Stack(DataType &e); /从栈顶取出一个元素到e中返回; /链栈类链栈的成员函数的实现 （1）判断栈是否为空int LinkStack:Empty_Stack() /判断链栈是否为空 return(!top);（2）入栈操作 算法思想：首先为链栈分配空间

8、，若成功，将入栈元素赋值到申请的链栈结点，并插入栈顶，使其成为栈顶元素，成功返回1；否则失败，返回0。int LinkStack:Push_Stack(DataType e) StackNode *p=new StackNode; /申请结点 if(p) /申请结点成功 p-data=e; p-next=top; top=p; /修改栈顶指针 return 1; else return 0;（3）出栈操作 算法思想：首先判断栈是否为空，若非空，则取出栈顶元素，以引用参数e返回，并删除这个结点，成功返回1；否则，失败返回0。 int LinkStack:Pop_Stack(DataType &e

9、) StackNode *p;if(top) p=top; e=p-data; top=top-next; /修改栈顶指针 delete p; /删除结点 return 1; else return 0;（4）取栈顶元素操作 算法思想：首先判断栈是否为空，若非空，则取出栈顶元素，以引用参数e返回，成功返回1；否则，失败返回0。 int LinkStack:GetTop_Stack(DataType &e) if(top) e=top-data; return 1; else return 0;返回栈的应用 1.数制转换 将十进制数N转换为r进制的数，其转换方法为辗转相除法。以N=1 234，r

10、=8为例，转换方法如下。算法思想如下。（1）初始化一个字符类型的栈，初始化N为要转换的数，r为进制数；（2）判断N的值，为0时转（4），否则N % r所表示的数码压入栈s中；（3）用N / r代替N，转（2）；（4）出栈，出栈序列即为结果。int DecConversion(int N,int r,char NumR) /十进制N转换成r进制,这里r为不大于10的数 SeqStack S; /定义一个顺序栈 DataType x; int i=0; if(r10) /限定为十进制以下 return(0); while(N) S.Push_Stack(CodeTableN%r); /余数表示的数

11、码入栈 N=N/r; /商作为被除数继续 while(!S.Empty_Stack() /直到栈空退出循环 S.Pop_Stack(x);/弹栈顶元素 NumRi+=x;/输出栈顶元素 NumRi=0; return(1);返回队 列 队列也是一种特殊的线性表，是限制在表的一端进行插入和在另一端进行删除的线性表。表中允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。 e1 e2 e3 e4 e5 入队 出队 队列又称为先进先出线性表（First In First Out），简称FIFO表。其特点是先进先出或者后进后出 顺序队列 分配一块连续的存储空间来存放队列中的元素，

12、并且由于队列的队头和队尾都是活动的，因此有队头、队尾两个指针。这里约定，队头指针指向实际队头元素所在的位置的前一位置，队尾指针指向实际队尾元素所在的位置 n队列假溢问题解决办法循环队列下的运算实现typedef int DataType; /这里以整型为队列的数据类型 class SeqQueueprivate: DataType *base; int front; int rear; int size;public: SeqQueue(int Queuesize=100) /构造一个空队列，空间大小为100 base=new DataType Queuesize; front=0; rear

13、=0; size=Queuesize; ; SeqQueue() /销毁一个已存在的队列 delete base; ; int Empty_Queue(); /判断队列是否为空 int En_Queue(DataType e); /入队将元素e插入队尾 int De_Queue(DataType &e); /出队从队头删除一个元素到e中返回 int Front_Queue(DataType &e); /取队头元素，从队头取出一个元素到e中返回; （1）判断循环队列是否为空 int SeqQueue:Empty_Queue()/判断循环队列是否为空 return(front=rear);（2）进

14、队操作 算法思想：首先判断队是否已满，若满则退出，否则，由于队的rear指向队尾元素，先修改rear到新的队尾位置，再将入队元素赋到rear的位置即可。 int SeqQueue:En_Queue(DataType e) if(rear+1)%size)!=front)/判断队列是否满 rear=(rear+1)%size; baserear=e; return 1; else return 0;（3）出队操作 算法思想：首先判断队列是否为空，若空则退出，否则，由于队列的front指向队头元素的前一位置，因此要先修改front，再将其front所指向的元素以引用参数e返回即可。int SeqQ

15、ueue:De_Queue(DataType &e) if(rear!=front) /判断队列是否空 front=(front+1)%size; e=basefront; return 1; else return 0;（4）取队头元素操作 算法思想：首先判断队是否为空，若空则退出，否则，由于队列的front指向队头元素的前一位置，因此要返回的队头元素是front的后一位置。 int SeqQueue:Front_Queue(DataType &e) if(rear!=front) /判断队列是否空 e=base(front+1)%size; return 1; else return 0;

16、 返回4.队列的应用 求迷宫的最短路径：现要求设计一个算法找一条从迷宫入口到出口的最短路径 算法基本思想：从迷宫入口点（1，1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点；依此类推，直到到达迷宫的出口点（m，n）为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径 使用队列保存搜索过程5.递归 递归的定义：若一个对象部分地包括它自己，或用它自己给自己定义，则称这个对象是递归的；或定义为在一个过程中直接或间接地调用自己，则这个过程是递归的。 以n的阶乘为例，n!的定义为：n的阶乘等于n乘以n-1的阶乘，公

17、式标示：1 0!(1)! 0nnnnn当时当时int fact(int n) if(n=0) return 1; else return(n* fact(n-1);递归算法书写要点如下。（1）问题具有类同自身的子问题的性质，被定义项在定义中的应用具有更小的尺度。（2）被定义项在最小尺度上有直接解。设计递归算法的方法是：（1）寻找方法，将问题化为原问题的子问题求解（例如n!=n*(n-1)!）。（2）设计递归出口，确定递归终止条件（例如求解n!时，当n=1时，n!=1）。递归过程的调用和返回 递归函数的递归过程：在递归进层（ii+1层）时系统需要做3件事。（1）保留本层参数与返回地址（将所有的实

18、际参数、返回地址等信息传递给被调用函数保存）；（2）给下层参数赋值（为被调用函数的局部变量分配存储区）；（3）将程序转移到被调函数的入口。而从被调用函数返回调用函数之前，递归退层（ii+1层）系统也应完成3项工作。（1）保存被调函数的计算结果；（2）恢复上层参数（释放被调函数的数据区）；（3）依照被调函数保存的返回地址，将控制转移回调用函数。n具体实例：n！的递归调用过程求迷宫中的一条路径的递归算法 算法思想：在搜索路径的过程中，每个点朝4个方向的搜索方法是一样的，故可设计成递归算法 int mazepath(int *maze,int x,int y,int m,int n) struct int dx; int dy; move4; /定义移动的4个方向