文档介绍：第3章栈和队列本章学****目标:、特性,并能正确应用它们解决实际问题。、链表存储以及相应操作的实现。、 栈的定义及其运算一、栈的定义栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此,表尾具有特殊的含义,是允许插入和删除的一端,称为栈顶(Top),表头端为固定的一端,称为栈底(Bottom)。不含元素的栈称为空栈。栈的插入与删除操作分别称为进栈和出栈。进栈是将一个数据元素存放栈顶,出栈是将栈顶元素取出,如图4- 栈的定义及其运算图4-1栈示意图an-2an-1... 栈的定义及其运算二、栈的特点根据栈的定义可知,最先放入栈中的元素在栈底,最后放入的元素在栈顶,元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。因此,栈是一种后进先出(Last In First Out)的线性表,简称为LIFO表。如元素是以a1,a2,…,an的顺序进栈,退栈的次序却是an,an-1,…,a1。 栈的定义及其运算三、栈的运算有关栈的基本操作主要有以下几种:1 初始化栈:InitStack(S) 初始条件:栈s不存在。操作结果:构造一个空栈S。2. 进栈:Push(S,X)初始条件:栈s已存在且非满。操作结果:若栈S不满,则将元素x插入S的栈顶。:Pop(S) 初始条件:栈s已存在且非空。操作结果:删除栈S中的栈顶元素,栈中少了一个元素,也称为“退栈”、“删除”或“弹出”。:GetTop(S) 栈的定义及其运算初始条件:栈s已存在且非空操作结果:输出栈顶元素,但栈中元素不变。:Empty(S)初始条件:栈s已存在操作结果:判断栈S是否为空,若为空,返回值为1,否则返回值为0。(S)初始条件:栈s已存在操作结果:若S为满栈,则返回1,否则返回0。注意:该运算只适用于栈的顺序存储结构。 ,它类似于线性表的顺序存储结构,是利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设一栈顶指针top指向栈顶元素的下一个位置。通常用一维数组来实现栈的顺序存储。一般以数组小下标一端做栈底,即top=0时为空栈,每进栈一个元素,指针top加1;每出栈一个元素,指针减1。栈的存储结构描述为:typedefstruct{ElemTypeelem[MaxSize];int top; }SqStack; 、栈满或不空不满三种状态之一,它们是通过栈顶指针top的值体现出来的。在这我们规定:top的值为下一个进栈元素在数组中的下标值。假设S是SqStack类型的指针变量,MaxSize为6,栈空时(初始状态),top=0,如图3-2(a)所示;图3-2(b)是进栈两个元素的状况,图3-2(c)是栈满时的状况,此时top=MaxSize;图3-2(d)是在图3-2(c)基础上出栈一个元素后的栈状况。 栈的顺序存储结构图3-2 (a)(b)(c)栈满edcba012345(d) (1)初始化栈【】 void InitStack(SqStack*S ){ /*建立一个空栈S*/ S->top=0; }/*InitStack*/