數據結構-隊列的鏈式實現

數據結構-隊列的鏈式實現

隊列的鏈式實現

1 隊列的鏈式存儲表示
隊列的鏈式存儲結構簡稱為鏈隊列，它是限制在表頭進行刪除操作和表尾進行插入操作的單鏈表。
需要兩類不同的結點：數據元素結點，隊列的隊首指針和隊尾指針的結點
指針結點類型定義：

typedef struct link_queue
{   QNode  *front ,  *rear ;
}LinkQueue ;

2 鏈隊運算及指針變化
鏈隊的操作實際上是單鏈表的操作，只不過是刪除在表頭進行，插入在表尾進行。插入、刪除時分別修改不同的指針

3    鏈隊列的基本操作
⑴ 鏈隊列的初始化
Status Init_LinkQueue(LinkQueue  *Q )
{   /*成功返回OK，否則返回ERROR*/
   QNode  *p ;
p=(QNode *)malloc(sizeof(QNode)) ; /* 開辟頭結點 */
if(p==NULL) return ERROR;
p->next=NULL ;
Q->front=Q->rear=p ; 
return OK;
}

⑵ 鏈隊列的入隊操作
       在已知隊列的隊尾插入一個元素e ，即修改隊尾指針(Q.rear)。
Status  Insert_LinkQueue(LinkQueue  *Q , ElemType  e)
      /*  將數據元素e插入到鏈隊列Q的隊尾  */
{  QNode  *p ;
   p=(QNode *)malloc(sizeof(QNode)) ;
if (!p)  return  ERROR;
/*  申請新結點失敗，返回錯誤標志 */
p->data=e ; p->next=NULL ;       /*  形成新結點 */
Q->rear->next=p ;  Q->rear=p ;  /* 新結點插入到隊尾  */
return OK;
}

鏈隊列的出隊操作
Status  Delete_LinkQueue(LinkQueue  *Q, ElemType *x)
   {   QNode *p ;
if  (Q->front==Q->rear)  return ERROR ;   /* 隊空  */
p=Q->front->next ;   /*  取隊首結點  */
*x=p->data ; 
Q->front->next=p->next ;      /*  修改隊首指針  */
if  (p==Q->rear)  Q->rear=Q->front ;
     /*  當隊列只有一個結點時應防止丟失隊尾指針  */
    free(p) ;   
return OK ; 
}

⑷ 鏈隊列的撤消
void  Destroy_LinkQueue(LinkQueue  *Q )
   /*  將鏈隊列Q的隊首元素出隊  */
{   while  (Q->front!=NULL)
{Q-> rear= Q-> front->next;   
      /*  令尾指針指向隊列的第一個結點   */
free(Q-> front);      /*  每次釋放一個結點  */ 
    /*  第一次是頭結點，以後是元素結點  */
Q-> front= Q-> rear;
}
}