【文章內(nèi)容簡介】 。 } 四川大學 計算機學院 唐寧九 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( )。 } 四川大學 計算機學院 唐寧九 表達式求值 一個表達式由 操作數(shù) (亦稱運算對象 )、 操作符 (亦稱運算符 ) 和 分界符 組成 。 算術表達式有三種表示： 中綴 (infix)表示 操作數(shù) 操作符 操作數(shù) ， 如 A+B。 前綴 (prefix)表示 操作符 操作數(shù) 操作數(shù) ， 如 +AB。 后綴 (postfix)表示 操作數(shù) 操作數(shù) 操作符 ， 如 AB+； 四川大學 計算機學院 唐寧九 Section 2 Queue 四川大學 計算機學院 唐寧九 隊列 ( Queue ) 定義 ?隊列是只允許在一端刪除，在另一端插入的順序表 ?允許刪除的一端叫做隊頭 (front)，允許插入的一端叫做隊尾 (rear)。 特性 ?先進先出 (FIFO, First In First Out) a0 a1 a2 an1 front rear ?? 四川大學 計算機學院 唐寧九 ADT Queue { 數(shù)據(jù)對象： D＝ {ai | ai∈ ElemSet, i=1,2,...,n, n≥0} 數(shù)據(jù)關系： R1＝ { a i1,ai | ai1, ai ∈ D, i=2,...,n} 約定其中 a1 端為 隊列頭 ， an 端為 隊列尾 基本操作： 隊列的抽象數(shù)據(jù)類型定義 } 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的元素個 數(shù)，即隊列的長 度。 四川大學 計算機學院 唐寧九 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