数据结构——C++实现 缪淮扣 顾训穰 沈俊 数据结构-第四章新.pptVIP

新世纪计算机专业系列教材 第四章　栈、队列和递归 本章所讨论的栈和队列是上一章所讨论的线性表的特殊情况，即限制存取位置的线性表。 线性表、栈和队列的数据元素和逻辑结构均相同，只是线性表是可在任意位置插入和删除的线性结构，栈是只可在表头位置插入和删除的线性结构，队列是只可在表尾位置插入、在表头位置删除的线性结构。 递归不是一种数据结构，而是一种有效的算法设计方法。递归在许多实际系统中都有应用。这里主要介绍递归的概念、递归的过程与递归工作栈，并讨论了用循环实现递归过程，还讨论了迷宫问题。 4.1??? 栈 栈（stack）是一种常用的重要的数据结构，其应用十 分广泛。 栈可以定义为只允许在表的末端进行插入和删除的线 性表。 允许插入和删除的一端叫做栈顶（top），不允许插入 和删除的另一端叫做栈底(bottom)。 无元素的栈为空栈。 设有空栈S，进栈时，按照A、B、C的顺序不断地向栈S中插入元素（即进栈，也称压入），则出现如图4-1所示的结果。  出栈如图4-3所示。 栈的两种抽象数据类型：采用顺序存储方式的顺序栈（如图4-1）和采用链式存储方式的链式栈。 4.1.1? 顺序栈 顺序栈（seqential stack）就是用顺序存储方式存储的栈。 在下面顺序栈的类定义中是用数组存储元素的。数组名为stacka[maxsize] ，maxsize是最大允许存放元素的个数。变量top表示栈顶部元素的位置，初始值为－1，表示空栈。 先给出顺序栈的抽象数据类型的描述，然后给出顺序栈的类定义与实现。 顺序栈的抽象数据类型的描述： ADT seqstack is Data 栈顶指示、存放栈元素的数组和栈元素个数的最大数 Operation seqstack //构造函数 输入： 栈元素个数的最大数size 初始化栈：栈顶指示置为-1，创建存储栈的数组，栈 元素个数的最大数maxsize置为size ~seqstack //析构函数 删除存储栈元素的数组 push 输入： 要进栈的项item 前置条件：栈未满 动作： 把item压入栈顶 输出： 无 后置条件：栈顶增加了一个新元素，栈顶指示加1 pop 输入： 无 前置条件：栈非空 动作： 弹出栈顶元素 输出： 返回栈顶元素的值 后置条件：删除栈顶元素，栈顶指示减1 gettop 输入： 无 前置条件：栈非空 动作： 取栈顶数据元素 输出： 返回栈顶数据元素 后置条件：无 empty 输入： 无 前置条件：无 动作： 检查栈顶指示是否等于-1 输出： 栈空时返回1，否则返回0 后置条件：无 full 输入： 无 前置条件：无 动作： 检查栈顶指示是否等于maxsize-1 输出： 栈满时返回1，否则返回0 后置条件：无 clear 输入： 无 前置条件：无 动作： 清空栈 输出： 无 后置条件：栈顶指示为-1 End ADT seqstack 顺序栈的类定义。 template class type class seqstack { //顺序栈的类定义 private: int top; 　　　　　　　//栈顶指示 type * stacka; 　　　　　　　//数组名 int maxsize; 　　　　　　 //栈最大可容纳元素个数 public: seqstack( int size );