template <class e> class linkedstack: public stack<E>{/链式栈类定义 private: StackNode<e> *top; /栈顶指针 public: Linkedstack0:top(NUL)各∥构造函数 Linkedstack({ make Empty;}∥构函数 void Push(e x) 进栈 bool pop(e& x); 退栈
16 template <class E> class LinkedStack : public Stack<E> { //链式栈类定义 private: StackNode<E> *top; //栈顶指针 public: LinkedStack() : top(NULL) {} //构造函数 ～LinkedStack() { makeEmpty(); } //析构函数 void Push(E x); //进栈 bool Pop(E& x); //退栈
bool gettop(e& x) const ∥取栈顶 bool Is Empty const return top== nUll; void makeempty(: 清空栈的内容 friend ostream& operator <<(ostream& os LinkedStack<E> &s); /出栈元素的重载操作<<
17 bool getTop(E& x) const; //取栈顶 bool IsEmpty() const { return top == NULL; } void makeEmpty(); //清空栈的内容 friend ostream& operator << (ostream& os, LinkedStack<E> & s) ; //输出栈元素的重载操作 << };
链式栈类操作的实现 template <class e> LinkedStack<E>: make Empty t 逐次删去链式栈中的元素直至栈顶指针为空。 Stacknode<e> x while(top != NULL) /逐个结点释放 &p=top; top=top->link; delete p; template <class e> void LinkedStack<E> Push(e x)( /将元素值X插入到链式栈的栈顶.即链头 top= new StackNode<E>(x,top);∥创建新结点 asse rt top !=null); ∥创建失败退出
18 链式栈类操作的实现 template <class E> LinkedStack<E>::makeEmpty() { //逐次删去链式栈中的元素直至栈顶指针为空。 StackNode<E> *p; while (top != NULL) //逐个结点释放 { p = top; top = top->link; delete p; } }; template <class E> void LinkedStack<E>::Push(E x) { //将元素值x插入到链式栈的栈顶,即链头 top = new StackNode<E> (x, top); //创建新结点 assert (top != NULL); //创建失败退出 };
template <class e> bool linkedstack<E>: Pop(e& x)i 删除栈顶结点,返回被删栈顶元素的值。 f( IsEmpty(=true) return false;/栈空返回 StackNodee> p= top 存栈顶元素 top=top->link; 退栈顶指针 x=p->datas d elete p; 释放结点 return true;
19 template <class E> bool LinkedStack<E>::Pop(E& x) { //删除栈顶结点, 返回被删栈顶元素的值。 if (IsEmpty() == true) return false; //栈空返回 StackNode<E> *p = top; //暂存栈顶元素 top = top->link; //退栈顶指针 x = p->data; delete p; //释放结点 return true; };
template <class e> bool LinkedStack<E>: :getTop (e& x)const i if( eMpty(=tue) return false;/栈空返回 X= top->data: 回栈顶元素的值 return true; 20
20 template <class E> bool LinkedStack<E>::getTop(E& x) const { if (IsEmpty() == true) return false; //栈空返回 x = top->data; //返回栈顶元素的值 return true; };