沈俊 第4章 栈和队列.pptVIP

第4章 栈和队列 引言 本章所讨论的栈和队列是上一章所讨论的线性表的特殊情况，即限制存取位置的线性表。 线性表、栈和队列的数据元素和逻辑结构均相同，只是线性表是可在任意位置插入和删除的线性结构，栈是只可在表头位置插入和删除的线性结构，队列是只可在表尾位置插入、在表头位置删除的线性结构。 递归不是一种数据结构，而是一种有效的算法设计方法。递归在许多实际系统中都有应用。这里主要介绍递归的概念、递归的过程与递归工作栈，并讨论了用循环实现递归过程，还讨论了迷宫问题。 4.1??? 栈 栈（stack）是只允许在表的末端进行插入和删除的线性表。 允许插入和删除的一端叫做栈顶（top），不允许插入和删除的另一端叫做栈底(bottom)。 无任何元素的栈称为空栈。  出栈如图4-3所示。 栈的两种抽象数据类型：采用顺序存储方式的顺序栈（如图4-1）和采用链式存储方式的链式栈。 4.1.1? 顺序栈 顺序栈（seqential stack）就是用顺序存储方式存储的栈。 在下面顺序栈的类定义中是用数组存储元素的。数组名为stacka[maxsize] ，maxsize是最大允许存放元素的个数。变量top表示栈顶部元素的位置，初始值为－1，表示空栈。 顺序栈的类定义 template class type class seqstack { //顺序栈的类定义 private: int top; 　 //栈顶指示 type * stacka; //数组名 int maxsize; //栈最大可容纳元素个数 public: seqstack( int size ); //构造函数 ~seqstack( ) { delete [ ] stacka;} //析构函数 void push (const type item); //元素item进栈 type pop(void ); //数据元素出栈，返回之 type gettop( ); //读栈顶数据元素并返回 int empty (void) const {return top == -1;} //栈空返回1，否则返回0 int full ( )const {return top == maxsize-1;} void clear(void) {top = -1;} //清空栈 }; 下面给出顺序栈的典型成员函数的实现。先给出顺序栈的构造函数，它动态地建立栈空间，其最大尺寸maxsize由函数参数size给出，并令top等于－1，置栈为空。如分配不成功则打印分配失败信息，否则正常结束。 ? template class type seqstack type :: seqstack (int size): top(-1) , maxsize (size) { //建立一个最大尺寸为size的空栈 stacka = new type[maxsize]; //创建存储栈的数组 if (stacka == NULL)　　　　　　//分配不成功 { cerr动态存储分配失败！endl; exit(1); } } 实现进栈、出栈和取栈顶元素的操作： template class typevoid seqstack type :: push(const type item) {//若栈已满，出错处理；否则把元素item入栈 if (full( ))　　　　　//栈已满 {cerr栈已满，不能入栈！endl; exit(1);} top++;　　　　　　　　//栈未满，入栈 stacka[top] = item; } template class typetype seqstack type :: pop( ) {//栈空时出错，否则出栈，并返回栈顶元素 if (empty( )) //栈空 {cout栈已空！endl;exit(1);} type data = stacka[top];//栈不空，取栈顶元素 top -- ; return data; //返回栈顶元素 } 4.1.2????链式栈 链式栈（linked