第3章栈和队列1.docVIP

第3章 栈和队列 栈和队列是两种重要的线性结构。它们的共同特点是：操作受限（插入元素和删除元素只能在端点处进行）的线性表。 3.1 栈 3.1.1 抽象数据类型栈的定义 什么是栈（Stack）：栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端有其特殊的含义，称为栈顶（Top），相应地，表头端称为栈底（Bottom）。不含元素的栈称为空栈。 栈在生活中的例子：蒸小茏包，先放下去的最后才拿出来。 栈：是先进后出（First In Last Out，FILO）的线性表，也可称为后进先出（Last in First Out，LIFO）。对应的一个名词：先进先出First In First Out（FIFO）。通常栈可用下图来表示： 假设插入元素的序列为：49,27,36,57,63,89,16，这个过程称为入栈。其过程为：将元素放到当前栈顶指向的空间，然后，栈顶移动一个位置。 出栈：就是将元素从栈顶元素处删除。其过程为：先将栈顶向下移动一个位置，再将该元素拷贝出来。 典型的题目：如果有4个元素：a b c d，依次入栈，其中又陆续出栈，问有哪些合法的出栈顺序？ 1）a b c d ？可以 2）a b d c ？可以 3）c b d a ？可以 4）c a d b ？不可能 抽象数据类型的定义： ADT Stack{ 数据对象： 数据关系： 基本操作： 1）InitStack，初始化栈 2）DestroyStack，销毁栈，栈的空间释放了 3）ClearStack，将一个栈清空，栈的空间还在 4）StackEmpty，判断一个栈是否是空栈，返回True或False 5）StackLength，求栈的长度，也就是求栈中还有几个元素 6）GetTop，返回栈顶元素，但该元素还在栈中 7）Push，元素入栈 8）Pop，栈顶元素出栈 9）遍历：StackTraverse，从栈底到栈顶元素，依个进行访问。 3.1.2 栈的表示和实现 栈有两种表示：顺序表示（顺序栈）、链式表示（链表栈）。 所谓顺序栈，就是用一个顺序表（数组）来存储栈的元素。显然，我们需要这些数据：存储元素的空间的首地址、栈顶指针、栈的空间总大小。就得到下列结构体： 1、顺序栈的第一种实现： typedef struct{ SElemType *base; //存储元素的空间的首地址，可用malloc函数申请空间，将地址赋给它 SElemType *top; //栈顶指针，指的是当前栈顶元素的上面的那个位置，初始时，top指向base int stacksize; //当前栈的最大空间大小，用来判断栈是否已经满了，从而可以采取必要的措施。 }SqStack; #define STACK_INIT_SIZE 100 #define STACK_INCREMENT 10 SqStack S; //定义一个栈的变量S 1）初始化栈函数 Status InitSqStack( 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; return OK; } 2）判断一个栈是否是空栈 Status SqStackEmpty( SqStack S ) { if( S.top==S.base ) return TRUE; else return FALSE; } 3）清空一个栈 Status ClearSqStack( SqStack S ) { S.top=S.base; return OK; } 4）销毁一个栈 Status DestroySqStack( SqStack S ) { free( S.base ); S.base=S.top=NULL; S.stacksize=0; return OK; } 5）求栈的长度 int SqStackLength( SqStack S ) { return S.top-S.base; } 6）入栈 Status PushSqStack( SqStack S, SElemType e ) { if( S.top-S.base=S.stacksize ) //栈的空间满了 { S.base=(SElemType*)realloc( S.base, (S.stacksize+10)*s