2010数据结构实验指导书48

};

virtual void enqueue (const Object&) = 0; virtual void dequeue (Object&) = 0; virtual void dequeue () = 0;

virtual const Object& front () const = 0; virtual bool empty () const = 0;

出队函数dequeue()有2个原型，如Queue<int>Q; int x; x = Q.front(); Q.dequeue (); 等价于Q.dequeue(x); 前面的用法符合STL的习惯，后面一个有时会觉得方便，所以2个都放在接口里。

*实验课题三： 将一个普通代数表达式（infix expression）转换为后缀表达式（postfix expression）。转换规则描述参见：描述C语言描述的课本pp.68-71，C++语言描述的课本pp.99-102。

栈的ADT接口：

用C++描述的教科书中没给栈的ADT，可以用以下Stack类模版： template <typename Object> class Stack { public:

bool empty( ) const { return theList.empty( ); } const Object & top( ) const { return theList.front( ); } void push( const Object & x ) { theList.push_front( x ); } void pop( Object & x )

{ x = theList.front( ); theList.pop_front( ); } void pop( )

{ theList.pop_front( ); } private:

List<Object> theList; };

在本实验中，也只用＋、＊、（、）作为算符，优先级自低至高为＋、*、（）。

实验三 队列

【实验目的】

1、 掌握队列的FIFO的特点（先进先出）特点和队列的存储结构； 2、熟悉队列的各种操作；