《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第3章 栈和队列》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第3章 栈和队列（45页珍藏版）》请在金锄头文库上搜索。
1、第3章 栈和队列,3.1 栈 3.2 栈的应用举例 3.3 队列 3.4 队列的应用举例,第3章 栈和队列,栈和队列是两类特殊的线性表，其逻辑结构仍然是线性结构，但栈和队列是运算受限的线性表。栈和队列结构被广泛应用于各种程序设计中。 本章讨论栈和队列的定义、运算及其实现等。,3.1.1 栈的定义及其运算 栈是一类特殊的线性表，数据元素的插入和删除运算只能在表的一端进行，通常将进行插入和删除的一端称为栈顶，另一端称为栈底。将元素的插入称为入栈或进栈，元素的删除称为出栈或退栈。 栈也称为后进先出的线性表（简称LIFO表）如图3.1(a)所示。 在日常生活中，栈的形式经常出现。例如，一叠盘子或一叠书
2、的取放、铁路调度站，如图3.1(b)所示。 栈的基本运算： （1）置空栈setnull(s)：将栈s置成空栈，建立起栈顶指针。 （2）判栈空empty(s)：若s为空栈，则返回TRUE值，否则返回FALSE值。 （3）入栈push(s,x)：若s未满，将x插入s栈栈顶，并使栈顶指针指向x。 （4）出栈pop(s)：若s栈非空，则从栈中删去栈顶元素，返回原栈顶元素。 （5）取栈顶元素gettop(s)：若s栈非空，则返回当前栈顶元素。,3.1 栈,3.1.2 栈的顺序存储结构 栈的顺序存储结构又称为顺序栈，顺序栈也可用向量来实现。顺序栈的类型定义如下： #define MAXSIZE 100 /
3、*栈的最大容量，这里设为100*/ typedef struct datatype stackMAXSIZE; int top; seqstack; /*顺序栈类型定义*/ seqstack *s; /*定义s为指向顺序栈的指针变量*/ 在顺序栈中进栈或出栈运算时要注意空间的“溢出”。当栈满时，若再进行入栈运算，会产生空间“上溢” ；而当栈空时，再进行出栈运算，会产生空间“下溢” 。图3.2说明了栈中元素与栈顶指针的关系。,在顺序栈上实现的栈的基本运算。 （1）置空栈 void setnull(seqstack *s) s-top=-1; （2）判栈空算法 int empty(seqstack
4、 *s) if(s-toptop=MAXSIZE-1) printf(“stack overflow！n”); return(FALSE); else s-stack+s-top=x; return(TRUE); ,（4）出栈 datatype pop(seqstack *s) if(s-toptop-; return(s-stacks-top+1); （5）取栈顶元素算法 datatype gettop(seqstack *s) if(s-topstacks-top); ,有时可以将多个栈安排在同一个顺序存储空间中，实现多个栈共享存储空间。 假定两个栈共享空间，可以给它们分配一个长度为m的数
5、组空间如图3.3所示。,两个栈共享的数据类型定义如下： typedef struct datatype stackm; int top2; /* top0和top1分别为两栈的栈顶指针*/ sharedstack;,两个栈共享存储单元的部分运算算法如下： （1）置空栈 void setnull(sharedstack *s) s-top0=-1; s-top1=m; /*setnull*/ （2）入栈 int push(sharedstack *s，int i，datatype x) if(i1|s-top0+1= =s-top1) return FALSE; else if(i=0) s-s
6、tack+s-top0=x; else s-stack-s-top1=x; return TRUE; /*push*/,（3）出栈 datatype pop(sharedstack *s，int i) if(i1) return NULL; else if(i= =0) if (s-top0=-1) return NULL; else return（s-stacks-top0-）; else if(s-top1= =m) return NULL; else return（s-stacks-top1+）; /*pop*/,3.1.3 栈的链式存储结构 栈的链式存储结构称为链栈。链栈是运算受限的单
7、链表，其运算只能在链表头部进行，其头指针就是栈顶指针。 链栈的数据类型定义： typedef struct node datatype data; struct node *next; linkstack; linkstack *top; /*链栈头指针，即栈顶指针*/ 链栈如图3.5所示，其中top是栈顶指针。当top=NULL时，该链栈是空栈。,链栈的入栈和出栈运算算法。 （1）入栈 void push(linkstack *top，datatype x) linkstack *p; p=(linkstack *)malloc(sizeof(linkstack); /*生成一个新结点*p*
8、/ p-data=x; p-next=top; top=p; （2）出栈 datatype pop(linkstack *top) linkstack *p; datatype x; if(top= =NULL) printf(“stack empty！n“); return(NULL); ,else ptop； top=top-next; x=p-data; free(p); /*释放p所指的结点*/ return(x); ,3.2 栈的应用举例,3.2.1 表达式求值 一般的，一个表达式由操作数、运算符和分界符组成。若运算符出现在两个运算数或操作数之间（单目运算符除外），称为中缀表达式。中
9、缀表达式有利于人的理解，但不适合机器的实现。因此，在编译系统中，要把中缀表达式变换成一种后缀表达式（也称为逆波兰式），在后缀表达式中，运算符处在两个操作数之后。后缀表达式一不需要使用括号；二不需要考虑运算符的优先级，只需从左到右扫描后缀表达式，当扫描遇到运算符时，就把它前面的两个操作数取出，然后进行运算。如图3.6所示。 把中缀表达式变换为相应的后缀表达式，然后根据后缀表达式计算表达式的值，这两个步骤都可以利用栈结构来实现。,图3.6 后缀表达式的计算过程,要把中缀表达式转变为后缀表达式可以从左到右依次扫描中缀表达式，根据所读到的是操作数还是运算符，利用栈并结合各个运算符之间的优先级关系（表3
10、-1 ）来进行运算。其算法思想是：设置一个栈并初始化，然后从左到右顺序读入中缀表达式。当读到的是操作数时就直接将其输出，并接着读下一个。当读到的是运算符时，就将它赋给2，并根据运算符的优先级关系表3-1，比较2与当前栈顶运算符1的优先级。若2的优先级比1的高，则将2进栈，继续读下一个；若2的优先级比1的低，则将1出栈并作为后缀表达式的一部分输出，然后继续比较2与新的当前栈顶运算符1的优先级；若2的优先级与1的相同，且1为(，2为)，则将1出栈，并丢弃1和2，再继续读下一个；若2的优先级与1的相同，且1和2都是#，则表示表达式处理完毕，算法结束。 例如，图3.7表示对中缀表达式A*(B+C)*D
11、变换为后缀表达式，最后结果为ABC+*D*。,表3-1 运算符优先级关系表,图3.7 中缀表达式转变为后缀表达式过程,将中缀表达式变换为后缀表达式的算法描述如下： void post (seqstack *s，char R ) char ch1，ch2； int j=0; s-stack0=#“; s-top=0; ch2=Rj; while (!(ch2= = # ) else if(proceed(gettop(s)，ch2)= =),push(s，ch2); ch2=R+j; else if(proceed(gettop(s)，ch2)= =) ch1=pop(s); printf(“%
12、c“，ch1); else if(proceed(gettop(s),ch2)= = ) /* postfix*/ 其中proceed( )函数实现表3-1的运算符优先级关系比较功能，其函数返回值为对应的字符，取值为，或=。,把中缀表达式变换成相应的后缀表达式后，根据后缀表达式计算表达式的基本思想是：设置一个操作数栈，从左到右扫描后缀表达式，每读到一个操作数，就将其压入栈中；每当读到一个运算符时，就从栈中弹出两个操作数，结合读入的运算符进行计算，然后将计算结果重新入栈，一直进行，直到整个表达式扫描完毕，最后在栈顶位置的数就是该表达式的值。 图3.8示出后缀表达式ABCD/E*+的求值过程。,(
13、a)读入ABCD后， (b)读到 /，作C/DT1，(c)读到 -，作B-T1T2，(d)读入E后， (e)读到*，作T2*ET3，(f)读到+，作A+T3T4 图3.8 后缀表达式求值过程示例,3.2.2 递归的实现 在程序设计中常常要用到递归的方法。递归函数的特点是在函数内部可以直接或间接地调用函数本身。函数直接调用本身称为直接递归调用；而一个函数通过另一个函数来调用其本身。 例如，一个整数n的阶乘的定义：,其递归算法如下： int fact(int n) if(n= =0) return(1); else return(n*fact(n-1); ,递归函数执行过程的信息传递和控制转移可以
14、用栈结构来实现。系统将整个程序运行时所需的空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当退出一个函数时，就释放它所占用的存储区，当前工作的函数的数据区总在栈顶。 例如，递归函数fact（4）的执行过程如图3.10所示，而图3.11表示求解4！时工作栈的变化。,3.3.1 队列的定义及其运算 队列也是一种运算受限的线性表。只允许在表的一端进行插入运算，而在另一端进行删除运算。允许插入（也称为入队）的一端称为队尾，允许删除（也称为出队）的一端称为队头，当队列中没有数据元素时称为空队列。 队列是一种与栈相反的结构。队列也称为先进先出的线性表，简称为FIFO表，如图3.12所示。队列的含义与现实生活中购物排队相似，先进入队列的成员总是先离开队列。,3.3 队列,通常，队列的基本运算有以下五种： （1）置空队setnull(q)：设置一个队列q为空队列。 （2）判队列空empty（q）：若队列q为空，则返回TRUE，否则返回FALSE。 （3）入队列enqueue（q，x）：将数据元素
