template <class E> class LinkedStack:public Stack<E>{/链式栈类定义 private: StackNode<E>*top; /栈顶指针 public: LinkedStack():top(NULL) /构造函数 ~LinkedStack){makeEmpty();}∥析构函数 void Push(E x); 川进栈 bool PopE&x); /退栈 16
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 IsEmpty(const return top ==NULL;} void makeEmpty(); 清空栈的内容 friend ostream&operator <(ostream&os, LinkedStack<E>&s); /输出栈元素的重载操作<< }; 17
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>: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); /创建失败退出 18
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) /川删除栈顶结点，返回被删栈顶元素的值。 if(IsEmpty()==true)return false;/∥栈空返回 StackNode<E>*p=top; /暂存栈顶元素 top top->link; /退栈顶指针 x=p->data; delete p; /释放结点 return true; ; 19
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 if(IsEmpty()=true)return false;l∥栈空返回 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; };