32队列.pptVIP

第三章 栈和队列 队列(Queue)定义和概念 队列：在一端插入，在另一端删除操作的线性表； 是操作受限制的线性表； 概念： 队尾rear：插入端，线性表的表尾。 队头front：删除端，线性表的表头。 队列(Queue)图示 FIFO（First In First Out） 队列的ADT ADT Queue { 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R={ai-1,ai|ai,ai-1∈D,i=2,…,n} 约定:a1为队列头，an为队列尾 基本操作： InitQueue( Q ); // 初始化空队列 DestroyQueue( Q ); // 销毁队列 ClearQueue( Q ); // 清空队列 QueueEmpty( Q ); // 队列空？ QueueLength( Q ); // 队列长度 GetHead( Q, e ); // 取对头元素 EnQueue( Q, e ); // 入队列 DeQueue( Q, e ); // 出队列 QueueTraverse( Q, visit( )); // 遍历 }// ADT Queue; 队列的其他形式_双端队列Deque 队列的其他形式_双端队列Deque 队列的表示和实现 两种 链式存贮结构__链队列； 顺序存贮结构__循环队列； 链队列_C表示 typedef struct QNode { QElemType data; struct QNode *pNext; }QNode, *QueuePtr; // 结点 typedef struct { QueuePtr pFornt; // 队头指针 QueuePtr pRear; // 队尾指针 }LinkQueue; 链队列_C表示 LinkQueue q; q.pFront = NULL; q.pRear = NULL; 链队列_InitQueue // 初始化一个空队列 Status InitQueue( LinkQueue Q ) { Q.pFront = Q.pRear = (QueuePtr )malloc( sizeof( QNode )); if( !Q.pFront ) { return OVERFLOW; } Q.pFront-pNext = NULL; }// InitQueue 链队列_DestroyQueue // 销毁队列 Status DestroyQueue( LinkQueue Q) { p = Q.pFront-pNext; //p指向对列的第一个结点 while( p ) { Q.pFront-pNext = p-pNext; // 删除第一个结点 free( p ); p = Q.pFront-pNext; } free( Q.pFront ); Q.pFront = Q.pRear = NULL; return OK; }// DestroyQueue 链队列_DestroyQueue // 销毁队列 Status DestroyQueue( LinkQueue Q) { while( Q.pFront ) { Q.pRear = Q.pFront-pNext; free( Q.pFront ); Q.pFront = Q.pRear; } return OK; }// DestroyQueue 链队列_ClearQueue // 清空队列 Status ClearQueue( LinkQueue Q ) { p = Q.pFront-pNext; //p指向对列的第一个结点 while( p ) { Q.pFront-pNext = p-pNext; // 删除第一个结点 free( p ); p = Q.pFront-pNext; } return OK; } 链队列_QueueLength // 取链队列的长度 int QueueLength( LinkQueue Q ) { k = 0; p = Q.pFront-pNext; while( p ) { k++; } return k; } 链队列_GetHead // 取队列的头元素 Status GetHead( LinkQueue Q, QElemType e ) { if( Q.pFront-pNext ) { e = Q.pFront-pNext-data; return OK; } return ERROR; } 链队列_EnQueue // 入