链式栈 data next k i+2 用单链表方式存 top 储 ■指针的方向从栈 顶向下链接 k 0 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 链式栈 ki+2 ki+1 ki k0 top data next ◼ 用单链表方式存 储 ◼ 指针的方向从栈 顶向下链接
链式栈的创建 template <class t> class Ink Stack: public Stack <T> I private ∥栈的链式存储 Link<t> ∥/指向栈顶的指针 sIze ∥放元素的个数 public ∥栈运算的链式实现 Ink Stack(int defsize)i ∥/构造函数 top= NULL, size =0 Ink Stack(( ∥析构函数 clear(; “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 链式栈的创建 template <class T> class lnkStack : public Stack <T> { private: // 栈的链式存储 Link<T>* top; // 指向栈顶的指针 int size; // 存放元素的个数 public: // 栈运算的链式实现 lnkStack(int defSize) { // 构造函数 top = NULL; size = 0; } ~lnkStack() { // 析构函数 clear(); } }
压栈操作 ∥栈操作的链式实现 bool Inks Stack<T>:: push(const T item)i Link<T>*tmp= new Link<T>(item, top) top tmp; size++ return true, “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 压栈操作 // 入栈操作的链式实现 bool lnksStack<T>:: push(const T item) { Link<T>* tmp = new Link<T>(item, top); top = tmp; size++; return true; }
出栈操作 ∥出栈操作的链式实现 bool Ink Stack <T>. pop(T& item)( if (size==O) cout<"栈为空,不能执行出栈操作"<endl; return false item= top->data top->next delete top top= tmp; size. return true “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 出栈操作 // 出栈操作的链式实现 bool lnkStack<T>:: pop(T& item) { Link <T> *tmp; if (size == 0) { cout << "栈为空，不能执行出栈操作"<< endl; return false; } item = top->data; tmp = top->next; delete top; top = tmp; size--; return true; }
顺序栈和链式栈的比较 时间效率 口所有操作都只需常数时间 口顺序栈和链式栈在时间效率上难分伯仲 空间效率 口顺序栈须说明一个固定的长度 口链式栈的长度可变,但增加结构性开销 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序栈和链式栈的比较 ◼ 时间效率 ❑ 所有操作都只需常数时间 ❑ 顺序栈和链式栈在时间效率上难分伯仲 ◼ 空间效率 ❑ 顺序栈须说明一个固定的长度 ❑ 链式栈的长度可变，但增加结构性开销