数据结构 （C语言版）课件：第3章栈和队列

1、第3章 栈和队列,3.1 栈,3.2 队列,本章小结,栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。 栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时，称为空栈。 栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。,3.1.1 栈的定义,3.1 栈,栈的主要特点是“后进先出”，即后进栈的元素先出栈。栈也称为后进先出表。,思考题： 栈和线性表有什么不同？,例3.1 设有4个元素a、b、c、d进栈，给出它们所有可能的出栈次序。,解：所有可能的出栈次序如下: abcd abdc

2、 acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba,例3.2 设一个栈的输入序列为A,B,C,D，则借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C,解：可以简单地推算，得容易得出D,A,B,C是不可能的，因为D先出来，说明A,B,C,D均在栈中，按照入栈顺序，在栈中顺序应为D,C,B,A，出栈的顺序只能是D,C,B,A。所以本题答案为D。,例3.3 已知一个栈的进栈序列是1,2,3,n，其输出序列是p1,p2,pn，若p1=n，则pi的值 。

3、 (A) i (B) n-i (C) n-i+1 (D) 不确定,解：当p1=n时，输出序列必是n,n-1,3,2,1，则有: p2=n-1, p3=n-2, , pn=1 推导出pi=n-i+1,所以本题答案为C。,例3.4 设n个元素进栈序列是1,2,3,n，其输出序列是p1,p2,pn，若p1=3，则p2的值 。 (A) 一定是2(B) 一定是1 (C) 不可能是1 (D) 以上都不对,解：当p1=3时，说明1,2,3先进栈，立即出栈3，然后可能出栈，即为2，也可能4或后面的元素进栈，再出栈。因此，p2可能是2，也可能是4,n，但一定不能是1。所以本题答案为C。,栈的几种基本运算如下:,

4、InitStack( ,（4）进栈Push( ElemType e; SqStack *st; InitStack(st);/初始化栈 for (i=0;stri!=0;i+)/将串所有元素进栈 Push(st,stri);/元素进栈 for (i=0;stri!=0;i+) Pop(st,e); /退栈元素e if (stri!=e) /若e与当前串元素不同则不是对称串 DestroyStack(st);/销毁栈 return false; DestroyStack(st); /销毁栈 return true; ,3.1.3 栈的链式存储结构及其基本运算的实现,采用链式存储的栈称为链栈,这里

5、采用单链表实现。 链栈的优点是不存在栈满上溢的情况。这里规定栈的所有操作都是在单链表的表头进行的，用带头节点的单链表表示链栈，第一个数据节点是栈顶节点,最后一个节点是栈底节点。 栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈的4要素：,栈空条件：s-next=NULL 栈满条件：不考虑 进栈e操作：将包含e的节点插入到头节点之后 退栈操作：取出头节点之后节点的元素并删除之,链栈中数据节点的类型LiStack定义如下:,typedef struct linknode ElemType data;/数据域 struct linknode *next;/指针域 LiStack;,在链栈中，栈的基本运算算法如下。 （1）初始化栈initStack( ,（