第三章栈、队列和递归A课件.ppt

;特殊线性表;3.1栈（Stack） ;３.1 栈;注： 栈的运算规则 　　只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。 入栈：插入元素到栈顶（即表尾）的操作。 出栈：从栈顶（即表尾）删除最后一个元素的操作。 问：栈与一般线性表有什么不同？ 一般线性表 （堆）栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 　　 运算规则：后进先出 (LIFO) 　　　入栈操作演示　　　　　　出栈操作演示;a1;a1;思考题１：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？;思考题２：;栈的抽象数据类型定义参见P86-87 2、栈的存储结构 顺序栈、链式栈 （１）顺序栈——栈的顺序存储结构(重点) ;进栈核心语句：top++; S[top]=a1;; 0 1 2 3 4 5 6 7 8;动态栈类的定义： template class type //定义模板类DSeqStack class DSeqStack { public: DSeqStack( int size) ; //构造函数，栈的初始化 　~DSeqStack( ){delete [] S;} //析构函数 void Push(const type item); //将元素item入栈 type Pop( ); //将栈顶元素弹出 type GetTop( ); //取栈顶元素（并不删除） 　int Empty( )const{return top==-1;} 　　　//判断栈是否为空 　int full()const{return top==MaxSize-1;} 　　　//为满则返回1，否则返回0 　void clear(){top=-1;}//清空栈 private: type *S; //存放栈元素的数组起始地址 　　int top; //栈顶指针，指示栈顶元素在数组中的下标 int MaxSize; //栈最大可容纳元素个数 };;顺序栈的构造函数算法实现;顺序栈的入栈操作算法实现;出栈核心语句： Item=S[top]; top--;;顺序栈的出栈操作算法实现;其它类型栈举例：如两栈共享空间 ;栈1的栈底:固定靠下标为0的这一端； 栈2的栈底:固定靠下标为MaxSize-1的这一端。 top1和top2分别为栈1和栈2的栈顶指针； MaxSize:整个数组空间的大小（图中用S表示）；;栈1为空条件：top1== -1 栈2为空条件??top2== MaxSize;a1 a2 … … ai;（２）链式栈——栈的链式存储结构;链栈类的定义： template class type class LinkStack;//声明 template class type class Node { friend class LinkStacktype; private: type data; Nodetype *next; //此处T也可以省略 }; template class type class LinkStack { public: LinkStack( ); //构造函数，置空链栈 ~LinkStack( ); //析构函数，释放链栈中各结点的存储空间 void Push(type item); //将元素item入栈 type Pop( ); //将栈顶元素出栈 type GetTop( ); //取栈顶元素（并不删除） bool Empty( ); //判断链栈是否为空栈 private: Nodetype *top; //栈顶指针即链栈的头指针 };;链栈的构造函数算法实现;算法实现： templateclass type void inkStacktype::Push(ty