21世纪高等学校计算机专业核心课程规划教材数据结构(C语言版)(第3版)/唐国民

第3章 栈 和 队 列 本章要点  栈  栈的应用举例  队列  队列的应用举例 本章学习目标  理解栈的定义及其基本运算  掌握顺序栈和链栈的各种操作实现  理解队列的定义及其基本运算  掌握循环队列和链队列的各种操作实现  学会利用栈和队列解决一些问题 3.1栈 栈和队列是在程序设计中广泛使用的两种重要的数据结构。由于从数据结构角度看，栈和队列是操作受限的线性表，因此，也可以将它们称为限定性的线性表结构。 3.1.1栈的定义与基本操作 在日常生活中，我们会发现有许多这样的趣事。例如，把许多书籍依次放进一个大小相当的箱子中，当我们在取书时，就得先把后放进里面的书取走，才能拿到先放入的被压在*底层的书； 又如一叠洗净的盘子，洗的时候总是将盘子逐个叠放在已洗好的盘子上面，而用的时候则是从上往下逐个取用，即后洗好的盘子比先洗好的盘子先被使用。这种后进先出的结构称为栈。 1. 栈的定义 栈(stack)是一种仅允许在一端进行插入和删除运算的线性表。栈中允许进行插入和删除的那一端，称为栈顶(top)。栈顶的第1个元素称为栈顶元素。栈中不可以进行插入和删除的那一端（线性表的表头），称为栈底(bottom)。在一个栈中插入新元素，即把新元素放到当前栈顶元素的上面，使其成为新的栈顶元素，这一操作称为进栈、入栈或压栈（push）。从一个栈中删除一个元素，即把栈顶元素删除掉，使其下面的元素成为新的栈顶元素，称为出栈或退栈（pop）。例如，在栈S=（a1，a2，…，an）中，a1称为栈底元素，an称为栈顶元素。进栈顺序为a1，a2，…，an，如图3.1(a)所示，而出栈顺序为an，an-1，…，a2，a1。 注意： 由于栈的插入和删除操作只能在栈顶一端进行，后进栈的元素必定先出栈，所以栈又称为后进先出(Last In First Out)的线性表(简称为LIFO结构)。它的这个特点可用图3.1(b)所示的铁路调度站形象地表示。 图3.1栈的图示 思考： ① 栈是什么？它与一般线性表有何不同？ ② 一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512有可能实现吗？12345的输出呢？ 讨论： 有无通用的判别原则？ 有！若输入序列是…,Pj，…，Pk，…，Pi，…(Pj 2. 栈的基本操作 定义在栈上的基本操作有： （1） InitStack(S)： 构造一个空栈S。 （2） ClearStack(S)： 清除栈S中的所有元素。 （3） StackEmpty(S)： 判断栈S是否为空，若为空，则返回true； 否则返回false。 （4） GetTop(S)： 返回S的栈顶元素，但不移动栈顶指针。 （5） Push(S, x)： 插入元素x作为新的栈顶元素（入栈操作）。 （6） Pop(S)： 删除S的栈顶元素并返回其值（出栈操作）。 由于栈是运算受限的线性表，因此线性表的存储结构对栈也同样适用。与线性表相似，栈也有两种存储表示方法，即顺序存储和链式存储两种结构。顺序存储的栈称为顺序栈，链式存储的栈称为链栈。 3.1.2顺序栈的存储结构和操作的实现 1. 顺序栈存储结构的定义 顺序栈利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，可以用一维数组描述顺序栈中数据元素的存储区域，并预设一个数组的*大空间。栈底设置在0下标端，栈顶随着插入和删除元素而变化，即入栈的动作使地址向上增长（称为“向上增长”的栈），可用一个整型变量top来指示栈顶的位置。为此，顺序栈存储结构的描述如下： #define Maxsize 100/*设顺序栈的*大长度为100，可依实现情况而修改*/ typedef int datatype; typedef struct { datatype stack［Maxsize］; int top； /*栈顶指针*/ }SeqStack； /*顺序栈类型定义*/ SeqStack *S； /*S为顺序栈类型变量的指针*/ 由于C语言中数组下标是从0开始的，即S>stack［0］是栈底元素，而栈顶指针S>top是正向增长的，即进栈时栈顶指针S>top加1，然后把新元素放在top所指的空单元内，退栈时S>top减1，因此S>top等于-1（或S>top小于0）表示栈空，S>top等于maxsize-1表示栈满。由此可知，对顺序栈进行插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为O(1)。一个栈的几种状态以及在这些状态下栈顶指针top和栈中元素之间的关系如图3.2所示。 图3.2栈顶指针和栈中元素之间的关系 通过分析，我们可以得出以下结论： （1） 若top=-1，则表示栈空。 如果使栈顶指针top指向待入栈元素的位置，则入栈、出栈时，top应该如何变化？栈空、栈满的条件又是什么？ （2） 若top=maxsize-1，则表示栈满。 如果使栈顶指针top指向待入栈元素的位置，则入栈、出栈时，top应该如何变化？栈空、栈满的条件又是什么？ 2. 顺序栈的基本操作 由于顺序栈的插入和删除只在栈顶进行，因此顺序栈的基本操作比顺序表简单得多。值得一提的是： 在做入栈操作前，首先要判定栈是否满； 在做出栈操作前，又得先判定栈是否空。 1） 构造一个空栈 SeqStack *InitStack() { SeqStack *S; S=(SeqStack *)malloc(sizeof(SeqStack)); if(!S) {printf("空间不足")； return NULL;} else {S->top=-1; return S;} } 2） 取栈顶元素 datatype GetTop(SeqStack *S) {if (S->top==-1) {printf("＼n栈是空的!"); return FALSE;} else return S->stack［S->top］; } 3） 入栈 SeqStack *Push(SeqStack *S，datatype x) {if(S->top==Maxsize-1) {printf("＼n栈是满的!"); return NULL; } else { S->top++; S->stack［S->top］=x; return s;} } 4） 出栈 datatype Pop( SeqStack *S) {if(S->top==-1) {printf("＼nThe sequence stack is empty!"); return FALSE;} S->top--; return S->stack［S->top+1］; } 5） 判别空栈 intStackEmpty(SeqStack*S) {if(S->top==-1) return TRUE; else return FALSE; } 例3.1若增加main函数以及display函数，则可以调试上述各种栈的基本操作算法。 #define Maxsize 50 typedef int datatype; typedef struct {datatype stack［Maxsize］; int top； }SeqStack； void display(SeqStack *S) {int t; t=S->top; if(S->top==-1) printf("the stack is empty!＼n"); else while(t!=-1)