队列的链式表示和实现

队列的链式表示和实现
16年3月2日19:56:24

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Qnode {
    int data;
    struct Qnode *pNext;
}QNODE, *PQNODE;

typedef struct {
    PQNODE front;
    PQNODE rear;
}LinkQueue;

/**
 * Initialise the Queue. Attention : return the address of the Queue. Don't use the void .
 * @param  Q [the LinkQueue]
 * @return [if success, return the address of the queue]
 */
LinkQueue * InitQueue (LinkQueue *Q)
{
    Q->front = Q->rear = (PQNODE)malloc(sizeof(QNODE));

    if (!Q->front || !Q->rear)
    {
        printf("Cannot malloc memory for Q->fornt or Q->rear.\n");
        exit(-1);
    }

    Q->front->pNext = NULL;

    return Q;
}

/**
 * Insert the entry to the front of the queue.
 * @param  Q [the LinkQueue]
 * @param  val [the value of the entry]
 * @return [if success, return 1]
 */
int EnQueue(LinkQueue *Q, int val)
{
    PQNODE pTmp;

    pTmp = (PQNODE)malloc(sizeof(QNODE));
    if (!pTmp)
    {
        printf("Can not malloc memory for pTmp.\n");
        exit(-1);
    }

    pTmp->data = val;
    pTmp->pNext = NULL;

    Q->rear->pNext = pTmp;
    Q->rear = pTmp;

    return 1;
}

/**
 * Judge the LinkQueue is empty or not.
 * @param  Q [the LinkQueue]
 * @return [if the linkqueue is empty, return 1, else return 0]
 */
int IsQueueEmpty(const LinkQueue *Q)
{
    return Q->front == Q->rear;
}

/**
 * Remove the entry from the rear of the linkqueue.
 * @param  Q [the linkqueue]
 * @param  val [the val of the removed entry]
 * @return [if success, return 1]
 */
int DeQueue(LinkQueue *Q, int *val)
{
    PQNODE pTmp;

    if (IsQueueEmpty(Q))
    {
        printf("The Queue is empty.\n");
        exit(-1);
    }

    pTmp = Q->front->pNext;
    *val = pTmp->data;
    Q->front->pNext = pTmp->pNext;
    free(pTmp);

    return 1;
}

/**
 * Ruturn the length of the linkqueue.
 * @param  Q [the linkqueue]
 * @return [the length]
 */
int TheLengthOfQueue(LinkQueue Q)
{
    int i = 0;

    PQNODE pTmp;
    pTmp = Q.front;

    while (pTmp != Q.rear)
    {
        i++;
        pTmp = pTmp->pNext;
    }

    return i;
}

/**
 * Traverse the linkqueue.
 * @param Q [the linkqueue]
 */
void TraverseQueue(LinkQueue Q)
{
    PQNODE pTmp = Q.front->pNext;

    while (pTmp)
    {
        printf("%d ", pTmp->data);
        pTmp = pTmp->pNext;
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    LinkQueue Q;
    int val;

    InitQueue(&Q);
    EnQueue(&Q, 1);
    EnQueue(&Q, 2);
    EnQueue(&Q, 3);
    EnQueue(&Q, 4);
    TraverseQueue(Q);
    printf("TheLengthOfQueue is %d. \n", TheLengthOfQueue(Q));


    if (DeQueue(&Q, &val))
    {
        printf("DeQueue success, the val is %d.\n", val);
    }
    if (DeQueue(&Q, &val))
    {
        printf("DeQueue success, the val is %d.\n", val);
    }
    printf("TheLengthOfQueue is %d. \n", TheLengthOfQueue(Q));

    return 0;
}
P { margin-bottom: 0.21cm; }
			
				程序运行结果是：
			
			
				1
2 3 4 
			
			
				TheLengthOfQueue
is 4. 
			
			
				DeQueue
success, the val is 1. 
			
			
				DeQueue
success, the val is 2. 
			
			
				TheLengthOfQueue
is 2.