chapter3stackqueue

chapter3stackqueue内容摘要：

} 四川大学 计算机学院 唐宁九 template class Type int StackType::GetTop ( Type amp。 x ) { if ( IsEmpty ( ) ) return 0。 x = topdata。 return 1。 } 四川大学 计算机学院 唐宁九 Linked Stacks 四川大学 计算机学院 唐宁九 四川大学 计算机学院 唐宁九 四川大学 计算机学院 唐宁九 struct Node { Node entry_entry。 Node *next。 Node( )。 Node(Node_entry item, Node *add_on = NULL)。 }。 四川大学 计算机学院 唐宁九 Node :: Node( ) { next = NULL。 } 四川大学 计算机学院 唐宁九 Node :: Node(Node_entry item, Node *add_ on) { entry = item。 next = add_on。 } 四川大学 计算机学院 唐宁九 class Stack { public: Stack( )。 bool empty( ) const。 Error_code push(const Stack_entry amp。 item)。 四川大学 计算机学院 唐宁九 Error_code pop( )。 Error_code top(Stack_entry amp。 item) const。 protected: Node *top node。 }。 四川大学 计算机学院 唐宁九 Error_code Stack :: push(const Stack _entry amp。 item) { Node *new_top = new Node(item, top_node)。 if (new_top == NULL) return overflow。 top_node = new_top。 return success。 } 四川大学 计算机学院 唐宁九 Error_code Stack :: pop( ) { Node *old_top = top_node。 if (top_node == NULL) return underflow。 top_node = old_topnext。 delete old_top。 return success。 } 四川大学 计算机学院 唐宁九 Stack :: ~Stack( ) { while (!empty( )) pop( )。 } 四川大学 计算机学院 唐宁九 表达式求值 一个表达式由 操作数 (亦称运算对象 )、 操作符 (亦称运算符 ) 和 分界符 组成。 算术表达式有三种表示： 中缀 (infix)表示 操作数 操作符 操作数 ， 如 A+B。 前缀 (prefix)表示 操作符 操作数 操作数 ， 如 +AB。 后缀 (postfix)表示 操作数 操作数 操作符 ， 如 AB+； 四川大学 计算机学院 唐宁九 Section 2 Queue 四川大学 计算机学院 唐宁九 队列 ( Queue ) 定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头 (front)，允许插入的一端叫做队尾 (rear)。 特性 先进先出 (FIFO, First In First Out) a0 a1 a2 an1 front rear  四川大学 计算机学院 唐宁九 ADT Queue { 数据对象： D＝ {ai | ai∈ ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝ { a i1,ai | ai1, ai ∈ D, i=2,...,n} 约定其中 a1 端为 队列头 ， an 端为 队列尾 基本操作： 队列的抽象数据类型定义 } ADT Queue 四川大学 计算机学院 唐宁九 队列的基本操作： InitQueue(amp。 Q) DestroyQueue(amp。 Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, amp。 x) ClearQueue(amp。 Q) DeQueue(amp。 Q, amp。 x) EnQueue(amp。 Q, x) 四川大学 计算机学院 唐宁九 InitQueue(amp。 Q) 操作结果： 构造一个空队列 Q。 DestroyQueue(amp。 Q) 初始条件： 队列 Q已存在。 操作结果： 队列 Q被销毁， 不再存在。 四川大学 计算机学院 唐宁九 QueueEmpty(Q) 初始条件： 队列 Q已存在。 操作结果： 若 Q为空队列，则 返回 TRUE，否则 返回 FALSE。 四川大学 计算机学院 唐宁九 QueueLength(Q) 初始条件： 队列 Q已存在。 操作结果： 返回 Q的元素个 数，即队列的长 度。 四川大学 计算机学院 唐宁九 GetHead(Q, amp。 x) 初始条件： Q为非空队列。 操作结果： 用 x返回 Q的队头 元素。 a1 a2 an … … 四川大学 计算机学院 唐宁九 ClearQueue(amp。 Q) 初始条件： 队列 Q已存在。 操作结果： 将 Q清为空队列。 四川大学 计算机学院 唐宁九 EnQueue(amp。 Q, x) 初始条件： 队列 Q已存在。 操作结果： 插入元素 x为 Q的 新的队尾元素。 a1 a2 an x … … 四川大学 计算机学院 唐宁九 DeQueue(amp。 Q, amp。 x) 初始条件： Q为非空队列。 操作结果： 删除 Q的队头元 素，并用 x返回 其值。 a1 a2 an … … 四川大学 计算机学院 唐宁九 DEFINITION A queue of elements of type T is a finite sequence of elements of T together with the following operations: 四川大学 计算机学院 唐宁九 1. Create the queue, leaving it empty. 2. Test whether the queue is Empty. 3. Append a new entry onto the rear of the queue, provided the queue is not full. 四川大学 计算机学院 唐宁九 4. Serve (and remove) the entry from the front of the queue, provided the queue is not empty. 5. Retrieve the front entry off the queue, provided the queue is not empty. 四川大学 计算机学院 唐宁九 Queue :: Queue( )。 Post: The Queue has been created and is initialized to be empty. 四川大学 计算机学院 唐宁九 Error_code Queue :: append(const。