数据结构域算法设计-第3章 栈和队列1教案

《数据结构域算法设计-第3章 栈和队列1教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列栈和队列是两种重要的线性结构。它们的共同特点是：操作受限（插入元素和删除元素只能在端点处进行）的线性表。3.1栈3.1.1抽象数据类型栈的定义什么是栈（Stack）：栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端有其特殊的含义，称为栈顶（Top），相应地，表头端称为栈底（Bottom）。不含元素的栈称为空栈。栈在生活中的例子：蒸小茏包，先放下去的最后才拿出来。栈：是先进后出（FirstInLastOut，FILO）的线性表，也可称为后进先出（LastinFirstOut，LIFO）。对应的一个名词：先进先出FirstInFirstOut（FIFO

2、）。通常栈可用下图来表示：362749栈底basetopstacksize=100SqStackS100......362749低位地址高位地址baseinttop=3stacksize=100假设插入元素的序列为：49,27,36,57,63,89,16，这个过程称为入栈。其过程为：将元素放到当前栈顶指向的空间，然后，栈顶移动一个位置。出栈：就是将元素从栈顶元素处删除。其过程为：先将栈顶向下移动一个位置，再将该元素拷贝出来。典型的题目：如果有4个元素：abcd，依次入栈，其中又陆续出栈，问有哪些合法的出栈顺序？1）abcd？可以2）abdc？可以3）cbda？可以4）ca

3、db？不可能抽象数据类型的定义：ADTStack{数据对象：数据关系：基本操作：1）InitStack，初始化栈2）DestroyStack，销毁栈，栈的空间释放了3）ClearStack，将一个栈清空，栈的空间还在4）StackEmpty，判断一个栈是否是空栈，返回True或False5）StackLength，求栈的长度，也就是求栈中还有几个元素6）GetTop，返回栈顶元素，但该元素还在栈中7）Push，元素入栈8）Pop，栈顶元素出栈9）遍历：StackTraverse，从栈底到栈顶元素，依个进行访问。3.1.2栈的表示和实现栈有两种表示：顺序表示（顺序栈）、链式表

4、示（链表栈）。所谓顺序栈，就是用一个顺序表（数组）来存储栈的元素。显然，我们需要这些数据：存储元素的空间的首地址、栈顶指针、栈的空间总大小。就得到下列结构体：1、顺序栈的第一种实现：typedefstruct{SElemType*base;//存储元素的空间的首地址，可用malloc函数申请空间，将地址赋给它SElemType*top;//栈顶指针，指的是当前栈顶元素的上面的那个位置，初始时，top指向baseintstacksize;//当前栈的最大空间大小，用来判断栈是否已经满了，从而可以采取必要的措施。}SqStack;#defineSTACK_INIT_SIZE10

5、0#defineSTACK_INCREMENT10SqStackS;//定义一个栈的变量S1）初始化栈函数StatusInitSqStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//申请100个空间if(!S.base)exit(-1);//申请空间失败，直接退出程序S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}2）判断一个栈是否是空栈StatusSqStackEmpty(SqStackS){if(S.top==

6、S.base)returnTRUE;elsereturnFALSE;}3）清空一个栈StatusClearSqStack(SqStack&S){S.top=S.base;returnOK;}4）销毁一个栈StatusDestroySqStack(SqStack&S){free(S.base);S.base=S.top=NULL;S.stacksize=0;returnOK;}5）求栈的长度intSqStackLength(SqStackS){returnS.top-S.base;}6）入栈StatusPushSqStack(SqStack&S,SElemTypee){if(

7、S.top-S.base>=S.stacksize)//栈的空间满了{S.base=(SElemType*)realloc(S.base,(S.stacksize+10)*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base+S.stacksize;S.stacksize+=10;}*(S.top)=e;//S.top++;returnOK;}7）出栈StatusPopSqStack(SqStack&S,SElemType&e){if(S.top==S.base)/