【正文】 ve_and_retrieve ( Queue_entry amp。 Post: All entries in the queue have been removed。 Post: Return true if the queue is full。 Post: If the Queue is not empty, the front of the Queue has been recorded as x. Otherwise an Error_code of underflow is returned. 四川大學(xué) 計算機學(xué)院 唐寧九 bool Queue :: empty( ) const。 Post: If the Queue is not empty, the front of the Queue has been removed. Otherwise an Error_code of underflow is returned. 四川大學(xué) 計算機學(xué)院 唐寧九 Error_code Queue :: retrieve(Queue_entry amp。x)。 a1 a2 an … … 四川大學(xué) 計算機學(xué)院 唐寧九 DEFINITION A queue of elements of type T is a finite sequence of elements of T together with the following operations: 四川大學(xué) 計算機學(xué)院 唐寧九 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. 四川大學(xué) 計算機學(xué)院 唐寧九 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. 四川大學(xué) 計算機學(xué)院 唐寧九 Queue :: Queue( )。x) 初始條件： Q為非空隊列。 a1 a2 an x … … 四川大學(xué) 計算機學(xué)院 唐寧九 DeQueue(amp。Q, x) 初始條件： 隊列 Q已存在。 操作結(jié)果： 將 Q清為空隊列。 a1 a2 an … … 四川大學(xué) 計算機學(xué)院 唐寧九 ClearQueue(amp。x) 初始條件： Q為非空隊列。 操作結(jié)果： 返回 Q的元素個 數(shù)，即隊列的長 度。 操作結(jié)果： 若 Q為空隊列，則 返回 TRUE，否則 返回 FALSE。 操作結(jié)果： 隊列 Q被銷毀， 不再存在。 DestroyQueue(amp。Q, x) 四川大學(xué) 計算機學(xué)院 唐寧九 InitQueue(amp。Q, amp。x) ClearQueue(amp。Q) DestroyQueue(amp。 后綴 (postfix)表示 操作數(shù) 操作數(shù) 操作符 ， 如 AB+； 四川大學(xué) 計算機學(xué)院 唐寧九 Section 2 Queue 四川大學(xué) 計算機學(xué)院 唐寧九 隊列 ( Queue ) 定義 ?隊列是只允許在一端刪除，在另一端插入的順序表 ?允許刪除的一端叫做隊頭 (front)，允許插入的一端叫做隊尾 (rear)。 算術(shù)表達式有三種表示： 中綴 (infix)表示 操作數(shù) 操作符 操作數(shù) ， 如 A+B。 } 四川大學(xué) 計算機學(xué)院 唐寧九 Stack :: ~Stack( ) { while (!empty( )) pop( )。 delete old_top。 if (top_node == NULL) return underflow。 return success。 if (new_top == NULL) return overflow。 四川大學(xué) 計算機學(xué)院 唐寧九 Error_code Stack :: push(const Stack _entry amp。 protected: Node *top node。 Error_code top(Stack_entry amp。item)。 bool empty( ) const。 next = add_on。 四川大學(xué) 計算機學(xué)院 唐寧九 Node :: Node( ) { next = NULL。 Node(Node_entry item, Node *add_on = NULL)。 Node *next。 return 1。 x ) { if ( IsEmpty ( ) ) return 0。 return 1。 x = pdata。 StackNodeType *p = top。 } 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type int StackType::Pop ( Type amp。 delete p。 while ( top != NULL ) { p = top。//實現(xiàn)與 ~Stack()同 int IsEmpty (){ return top == NULL。 x )。 x )。 四川大學(xué) 計算機學(xué)院 唐寧九 void Push ( Type x )。 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type class Stack { private: StackNodeType *top。 StackNodeType *link。 template class Type class StackNode { friend class StackType。 } 四川大學(xué) 計算機學(xué)院 唐寧九 Stack :: Stack( ) { count = 0。 if (count 0) oute = false。 return oute。 if (count == 0) oute = underflow。 } 四川大學(xué) 計算機學(xué)院 唐寧九 Error_code Stack :: top(Stack_entry amp。 else count。 } 四川大學(xué) 計算機學(xué)院 唐寧九 Error_code Stack :: pop( ) { Error_code oute = success。 else entry[count++] = item。item) { Error_code oute = success。 }。 四川大學(xué) 計算機學(xué)院 唐寧九 private: int count。 Error_code push(const Stack_entry amp。 Error_code top(Stack_entry amp。 bool empty( ) const。 } 四川大學(xué) 計算機學(xué)院 唐寧九 雙棧共享一個?？臻g b[0] t[0] t[1] b[1] 0 maxSize1 V 四川大學(xué) 計算機學(xué)院 唐寧九 Contiguous Stack 四川大學(xué) 計算機學(xué)院