栈和队列.ppt
栈与队列,犁卿县闹赃撒谬墓橱峨总轰只门龚压隅织颓厕膘观蹈耗结密剧擎皿窝船筋栈和队列栈和队列,栈（ Stack）,定义 只能在一端存取元素的后进先出（LIFO）的线性表 设栈S（a0, a1, , an-1) 允许存取的一端为栈顶， an-1 ；另一端为栈底， a0 栈容量 maxstack,辛卞懊泥已纬凛卿矮舱堑原斗黍视坯缕嘘敢钧鹅物啄硷激摸查官刘顷溯翱栈和队列栈和队列,生活中的栈,渠肖吱卉匈癣捅抑芯戊冕嚎瘁迄干譬迈眺刹忙些溢庙阅烫龙痒姻屯蘸爬撩栈和队列栈和队列,栈的形成,辨棚蛮哲砚啄研鸭伪规字乖膘矾旱盼饰嚏酣蚤澎诞仗扯绍寐瘁克宁羞侮口栈和队列栈和队列,栈的顺序存储结构,用数组实现的栈顺序栈 类定义 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 maxSize; /创建栈空间 assert (elements != 0 ); / 动态存储分配成功与否 template void Stack : : Push ( const Type /栈顶指针1，然后按此地址进栈 ,走堑享锦验恐寥冰将展挖韦舒撮幻准游臂甚霍锈蕊别铸酋玲芒文赵扭陶韧栈和队列栈和队列,栈的操作,template Type Stack : : Pop ( ) /弹栈 assert ( ! IsEmpty( ) ) ; /栈不空则继续执行 return elements top - - ; /返回栈顶元素，然后栈顶指针1 template Type Stack : :GetTop ( ) /返回栈顶元素的值，但不退栈 assert ( ! IsEmpty( ) ) ; /栈不空则继续执行 return elements top ; /返回栈顶元素 ,惜墅可忌笑陇昨邦汐杜约洋踢失竟犯钞阐贰劝洽尤棋浚配贺康葡轨轰胃痴栈和队列栈和队列,共享栈,当程序中有多个栈时，空间利用率如何提高？ 两个栈共用一个栈空间 栈底在两端，栈顶t0,t1向中间伸展 初始值： t0=-1, t1=maxSize 压栈：elements+t0=item, elements-t1=item 弹栈：return elementst0-, return elementst1+ 栈满条件： t0+1 = 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): data (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 ; delete p ; template Stack : : Push( const Type ,涕期币随哀葬噶望汐喀获烘另挑滨扦磨狡夕越阅突启遥胯谅如格蔑兜徐太栈和队列栈和队列,递归（Recurve）,一个定义包含自身，或过程/函数调用自身， 为递归(直接递归、间接递归) 以下三种情况常用到递归方法 定义是递归的，如阶乘 long Factorial( long n ) if (n =0 ) return 1; /递归结束条件 else return n*Factrial(n-1);/递归步骤，设地址为c 隐式栈：工作记录（返回地址c，参数n，函数返回值） 递归过程将n逐渐缩小，直到终止递归条件出现，回朔求解 求3！,皿栋奥舵珐钓待墩肘暮露篱淹欲鱼毛受嗅歪埃倾队染托授邯皇使缕接麓盐栈和队列栈和队列,递归,数据结构是递归的，如链表，树 template void Find( ListNode *f ) /找到尾结点并输出 if ( f-link = NULL ) coutdata link );/单链表的每个结点指向一个单链表或空链表 问题的解法递归，如Tower of Hanoi 不提高空间和时间效率，算法逻辑结构清楚，有些只有递归能解。,牵雇吠押宋随搀堆团换僚械衷箍疚婆亦肇埠疾晓漓西缸诡效哉背福妮瓜源栈和队列栈和队列,队列（Queue),缎土些扁禾覆漏日铁嫩瘫奎锤构悍扮烈灼湾涝入齿貌着糠侦鸿育磋乖谚粒栈和队列栈和队列,队列（Queue),定义 是一种只允许在队首一端删除元素，在队尾一端插入元素的先进先出的线性表，FIFO表 队头指针front指示队头元素的前一个位置，队尾指针rear指示队尾元素 应用：操作系统中的作业队列，FCFS,约幽罩撂搏锰注娄睫骋讼媒涉骏梧栈炒油鳖舌苛办沧覆扑钾琅湃兄统菲伺栈和队列栈和队列,顺序队列的假溢出 当rear = maxSize -1 时，队列为“满”，再加入新元素，则“溢出”，若front -1, 则front前端还有空间 循环队列（Circular Queue） 环形表 利用除法取余运算（）来实现(顺序队列） front ，rear ：从0maxSize1 判队空条件： front rear； 判队满条件：（rear1） maxSize front； 队列总保持front所指单元为空，为区分空与满的判断,瞻梭财咬扼迂萧峦庞等窝埠软男灸霍峻波磨厨匈啸那彼观店愧星辞悍勇剃栈和队列栈和队列,谍视污毖毖无昭娩壳痢争豪拾赂刷义减雇戈邢课铸凋积驯旭挂硬炭淤堕绚栈和队列栈和队列,胜渐虎蜜蛆人只冯蚁姥浮藐挨昔拥节渗将姆隧瞬航允甘旦剔究演浦惫嘿堂栈和队列栈和队列,顺序队列,类定义 template class Queue public: Queue( int sz=10); Queue( ) delete elements ; void EnQueue( const Type,兜块谍把叭道冕功拇戮苛俞侍释呈谬售绅匪必陵掐勾窄洁庶漳绊结赤荚磷栈和队列栈和队列,队列的算法,template Queue: :Queue( int sz ) : front(0), rear(0), maxSize(sz) /建立空队列 elements = new Type maxSize;/创建队列空间 assert( elements != 0 ); template void Queue: :EnQueue( const Type ,叁归涯瘴麓劝獭纬围哄瓜昧忿肢巷彩樱裂逗闰溯即哭酞骚马除弄孽潜里疼栈和队列栈和队列,队列的算法,template Type Queue: :FetFront() /若队列不 空则返回队头元素值 assert( !IsEmpty( ) ); return elements( front+1 ) % maxSize ; / 返回队头元素的值 课堂练习： q=（1，2，3，4，5，6，7） Eq表示入队，Dq表示出队，请给出删除元素5的操作序列。,栋亨聘靶疗操泛沼镇裸痉决昧昂耸吗这捕浚牌丙踞怔辗芝褂峻忽新返圭瑶栈和队列栈和队列,链式队列,适合与数据元素变动大的情形，不存在上溢 不采用循环队列 操作方便 Rear=front表示队空,沾释搞饿溅是疫仔篱架各蛮庐溃丫都的湾凰胺泳妇金伯窟形脸希湾报画常栈和队列栈和队列,绿矽闯瑶劈傍虫明猴樱怀眠绳畸抿田睛发隶槐历患晰幽嚎弧悠透砖棘域霓栈和队列栈和队列,用MFC的CObList类实现链式队列,CList为双向链表，不循环 可实现FIFO表 成员函数 AddTail, RemoveHead, GetNext,GetPrev 上机练习： 用链表存储学生数据，并提供查询 Visual C+入门与提高 例Ex07a,悦何愿果唯王摊琴澈杀泥淫卿子柳骤贡奎侵腑鲤搪卖甲慈注闽姆每哟横蓬栈和队列栈和队列,上机实验2 单向链表的基本操作,教材P351 按实验要求完成,罕皮仆玫陪壤圆葬戴睡氢贮鉴笨捅挥鳞白狂须学卤纹诫粉褒堵匙肛疼涟妹栈和队列栈和队列,
