【正文】 } 。 delete old_front。 front = old_frontnext。 } 四川大學(xué) 計算機學(xué)院 唐寧九 Error_code Queue :: serve( ){ if (front == NULL) return underflow。 rear = new_rear。 if (rear==NULL)front=rear=new_rear。item){ Node *new_rear=new Node(item)。 四川大學(xué) 計算機學(xué)院 唐寧九 Queue :: Queue( ) { front = rear = NULL。 protected: Node *front, *rear。item) const。 Error_code serve( )。 Error_code append(const Queue _entry amp。 } 四川大學(xué) 計算機學(xué)院 唐寧九 Linked Queues 四川大學(xué) 計算機學(xué)院 唐寧九 四川大學(xué) 計算機學(xué)院 唐寧九 class Queue { public: Queue( )。 x=frontdata。 } 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type int QueueType::GetFront(Type amp。 delete p。 front=frontlink。 x){ if ( IsEmpty ( ) ) return 0。 rear=rearlink。 } } 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type void QueueType :: EnQueue ( Type x ) { if ( front == NULL ) front=rear=newQueueNodeType(x)。 front = frontlink。 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type QueueType :: ~Queue ( ) { QueueNodeType *p。 //實現(xiàn)與 ~Queue()同 int IsEmpty ( ) const { return front == NULL。 x )。 x )。 四川大學(xué) 計算機學(xué)院 唐寧九 void EnQueue ( Type x )。 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type class Queue { private: QueueNodeType *front, *rear。 QueueNodeType *link。 template class Type class QueueNode { friend class QueueType。 ? 鏈式隊列在進隊時無隊滿問題，但有隊空問題。 return success。item) const { if (count = 0) return underflow。 return success。 count。 return success。 rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1)。item) { if (count = maxqueue) return overflow。 } 四川大學(xué) 計算機學(xué)院 唐寧九 bool Queue :: empty( ) const { return count == 0。 rear = maxqueue 1。 }。 int front, rear。item) const。item)。 Error_code serve( )。 class Queue { public: Queue( )。 Return 1。 return 0。 } 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type int QueueType::GetFront( Type amp。 x = elements[front]。 x ) { if ( IsEmpty ( ) ) return 0。 return 1。 rear = (rear+1) % MaxSize。 ?隊滿條件： (rear+1) % maxSize == front 循環(huán)隊列 (Circular Queue) 四川大學(xué) 計算機學(xué)院 唐寧九 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front rear A A B C rear rear 空隊列 A進 隊 B, C進 隊 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A退 隊 B退 隊 0 1 2 3 4 5 6 7 D,E,F,G,H進 隊 front B C rear A front B C rear front C rear D E F G H 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type QueueType::Queue( int sz ) : front (1), rear (1), maxSize (sz) { elements = new Type[maxSize]。 ?隊列初始化： front = rear = 0。 ?隊頭指針進 1: front = (front+1) % maxSize。 四川大學(xué) 計算機學(xué)院 唐寧九 ? 隊列存放數(shù)組被當作首尾相接的表處理。 ? 隊滿時再進隊將 溢出出錯 ； ? 隊空時再出隊將 隊空處理 。} } 四川大學(xué) 計算機學(xué)院 唐寧九 隊列的進隊和出隊 front rear 空隊列 front rear A進隊 A front rear B進隊 A B front rear C, D進隊 A B C D front rear A退隊 B C D front rear B退隊 C D front rear E,F,G進 隊 C D E F G C D E F G front rear H進 隊 ,溢出 四川大學(xué) 計算機學(xué)院 唐寧九 隊列的進隊和出隊原則 ? 進隊時隊尾指針先進一 rear=rear+1， 再將新元素按 rear 指示位置加入。 } int IsFull ( ) const { return (rear+1) % maxSize == front。 void MakeEmpty ( ) { front = rear。 int GetFront ( Type amp。 四川大學(xué) 計算機學(xué)院 唐寧九 int DeQueue ( Type amp。 ~Queue ( ) { delete [ ]elements。 int maxSize。 Post: Return underflow if the queue is empty. Otherwise remove and copy the item at the front of the queue to item and return success. 四川大學(xué) 計算機學(xué)院 唐寧九 循環(huán)隊列 (Circular Queue) 四川大學(xué) 計算機學(xué)院 唐寧九 template class Type class Queue { private: int rear, front。 Post: Return the number of entries in the queue. 四川大學(xué) 計算機學(xué)院 唐寧九 Error_code Queue :: ser