《数据结构域算法设计-第三章栈和队列(修订版本2010.6)教案》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第三章栈和队列(修订版本2010.6)教案（25页珍藏版）》请在金锄头文库上搜索。
1、1第三章第三章 栈和队列栈和队列内容提要内容提要栈和队列的概念；栈和队列的存储结构及它们的应用。栈和队列与线性表有着密切的联系。一方面，栈和队列的逻辑结构也是线性结构；另 一方面，栈和队列的基本操作是线性表操作的子集。因此，可将栈和队列看成是两种特殊 的线性表。3.1 栈栈3.1.13.1.1 栈的基本概念栈的基本概念在日常生活中有不少类似于栈（如图 3.1（a）所示）的例子。假设有一个很窄的死胡 同，其宽度只能容纳一辆车，现有五辆车，分别编号为，按编号顺序依次进入此胡 同，若要退出，必须先退出；若要退出必须将依次都退出才行。这个死胡 同就是一个栈，如图(b)所示。图 3.1(a) (b)由上
2、面的例子我们可以知道：栈(Stack) 是限制仅在表的一端进行插入和删除操作的线 性表。允许进行插入和删除的一端称为栈顶(top)，不允许插入和删除的一端称为栈底 (bottom)。不含元素的空表称为空栈。假设栈 S(a0 ,a1 ,.,an-1 )，如图(a)所示，a0 为栈底元素，an-1为栈顶元素。栈中元 素按 a0 ,a1 ,.,an-1 的次序进栈，退栈的第一个元素应为栈顶元素。也就是说，栈的特点是 后进先出(Last In First Out)，因此，栈又称为后进先出的线性表，简称 LIFO 线性表。 栈的基本操作如下：InitStack(S)：初始化操作。设置一个空栈 S。Sta
3、ckEmpty(S)：判栈空操作。若 S 为空栈，函数值为 1，否则为 0。Size(S) ：求栈深操作。函数值为栈中当前的元素个数。12345进出a1a2a3an栈顶栈底进栈出栈2Top(S)：读栈顶元素操作。若栈 S 不空，函数值为栈顶元素，否则为空元素 NULL。Push(S,x)：进栈操作。将元素 x 插入栈 S 中，使 x 成为栈 S 的栈顶元素。Pop(S)：出栈操作。若栈 S 不空，函数值为栈顶元素，且从栈中删除当前栈顶 元素，否则函数值为空元素 NULL。Clear(S)：栈置空操作。不论栈 S 是否为空栈，将 S 置为空栈。 下面我们看一个简单的栈的应用的例子。 我们在学习计
4、算机文化基础课时已经学习了用除法把十进制数转换成二进制数的方法。 用初始十进制数除以 2，把余数记录下来，若商不为 0，则再用商去除以 2，直到商为 0， 这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前 面）就得到了相应的二进制数。如把十进制数 35 转换成二进制数的过程如下。由题意可知，我们可以用一个栈来保存所有的余数，当商为 0 时则让栈里的所有余数 出栈，这样就可以得到正确的二进制数。上述算法可描述如下： void conversion() Stack S; int n; InitStack( printf(“Input a number to conve
5、rt:n“); scanf(“%d“, if(n /栈的最大容量 typedef struct elemtype elemmaxsize; int top; sqstacktp; 设 s 为 sqstacktp 型变量，即 s 表示一个顺序栈。图说明了这个顺序栈的几种状态。 (a)表示顺序栈为空，s.top=0； (b)表示栈中只含一个元素 A，s.top=1，在(a)的基础上用进栈操作 Push(s,A)可以得到这 种状态； (c)表示在(b)的基础上将元素 B、C 依次进栈后的状态，s.top=3； (d)表示在(c)状态下将元素 C 退栈后的情况，s.top=2，由执行一次 Pop(s)
6、得到； (e)表示栈中有五个元素，s.top=maxsize，这种状态称为栈满，此时若有元素进栈则将 产生“数组越界”的错误，称为栈溢出。（a） (b) (c) (d) (e)图 顺序栈的几种状态因此，s.top=0 表示空栈，出栈和读栈顶元之前应判断栈是否为空。s.top=maxsize 表示 栈满，进栈之前应判断是否栈满。下面讨论在顺序栈上实现的操作。（1）初始化（栈置空）操作 算法： void InitStack(sqstacktp *s) /将顺序栈 s 置为空 s-top=0; 如下函数生成了一个顺序栈，并完成了对该顺序栈的初始化。 void main()topC B AtopB A
7、topF E D B AtopAtop4 void InitStack(sqstacktp *s); sqstacktp *s; s=(sqstacktp *)malloc(sizeof(sqstacktp); InitStack(s); （2）判栈空操作 算法： int StackEmpty(sqstacktp *s) if(s-top0) return 0; else return 1; （3）进栈操作 算法： void Push(sqstacktp *s,elemtype x) / 若栈 s 未满，将元素 x 压入栈中；否则，栈的状态不变并给出出错信息if(s-top=maxsize)p
8、rintf(“Overflow“);elses-elems-top+=x; /x 进栈 （4）出栈操作 算法： elemtype Pop(sqstacktp *s) / 若栈 s 不空，则删去栈顶元素并返回元素值，否则返回空元素 NULL if(s-top=0) return NULL; else s-top-; /栈顶指针减 1 return s-elems-top; /返回原栈顶元素值 （5）求栈深操作 算法: int Size(sqstacktp *s) 5return(s-top); （6）读取栈顶元素操作 算法： elemtype Top(sqstacktp *s) if(s-top
9、=0) return NULL;else return(s-elems-top-1); 顺序栈使用起来比较简单，但是必须预先给它分配一个存储空间。为了使栈不溢出， 我们通常必须为它分配一个较大的空间，然而在大多数时候都会造成存储空间的浪费。但 是在当程序中同时使用两个栈时，有一种方法可以提高存储空间的使用效率：可以将两个 栈的栈底设在一维数组空间的两端，让两个栈各自向中间延伸，仅当两个栈的栈顶相遇时 才可能发生上溢，如图所示。这样当一个栈里的元素较多，超过向量空间的一半时， 只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。所以，当两个栈共享一个长度为 maxsize 的数组空间时
10、，每个栈实际可利用的最大空间大于 maxsize/2。图 两个栈共亨空间示意图 上述结构的类型描述如下： #define maxsize /栈的最大容量 typedef struct elemtype elemMAXSIZE; int top2; dustacktp若 ds 为 dustacktp 型变量，显然，栈 1 的顶由 ds.top0指示，ds.top0=0 表示栈 1 为空。栈 2 的顶由 ds.top1指示，ds.top1=maxsize+1 表示栈 2 为空。ds.top0 +1=ds.top1表示栈满。3.1.33.1.3 栈的链式存储结构栈的链式存储结构由栈的顺序存储结构可知
11、，顺序栈的最大缺点是：为了保证不溢出，必须事先给栈分 配一个较大的空间，这显然浪费了存储空间，而且在很多时候我们并不能保证所分配的空 间就一定够用，这大大降低了顺序栈的可用性，这时我们就要采用链式存储结构。 栈的链式存储结构，简称链栈(linked stack)，它的组织形式与单链表类似，链表的尾部 结点是栈底，链表的头部结点是栈顶。由于只在链表的头部进行操作，故链栈没有必要设 置头结点。如图所示，其中，单链表的头指针 head 作为栈顶指针。链栈由栈顶指针 head 唯一确定，栈底结点的 next 域为 NULL。abcaABtop1top26图 链栈示意图链栈的类型定义如下： typede
12、f struct stacknode elemtype data; struct stacknode *next; stacknode; typedef struct stacknode *top; /栈顶指针 LinkStack;下面给出初始化、进栈和出栈操作在链栈上的实现。 (1) 初始化操作 算法： void InitStack(LinkStack *ls) /建立一个空栈 ls ls-top=NULL; 下面函数完成了对一个链栈的创建和初始化操作。 void main() LinkStack *ls; ls=(LinkStack *)malloc(sizeof(LinkStack);
13、InitStack(ls); (2) 进栈操作 算法： void Push(LinkStack *ls,elemtype x) stacknode *s=NULL; s=(stacknode *)malloc(sizeof(stacknode); /生成新结点 s-data=x; FheaddatanextEDANULL栈顶栈底7s-next=ls-top; /链入新结点 ls-top=s; /修改栈顶指针 （3）出栈操作 算法： elemtype Pop (LinkStack *ls) /若栈 ls 不空，删去栈顶元素并返回元素值，否则返回空元素 NULL stacknode *p=NULL
14、; elemtype x; if(ls-top=NULL) return NULL; else x=(ls-top)-data; p=ls-top; ls-top=p-next; free(p); return x; /返回原栈顶元素值 链栈一般不会产生栈满，只有当整个可用空间都被占满，malloc()函数过程无法实现时 才会发生上溢。另外，链栈占用的空间是动态分配的，所以多个链栈可以共享存储区域。3.2 栈的应用实例栈的应用实例栈在计算机科学领域具有广泛的应用，只要问题满足后进先出原则，均可使用栈作为 其数据结构。例如：在编译和运行计算机语言程序的过程中，就需要利用栈进行语法检查 （如检查
15、PASCAL 语言中 begin 和 end、 （和） 、和是否配对等） 、计算机表达式的值、实 现递归过程和函数的调用等。表达式求值表达式求值要把一个表达式翻译成能正确求值的机器指令，或者直接对表达式求值，首先要能正 确解释表达式。例如，要对下面的算术表达式求值1 + 2 * 4 - 9 / 3 必须遵循先乘除后加减、先左后右及先括号内后括号外的四则运算法则，其计算顺序应为1 + 2 * 4 - 9 / 3 8 那么，如何让机器也按照这样的规则求值呢？通常采用“运算符优先数法” 。一般表达式中会遇到操作数、运算符和表达式结束符（为了简化问题，这里仅讨论只 含加、减、乘、除四种运算，并且不含括号的情况） 。对每种运算符赋予一个优先数，如运算符： * / + - #优先数： 2
