链式队列

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

#define STRINGSIZE 128

typedef char STRING[STRINGSIZE];

/*队列节点的定义*/
typedef struct queuenode
{
    STRING string;
    struct queuenode * next;
}QUEUENODE;

typedef QUEUENODE * QueueNodePtr;

typedef struct linkqueue
{
    QueueNodePtr front; /*队头指针:始终指向链表头节点*/
    QueueNodePtr rear; /*队尾指针*/
}LINKQUEUE;

int InitQueue(LINKQUEUE * linkqueue);
int QueueIsEmpty(LINKQUEUE linkqueue);
int QueueLen(LINKQUEUE linkqueue);
int CreateQueueNode(QueueNodePtr * queuenodeptr, STRING string);
int GetQueueHead(LINKQUEUE linkqueue, STRING string);
int PrintQueue(LINKQUEUE linkqueue);
int EnQueue(LINKQUEUE * linkqueue, STRING string);
int DeQueue(LINKQUEUE * linkqueue, STRING string);
int DestroyQueue(LINKQUEUE * linkqueue);

int main(int argc, char ** argv)
{
    printf("队列的链式存储结构！\n");
    LINKQUEUE linkqueue;
    InitQueue(&linkqueue);
    int flag = -1;
    flag = QueueIsEmpty(linkqueue);
    if(flag == 1)
        printf("是空队列！\n");
    else if(flag == 2)
        printf("是非空队列！\n");

    PrintQueue(linkqueue);

    EnQueue(&linkqueue, "AAA");

    flag = QueueIsEmpty(linkqueue);
    if(flag == 1)
        printf("是空队列！\n");
    else if(flag == 2)
        printf("是非空队列！\n");

    EnQueue(&linkqueue, "BBB");
    EnQueue(&linkqueue, "CCC");
    EnQueue(&linkqueue, "DDD");
    EnQueue(&linkqueue, "EEE");
    EnQueue(&linkqueue, "FFF");
    EnQueue(&linkqueue, "GGG");

    PrintQueue(linkqueue);

    STRING string;
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    printf("出列元素1=[%s]\n", string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    printf("出列元素2=[%s]\n", string);

    memset(string, 0, sizeof(STRING));
    GetQueueHead(linkqueue, string);
    printf("取得的对头元素=[%s]\n", string);

    PrintQueue(linkqueue);

    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    memset(string, 0, sizeof(STRING));
    DeQueue(&linkqueue, string);
    /*DestroyQueue(&linkqueue);*/
    PrintQueue(linkqueue);

    return 0;
}

/*功能：判断链式队列是否为空,1：空， 2：非空*/
int QueueIsEmpty(LINKQUEUE linkqueue)
{
    if(linkqueue.front == linkqueue.rear)
        return 1;
    else
        return 2;
}

/*功能：初始化链队列:创建队列空头节点，front队头指针始终指向他*/
int InitQueue(LINKQUEUE * linkqueue)
{
    linkqueue->front = (QUEUENODE*)malloc(sizeof(QUEUENODE));
    if(linkqueue->front == NULL)
    {
        printf("InitQueue malloc err!\n");
        exit(-1);
    }
    memset(linkqueue->front->string, 0, sizeof(STRING));
    linkqueue->front->next = NULL; /*front指针指向空头节点，front指针的下一个节点才是队头元素*/
    linkqueue->rear = linkqueue->front;

    return 0;
}

/*功能：创建一个队列节点元素*/
int CreateQueueNode(QueueNodePtr * queuenodeptr, STRING string)
{
    *queuenodeptr = (QueueNodePtr)malloc(sizeof(QUEUENODE));
    if(*queuenodeptr == NULL)
    {
        printf("CreateQueueNode malloc err!\n");
        exit(-1);
    }
    strcpy((*queuenodeptr)->string, string);

    return 0;
}

/*功能：求队列中元素的个数*/
int QueueLen(LINKQUEUE linkqueue)
{
    int len = 0;
    QueueNodePtr p = NULL;
    p = linkqueue.front;
    if(p == NULL)
    {
        //printf("链式队列不存在，或者已经销毁！\n");
        return len;
    }
    while(p->next != NULL)
    {
        p = p->next;
        len++;
    }

    return len;
}

/*功能：打印队列中的所有元素*/
int PrintQueue(LINKQUEUE linkqueue)
{

    STRING string;
    int i = 0;
    int flag = -1;

    if(QueueIsEmpty(linkqueue) == 1)
    {
        printf("是空队列,无需打印！\n");
        return 1;
    }
    printf("队列中元素个数=[%d]\n", QueueLen(linkqueue));

    QueueNodePtr p = NULL;
    p = linkqueue.front;
    printf("从队列头开始：\n");
    while(p->next != NULL)
    {
        p = p->next;
        memset(string, 0, sizeof(STRING));
        strcpy(string, p->string);
        i++;
        printf("(第%d个元素=[%s])\n", i, string);
    }

    return 0;
}

/*功能：入队：向队列尾插入一个元素*/
int EnQueue(LINKQUEUE * linkqueue, STRING string)
{
    QueueNodePtr queuenodeptr = NULL;
    CreateQueueNode(&queuenodeptr, string); /*创建一个队列节点元素*/

    linkqueue->rear->next = queuenodeptr; /*连上新的节点*/
    queuenodeptr->next = NULL;
    linkqueue->rear = queuenodeptr; /*队尾指针指向新加入的节点*/
    printf("入队一个元素=[%s], 链队中元素个数=[%d]\n", linkqueue->rear->string, QueueLen(*linkqueue));

    return 0;
}

/*功能：出队：从队头删除一个元素*/
int DeQueue(LINKQUEUE * linkqueue, STRING string)
{
    if(QueueIsEmpty(*linkqueue) == 1)
    {
        printf("队列为空，无元素可出队！\n");
        return -1;
    }
    QueueNodePtr tempnodeptr = linkqueue->front->next;
    if(linkqueue->front->next == linkqueue->rear) /*如果只有一个队尾元素了，则将队尾指针指向头节点*/
    {
        linkqueue->rear = linkqueue->front;
    }
    linkqueue->front->next = linkqueue->front->next->next; /*空头节点后的第一个元素就是队头元素：将队头元素出列*/

    strcpy(string, tempnodeptr->string);
    printf("出队一个元素=[%s], 链队中剩余元素个数=[%d]\n", tempnodeptr->string, QueueLen(*linkqueue));
    free(tempnodeptr); /*删除的节点要释放*/
    tempnodeptr == NULL;

    return 0;
}

/*功能：取得队列头元素*/
int GetQueueHead(LINKQUEUE linkqueue, STRING string)
{
    if(QueueIsEmpty(linkqueue) == 1);
    {
        printf("队列为空，无元素可取！\n");
        return -1;
    }

    strcpy(string, linkqueue.front->next->string);

    return 0;
}

/*功能：销毁队列*/
int DestroyQueue(LINKQUEUE * linkqueue)
{
    QueueNodePtr p = NULL;
    QueueNodePtr q = NULL;
    p = linkqueue->front;
    q = linkqueue->front;
    if(p == NULL)
    {
        //printf("链式队列不存在，或者已经销毁！\n");
        return 0;
    }
    while(q->next != NULL)
    {
        p = q->next;
        free(q);
        q = p;
    }
    free(p);
    p = NULL;
    q = NULL;
    linkqueue->front = NULL;
    linkqueue->rear = NULL;

    printf("链式队列已销毁！\n");

    return 0;
}