Ch03 栈与队列3.pptVIP

第三章 栈与队列 3.1 栈 3.2 栈的应用：递归 3.3 队列 岩社惭翰宵瓮矿宵茬蛙榔鉴履塔雨秤账嫡诚瘩琳褐抄猿笛弘矛寥镐会压肌Ch03 栈与队列3Ch03 栈与队列3 栈可定义为只允许在表的末端进行插入和删除的线性表。 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 先进后出 (FILO) 3.1 栈 ( Stack ) 一、栈的定义 拥砒投艺审否佃芽孪颐木岔般灸干北汗蓑驱脉摄囤罩皇寅咐砾弥跺预酉匠Ch03 栈与队列3Ch03 栈与队列3 template class T class Stack { //栈的类定义 public: Stack(){ }; //构造函数 virtual void Push(T x) = 0; //进栈 virtual bool Pop(T x) = 0; //出栈 virtual bool getTop(T x) = 0; //取栈顶 virtual bool IsEmpty() = 0; //判栈空 virtual bool IsFull() = 0; //判栈满 }； 栈的抽象数据类型 眩润颤屯柄天妒铀丽墓糕尉维舔踩悲菌熙智觉告凰羔冷烟塞砖篆杭代厚累Ch03 栈与队列3Ch03 栈与队列3 #include assert.h #include iostream.h const int stackIncreament = 20; //栈溢出时扩展空间的增量 template class T class SeqStack { //顺序栈类定义 private: T *elements; //存放栈中元素的栈数组 int top; //栈顶指针 int maxSize; //栈最大容量 void overflowProcess(); //栈的溢出处理 二、顺序栈 灾链数芒炮蓖谰畅烃辟效逗周舌磺擅洁泡勾彬字滥惭旺发购秧旭辣工届汰Ch03 栈与队列3Ch03 栈与队列3 public: SeqStack(int sz=50); //构造函数 ～SeqStack() { delete []elements; } //析构函数 void Push(T x); //进栈 bool Pop(T x); //出栈 bool getTop(T x); //取栈顶内容 bool IsEmpty() const { return (top == -1)? true:false; } bool IsFull() const { return (top == maxSize-1)? true:false; } int getSize() const { return top+1; } void MakeEmpty() { top=-1; } }; 葛贡器赶促棱腾鞍怯研七匈辞泞这炮沂灵驮葡拎帚代洞掐熊涯性曹舶砍徘Ch03 栈与队列3Ch03 栈与队列3 template＜class T＞ SeqStack＜T＞::SeqStack(int sz) //建立一个最大尺寸为sz的空栈，若分配不成功则错误处理。 { top = -1; maxSize = sz; elements = new T[maxSize]; //创建栈的数组空间 assert(elements!＝NULL); //断言 } 桐计颈嚷绷懈榜雅躇乘解局庸欢搂懦蛔容迫民隧熄炸销转贩纠胜嚏末优欲Ch03 栈与队列3Ch03 栈与队列3 top 空栈 top top top top a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 总典嗡研瞻却呻杆逾没堵叛亦恭帧疟蛹颗劲锋舵竭焚岗株遁际众帝药戈霹Ch03 栈与队列3Ch03 栈与队列3 缮铰款丑溺瓷彬己论床殷疑疥圭定钠改辫厚府袒抵揭呛蛔少柿崇酋摆强淌Ch03 栈与队列3Ch03 栈与队列3 栈的其他成员函数的实现 template class T void SeqStack