链式栈( Linked stack)类的定义 template <class Type> class Stack template <class Type> class StackNode i friend class Stack<Type> private. Type data ∥/结点数据 StackNode<ype>link;∥结点链指针 publica StackNode( Type d=0, StackNode<Type> "1-NULL ) data (d), link(1)
template <class Type> class Stack; template <class Type> class StackNode { friend class Stack<Type>; private: Type data; //结点数据 StackNode<Type> *link; //结点链指针 public: StackNode ( Type d = 0, StackNode<Type> *l = NULL ) : data ( d ), link ( l ) { } }; 链式栈 (LinkedStack)类的定义
template <class Type> class Stack t private StackNode<ype>*top;∥栈顶指针 p ublic. Stack(): top(NULL)& Stack (; void push( const Type&item);∥进栈 int Pop (; 退栈 Type GetTop();∥读取栈顶元素 void MakeEmpty();∥实现与~ Stack()同 int IsEmpty(i return top=-NULL; 3
template <class Type> class Stack { private: StackNode<Type> *top; //栈顶指针 public: Stack ( ) : top ( NULL ) { } ~Stack ( ); void Push ( const Type & item); //进栈 int Pop ( ); //退栈 Type *GetTop ( ); //读取栈顶元素 void MakeEmpty ( ); //实现与~Stack( )同 int IsEmpty ( ) { return top == NULL; } }
template <class Type> Stack<Type>:: Stack(( StackNode<Type>*p; while(topl=NULL)逐结点回收 ip=top; top=top->link; delete p;) template <class Type> void Stack<Type>:: Push( const Type &item )t top= new StackNode<Type>( item, top )i ∥新结点链入*top之前,并成为新栈顶
template <class Type> Stack<Type> :: ~Stack ( ) { StackNode<Type> *p; while ( top != NULL ) //逐结点回收 { p = top; top = top->link; delete p; } } template <class Type> void Stack<Type> :: Push ( const Type &item ) { top = new StackNode<Type> ( item, top ); //新结点链入*top之前, 并成为新栈顶 }
template <class Type> int Stack<Type>:: Pop(i if( IsEmpty ( return 0 Stack Node<Type>>p= top; top= top->link //修多改栈顶指针 delete p; return 1 ∥释放 template <class Type> Type Stack<Type> GetTop(i assert(! IsEmpty (); return top->data
template <class Type> int Stack<Type> :: Pop ( ) { if ( IsEmpty ( ) ) return 0; StackNode<Type> *p = top; top = top->link; //修改栈顶指针 delete p; return 1; //释放 } template <class Type> Type Stack<Type>:: GetTop ( ) { assert ( !IsEmpty ( ) ); return top->data; }
表达式求值 个表达式由操作数(亦称运算对象、操 作符(亦称运算符)和分界符组成 算术表达式有三种表示 中缀infx)表示 <操作数><操作符><操作数>,如A+B 前缀 prefix)表示 操作符><操作数><操作数>,如+AB; ◆后缀 postfix)表示 <操作数><操作数><操作符>,如AB+
表达式求值 ◼ 一个表达式由操作数(亦称运算对象)、操 作符 (亦称运算符) 和分界符组成。 ◼ 算术表达式有三种表示： ◆ 中缀(infix)表示 <操作数> <操作符> <操作数>，如 A+B； ◆ 前缀(prefix)表示 <操作符> <操作数> <操作数>，如 +AB； ◆ 后缀(postfix)表示 <操作数> <操作数> <操作符>，如 AB+；