C语言链队列的实现

未测

/*
 * An implement of Queue data structure.
 * 一个链队列的实现方式来说，基本问题是如何判空。
 * 即认定front==rear时队列为空还是有一个结点；
 * 也就是带不带头结点。
 * 不带头结点，则(NULL==front && NULL==rear)为空
 * 带头结点， 则(front==rear)就是空了。
*/

#ifndef Queue_H
#define Queue_H
/*---------------------------*/
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

#define ERROR -1
#define OK 1
#define elem_t int

#define WITH_HEAD_OF_FRONT

/*
 * Queue: |--------------------------|
 * front: ...some nodes... rear:
 * |data| |data|
 * |next| |next|
 * front is a node, rear is another if Queue not empty.
 */

typedef struct node_q
{
    elem_t data;
    struct node_q *next;
}QNode;

typedef struct
{
    QNode *front;
    QNode *rear;
    int size;
}Queue;

Queue* InitQueue()
{
    Queue *pQ = (Queue *)malloc(sizeof(Queue));
    if(!pQ) exit(ERROR);
#ifdef WITH_HEAD_OF_FRONT
    pQ->front = pQ->rear = (QNode *)malloc( sizeof(QNode) );
    if(!pQ->front)
        exit(ERROR);
    pQ->front->next = NULL;
#else
    pQ->front = pQ->rear = NULL;
#endif
    pQ->size = 0;
    return pQ;
}

int QueueEmpty(Queue *pQueue)
{
#ifdef WITH_HEAD_OF_FRONT
    if( pQueue->front == pQueue->rear )
#else
    if(NULL == pQueue->front && NULL == pQueue->rear)
#endif
     return 1;
    return 0;
}

int EnQueue(Queue *pQueue, elem_t e)
{
    QNode *p = (QNode)malloc(sizeof(QNode));
    if(!p) exit(ERROR);
    p->data = e;
    p->next = NULL;
    pQueue->rear->next = p;
    pQueue->rear = p;
    pQueue->size++;
    printf("%d: %c ", pQueue->size, (char)e);
    return OK;
}

/* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */
int DeQueue(Queue *pQueue, elem_t *e)
{
    assert(pQueue);
    QNode *pnode;
#ifdef WITH_HEAD_OF_FRONT
    if(pQueue->front == pQueue->rear)//QueueEmptry
        return ERROR;
    pnode = pQueue->front->next;//first node after head
    if(e != NULL) *e = p->data;
    // try to delete pnode
    pQueue->front->next = pnode->next;// pnode became "another head"
    // front is actually head, so we leave it alone, change rear if empty
    if(pnode == pQueue->rear ) // seems to be Empty, so
        pQueue->rear = pQueue->front; //make it empty.
    free(pnode);
#else
    pnode = pQueue->front;
    if(QueueEmpty(pQueue) || NULL == pnode)
    return ERROR;

    if(e != NULL)
        *e = pnode->data;
    pQueue->size--;
    pQueue->front = pnode->next; //may be null
    free(pnode);
    if(pQueue->front == pQueue->rear) //Empty, and to make sure it's empty
    {
        pQueue->rear = NULL;
        pQueue->size = 0;
    }
#endif
    return OK;
}

void DestroyQueue(Queue *pQueue)
{
    assert(pQueue);
#ifdef WITH_HEAD_OF_FRONT
    while(pQueue->front)
    {
    // use rear as temp to delete node
        pQueue->rear = pQueue->front->next;
        free(pQueue->front);
        pQueue->front = pQueue->rear;
    }
#else
    while(QueueEmpty(pQueue))
    {
        DeQueue(pQueue, NULL);
    }
    // free the Queue itself
    free(pQueue);
#endif
}

int QueueLength(Queue *pQ)
{
    int i = 0;
#ifdef WITH_HEAD_OF_FRONT
    QNode *ptmp = pQ->front;
    while(ptmp != pQ->rear)
    {
        ++i;
        ptmp = ptmp->next;
    }
    return i;
#else
    return pQ->size;
#endif

}

int getFront(Queue *pQ, elem_t *e)
{
//both WITH_HEAD_OF_FRONT or not is OK
    assert(pQ);
    if( ! QueueEmpty(pQ) )
        return -1;
    *e = pQ->front->data;
    return OK;
}

// Test
int main()
{
    int i, item;
    Queue * pTestQ = InitQueue();
    printf("ABCD...EnQueue：\n");
    for(i = 'A'+0; i <= 'K'+0; ++i)
    {
        EnQueue(pTestQ, i);
    }
    printf("\nABCD...DeQueue：\n");
    for(i = 'A'+0; i <= 'K'+0; ++i)
    {
        DeQueue(pTestQ, &item);
        printf("%c ", (char)item);
    }
    DestroyQueue(pTestQ);
}

/*----------------------------*/
#endif