第03讲 栈和队列.pptVIP

第三章 栈和队列 第一部分 栈 第二部分 队列 第一部分 栈 一、栈的定义 二、栈的抽象数据类型 三、栈的顺序存储结构和操作实现 四、栈的链接存储结构和操作实现 五、栈的简单应用举例 一、栈的定义 栈（Stack）是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把对栈进行运算的一端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为退栈或出栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。 在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的一摞盘子的上面，此操作相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则称为进栈；射击时子弹总是从顶部一个接一个地被射出，此称为子弹出栈。 由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表(Last In First Out, 简称LIFO)。 假定一个栈S为(a,b,c)，其中表尾的一端为栈顶，字符c为栈顶元素。若向S压入一个元素d，则S变为(a,b,c,d)，此时字符d为栈顶元素；若接着从栈S中依次删除两个元素，则首先删除的是元素d，接着删除的是元素c，栈S变为(a,b)，栈顶元素为b。 二、栈的抽象数据类型 栈的抽象数据类型中的数据部分为具有ElemType元素类型的一个栈，它可以采用任一种存储结构实现；操作部分应包括元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。下面给出栈的抽象数据类型的具体定义。 ADT STACK is //STACK是栈的抽象数据类型名 Data: 一个栈S //存储栈中的所有元素 Operation: void InitStack(S); //初始化栈S,即把它置为空 void Push(S,item) //元素进栈，即把元素item插入到栈顶 ElemType Pop(S) //删除栈顶元素并返回之 ElemType Peek(S) //返回栈顶元素的值，但不改变栈的状态 bool EmptyStack (S); //判断S是否为空 void ClearStack(S); //清除栈中所有元素，使之成为空栈 End STACK 三、栈的顺序存储结构和操作实现 对于判断栈是否为空和返回栈顶元素这两种操作，由于它们不改变栈的状态，所以可在引用参数前使用常量定义符const，使得函数操作不能有意或无意地改变栈的状态。 假定栈a的元素类型为int，下面给出调用上述栈操作的一些例子。 (1) InitStack(a); //表示把栈a置空 (2) Push(a,18); //表示元素18进栈 (3) int x=46; Push(a,x); //表示x的值46进栈 (4) Push(a,x/3); //表示x除以3的整数值15进栈 (5) x=Pop(a); //表示栈顶元素15退栈并赋给x (6) coutPeek(a); //表示读取当前栈顶元素46并输出 (7) Pop(a); //栈顶元素46出栈，返回值46自动丢失 (8) EmptyStack(a); //因此时栈a非空，所以返回的值false (9) coutPop(a)endl; //栈顶元素18退栈并输出，此时栈已空 (10) x=EmptyStack(a); //因栈为空,返回true,接着把对应的整数值1赋给x 栈的顺序存储结构同集合的顺序存储结构类似，定义的结构类型如下： struct Stack { // Stack为结构类型名 ElemType *stack; //指向动态分配的数组存储空间的首地址的指针 int top; //栈顶指针，存储栈顶元素所在的下标位置 int MaxSize; //保存stack所指向的栈空间的大小 }; 在顺序存储的栈中，top的值为-1表示栈空，每次向栈中压入一个元素时，首先使top增1，用以指示新的栈顶位置，然后再把元素赋值到这个空位置上