隊列使用單鏈表實現(xiàn)，另外設置兩個指針一個指向隊首，一個指向隊尾。如果直接使用以前的帶頭節(jié)點的單鏈表，取隊尾元素和入隊的時間復雜度是O(N)。雖然可以采用循環(huán)鏈表，只設置一個指向尾節(jié)點的指針來解決，但是不是很好理解，所以我還是使用兩個指針來實現(xiàn)^_^，代碼比較簡單

/********************************************************************
    created:    2005/12/25
    created:    25:12:2005   9:41
    filename:     queue.h
    author:        Liu Qi, ngaut#126.com
    
    purpose:    鏈隊列的定義與實現(xiàn)
*********************************************************************/

#ifndef QUEUE_H
#define QUEUE_H


#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include <assert.h>


typedef int ElemType;


typedef struct
{
    ElemType Element;
    struct Node* Next;
} Node;

typedef Node* PNode;


typedef struct
{
   PNode front;
   PNode rear;
} Queue;


/*===========================================================================
* Function name:    MakeNode
* Parameter:        target:元素的值
* Precondition:        void
* Description:        構造一個節(jié)點，其值為target，Next為NULL
* Return value:        指向新節(jié)點的指針
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
static PNode MakeNode(ElemType target)
{
    PNode PNewNode = (PNode) malloc(sizeof(Node));

    assert( NULL != PNewNode ); 

    PNewNode->Element = target;
    PNewNode->Next     = NULL;

    return PNewNode;
}


/*===========================================================================
* Function name:    Q_Create
* Parameter:        void
* Precondition:        void
* Description:        創(chuàng)建一個隊列
* Return value:        指向隊列的指針
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
Queue* Q_Create( void )
{
    Queue *Q = (Queue *) malloc(sizeof(Queue));

    assert( NULL != Q ); 

    Q->front = NULL;
    Q->rear     = NULL;

    return Q;
}


/*===========================================================================
* Function name:    Q_IsEmpty
* Parameter:        QPtr:指向隊列的指針
* Precondition:        NULL != QPtr
* Description:        判斷隊列是否為空
* Return value:        true：隊列為空，false：隊列不空
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
bool Q_IsEmpty(Queue* QPtr)
{
    assert( NULL != QPtr ); 

    return (NULL == QPtr->front) ? true : false;
}



/*===========================================================================
* Function name:    Q_PushBack
* Parameter:        target：要入隊的元素，QPtr:指向隊列的指針
* Precondition:        NULL != QPtr
* Description:        入隊
* Return value:        void
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
void Q_PushBack(ElemType target, Queue* QPtr)
{
    PNode PNewNode = MakeNode(target);

    assert( NULL != QPtr ); 
    
    if ( !Q_IsEmpty(QPtr))    //隊列不為空，直接鏈接到隊列尾部
    {
        QPtr->rear->Next = PNewNode;
        QPtr->rear = PNewNode;
    }
    else
    {    //隊列為空
        QPtr->front = PNewNode;
        QPtr->rear = PNewNode;
    }
}



/*===========================================================================
* Function name:    Q_PopFront
* Parameter:        QPtr:指向隊列的指針
* Precondition:        NULL != QPtr && !Q_IsEmpty(QPtr)
* Description:        從隊首出隊
* Return value:        元素的值
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
void Q_PopFront(Queue *QPtr)    
{
    PNode PTmp;

    assert( NULL != QPtr && !Q_IsEmpty(QPtr)); 

    PTmp = QPtr->front;
    QPtr->front = PTmp->Next;
    free(PTmp);
}


/*===========================================================================
* Function name:    Q_Front
* Parameter:        QPtr:指向隊列的指針
* Precondition:        NULL != QPtr && !Q_IsEmpty(QPtr)
* Description:        返回隊首的第一個元素的值
* Return value:        隊首的第一個元素的值
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
ElemType Q_Front(Queue *QPtr)    //個人覺得該函數(shù)返回指針更具通用性
{
    assert( NULL != QPtr && !Q_IsEmpty(QPtr) ); 

    return QPtr->front->Element;
}


/*===========================================================================
* Function name:    Q_Back
* Parameter:        QPtr:指向隊列的指針
* Precondition:        NULL != QPtr && !Q_IsEmpty(QPtr)
* Description:        返回隊尾最后一個元素的值
* Return value:        隊尾最后一個元素的值
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
ElemType Q_Back(Queue *QPtr)    //個人覺得該函數(shù)返回指針更具通用性
{
    assert( NULL != QPtr && !Q_IsEmpty(QPtr) ); 

    return QPtr->rear->Element;
}


/*===========================================================================
* Function name:    Q_Destory
* Parameter:        QPtr:指向隊列的指針
* Precondition:        NULL != QPtr
* Description:        銷毀隊列，并釋放空間
* Return value:        void
* Author:            Liu Qi,  [12/25/2005]
===========================================================================*/
void Q_Destory(Queue *QPtr)
{
    assert( NULL != QPtr ); 

    while ( !Q_IsEmpty(QPtr) )
    {
        Q_PopFront(QPtr);
    }

    free(QPtr);
}

#endif


測試代碼如下：
#include <stdio.h>
#include "queue.h"


#define MAX_CNT 10

int main()
{
    int i;

    Queue *QPtr = Q_Create();

    for (i = 0; i < MAX_CNT; i++)
    {
        Q_PushBack(i, QPtr);
        printf("Q->front: %d\n", Q_Front(QPtr));
        printf("Q->rear:  %d\n", Q_Back(QPtr));
    }

    printf("\n");

    for (i = 0; i < MAX_CNT; i++)
    {
        Q_PopFront(QPtr);
        if ( !Q_IsEmpty(QPtr) )
        {
            printf("Q->front: %d\n", Q_Front(QPtr));
            printf("Q->rear:  %d\n", Q_Back(QPtr));
        }
    }

    Q_Destory(QPtr);
    
    return 0;
}
明天該學串了，高興ing......