文档介绍：第3章栈和队列
栈
队列
本章小结
习题三
实训3-1 栈的应用
实训3-2 队列的应用
【教学目标】栈和队列是两种特殊并且非常重要的线性表。通过对本章学习,掌握栈和队列的概念和特征,掌握栈和队列的顺序存储结构和链式存储结构,掌握栈和队列的基本操作的实现算法——进栈、出栈、判断栈空、入队、出队、判断队列空和队满,并能熟练地运用栈和队列解决实际问题。
栈和队列是两种重要的数据结构,也是两种特殊的线性结构。从数据的逻辑结构角度来看,栈和队列是线性表;从操作的角度来看,栈和队列的基本操作是线性表操作的子集,是操作受限制的线性表。栈和队列在操作系统、编译原理、大型应用软件系统中得到了广泛的应用。
栈
栈的定义和基本操作
1. 栈的定义
栈(Stack)是一种限定性的线性表,是将线性表的插入和删除运算限制在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top),因此栈顶的当前位置是动态变化的,它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom),栈底是固定的。(a)所示。当栈中没有元素时称为空栈,(b)所示。栈的插入操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。
栈结构示意图
(a) 非空栈;(b) 空栈
假设有一个栈S=(a1, a2 ,…, ai-1, ai, ai+1, …, an),如果a1先进栈,则an最后进栈。因为进栈和出栈元素都只能在栈顶一端进行,所以每次出栈的元素总是当前栈中栈顶的元素,它是最后进栈的元素,而最先进栈的元素要到最后才能出栈。在日常生活中,有许多类似栈的例子。例如将洗净的盘子放入消毒桶时,总是一个接一个地往上摞(相当于进栈);取出盘子时,则是从最上面一个接一个地往外拿(相当于出栈),最后取出的是最先放进去的那个盘子。因此,栈又被称为后进先出(Last In First Out,LIFO)的线性表。
2. 栈的基本操作
栈的基本操作主要有以下七种:
(1) InitStack(S)。
操作前提:S为未初始化的栈。
操作结果:将S初始化为空栈。
(2) ClearStack(S)。
操作前提:栈S已经存在。
操作结果:将栈S置成空栈。
(3) IsEmpty(S)。
操作前提:栈S已经存在。
操作结果:判栈空函数,若S为空栈,则函数值为TRUE或1,否则为FALSE或0。
(4) IsFull(S)。
操作前提:栈S已经存在。
操作结果:判栈满函数,若S栈已满,则函数值为TRUE或1,否则为FALSE或0。
(5) Push(S,x)。
操作前提:栈S已经存在。
操作结果:在S的顶部插入(亦称压入)元素x;若S栈未满,将x插入栈顶位置,若栈已满,则返回FALSE或0,表示操作失败,否则返回TRUE或1。
(6) Pop(S)。
操作前提:栈S已经存在。
操作结果:删除(亦称弹出)栈S的顶部元素,返回该值;若栈为空,返回值为NULL,表示操作失败。
(7) GetTop(S)。
操作前提:栈S已经存在。
操作结果:取栈S的顶部元素。与Pop(S)不同之处在于GetTop(S)不改变栈顶的位置。