队列使用单链表实现，另外设置两个指针一个指向队首，一个指向队尾。如果直接使用以前的带头节点的单链表，取队尾元素和入队的时间复杂度是O(N)。虽然可以采用循环链表，只设置一个指向尾节点的指针来解决，但是不是很好理解，所以我还是使用两个指针来实现^_^，代码比较简单

/********************************************************************
    created:    2005/12/25
    created:    25:12:2005   9:41
    filename:     queue.h
    author:        Liu Qi, ngaut#126.com
    
    purpose:    链队列的定义与实现
*********************************************************************/

#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:        构造一个节点，其值为target，Next为NULL
* Return value:        指向新节点的指针
* 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:        创建一个队列
* 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)    //个人觉得该函数返回指针更具通用性
{
    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)    //个人觉得该函数返回指针更具通用性
{
    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......