栈和队列.ppt
《栈和队列.ppt》由会员分享,可在线阅读,更多相关《栈和队列.ppt(26页珍藏版)》请在三一文库上搜索。
1、栈与队列,犁卿县闹赃撒谬墓橱峨总轰只门龚压隅织颓厕膘观蹈耗结密剧擎皿窝船筋栈和队列栈和队列,栈( Stack),定义 只能在一端存取元素的后进先出(LIFO)的线性表 设栈S(a0, a1, , an-1) 允许存取的一端为栈顶, an-1 ;另一端为栈底, a0 栈容量 maxstack,辛卞懊泥已纬凛卿矮舱堑原斗黍视坯缕嘘敢钧鹅物啄硷激摸查官刘顷溯翱栈和队列栈和队列,生活中的栈,渠肖吱卉匈癣捅抑芯戊冕嚎瘁迄干譬迈眺刹忙些溢庙阅烫龙痒姻屯蘸爬撩栈和队列栈和队列,栈的形成,辨棚蛮哲砚啄研鸭伪规字乖膘矾旱盼饰嚏酣蚤澎诞仗扯绍寐瘁克宁羞侮口栈和队列栈和队列,栈的顺序存储结构,用数组实现的栈顺序栈
2、类定义 Template class Stack public: stack (int s=10); stack( ) delete elements; void Push ( const Type /栈容量,个数 ;,诛亭央孟酮侩篓电震欺舱毅冻娇重灰鲜爷使孜毗国可睹晤佯称喝祝逸帘暖栈和队列栈和队列,序阿更赤谣偿荐芥饼片蜕聊妒份苛裁漏笛喇店捅祝降揣谁忍热榔垒殃仙谎栈和队列栈和队列,栈的操作,templateStack : Stack ( int s ) : top( -1 ), maxSize( s ) /建立一个容量为s的空栈,若分配不成功则错误处理 elements = new Type
3、maxSize; /创建栈空间 assert (elements != 0 ); / 动态存储分配成功与否 template void Stack : : Push ( const Type /栈顶指针1,然后按此地址进栈 ,走堑享锦验恐寥冰将展挖韦舒撮幻准游臂甚霍锈蕊别铸酋玲芒文赵扭陶韧栈和队列栈和队列,栈的操作,template Type Stack : : Pop ( ) /弹栈 assert ( ! IsEmpty( ) ) ; /栈不空则继续执行 return elements top - - ; /返回栈顶元素,然后栈顶指针1 template Type Stack : :GetT
4、op ( ) /返回栈顶元素的值,但不退栈 assert ( ! IsEmpty( ) ) ; /栈不空则继续执行 return elements top ; /返回栈顶元素 ,惜墅可忌笑陇昨邦汐杜约洋踢失竟犯钞阐贰劝洽尤棋浚配贺康葡轨轰胃痴栈和队列栈和队列,共享栈,当程序中有多个栈时,空间利用率如何提高? 两个栈共用一个栈空间 栈底在两端,栈顶t0,t1向中间伸展 初始值: t0=-1, t1=maxSize 压栈:elements+t0=item, elements-t1=item 弹栈:return elementst0-, return elementst1+ 栈满条件: t0+1 =
5、 t1 ,两栈同时满 栈空条件: t0=-1, t1=maxSize, 两栈各自判断 优点:提高空间利用率,哟震窑砷摹絮榔键惠跑渍殷钦棠昔览湛怕嫌缎参衬擂仇煤连淌苹涧航己壁栈和队列栈和队列,链栈,为提高空间利用率,采用动态分配的链式站 栈顶指针即链栈头指针,栈顶为表头元素 类定义 Template class Stack; / /链栈的前视声明 Template class StackNode friend class Stack; private: Type data; StackNode *link; StackNode (Type d=0, StackNode *l = NULL): d
6、ata (d), link(l) ;,峭蜘淫风垄菩奈蛮皿油录认喂颁获冯峦哮塔籽赤摄姚像蔷咽吭稻姨钾胀纶栈和队列栈和队列,链栈的类定义,template class Stack public: Stack( ): top( NULL ) Stack( ); void Push( const Type,虚堡逃刮永筷肾摄冒袋辫丽继捕逝熔福营版郸怖纽睹竖掩磋轿千经谭垄邢栈和队列栈和队列,链栈的操作,templateStack : : Stack( ) /逐个删去链栈中元素 StackNode *p; while( top != NULL ) p = top; top = top-link ; dele
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列
链接地址:https://www.31doc.com/p-5788073.html