【数据结构】之队列（C语言描述）

　　队列（Queue）是编程中最常用的数据结构之一。

　　队列的特点是“先进先出”，就像食堂排队买饭一样，先来的人排在前面，后来的人排在后面；前面的人先买饭，买完饭后离开这个队列。这就是队列的原理，它可以进行入队列和出队列的操作，也就是说，队列限制用户只能在队列的前后两端进行操作，不能在中间进行操作。

　　和线性表、栈相同，队列也有顺序的存储方式和链式的存储方式两种方式，分别称为顺序对和链队。与栈不同的是，队列可以在前后两个端点处进行增/删操作，因此，顺序队性能大大不如链队，链队是二者中比较常用的队列表示形式。

　　下面的代码是使用 C语言描述的链队的代码。

　　队列的头文件Queue.h中的代码如下：

/**

 * 队列（链式存储）

 * 本程序中队列的存储方式：头节点->节点1->节点2->...->节点N，头结点中不存储数据

 */

#include <Constant.h>

// 定义队列节点中数据的类型

typedef int ElemType;

// 队列中节点的数据结构体

typedef struct QueueNode {

    ElemType value;

    struct QueueNode* nextNode;

} QueueNode;

// 队列的结构体

typedef struct Queue {

    QueueNode* data;

    QueueNode* firstNode;

    QueueNode* lastNode;

    int length;

} Queue;

// 初始化队列

Status initQueue(Queue* Q) {

    Q->data = (QueueNode*)malloc(sizeof(QueueNode));

    if(Q->data == NULL) {

        printf("队列初始化失败！\n");

        return FAILURE;

    }

    Q->data->nextNode = NULL;

    Q->firstNode = NULL;

    Q->lastNode = NULL;

    Q->length = ;

    return SUCCESS;

}

// 销毁队列

Status destroyQueue(Queue* Q) {

    QueueNode* node;

    if(Q->data == NULL) {

        printf("队列不存在，销毁失败！\n");

        return FAILURE;

    }

    while(Q->data->nextNode != NULL) {

        node = Q->data->nextNode;

        Q->data->nextNode = node->nextNode;

        free(node);

    }

    free(Q->data);

    return SUCCESS;

}

// 判断队列是否为空

Status isQueueEmpty(Queue* Q) {

    if(Q->data == NULL) {

        printf("队列不存在！\n");

        exit();

    }

    if(Q->length == ) {

        return TRUE;

    }

    return FALSE;

}

// 清空队列

Status clearQueue(Queue* Q) {

    QueueNode* node;

    if(Q->data == NULL) {

        printf("队列不存在，清空失败！\n");

        return FAILURE;

    }

    while(Q->data->nextNode != NULL) {

        node = Q->data->nextNode;

        Q->data->nextNode = node->nextNode;

        free(node);

    }

    return SUCCESS;

}

// 获取队列中元素的个数

int getQueueSize(Queue* Q) {

    if(Q->data == NULL) {

        printf("队列不存在！\n");

        exit();

    }

    return Q->length;

}

// 查看队列中的第一个元素

QueueNode* getFirstElem(Queue* Q) {

    if(Q->data == NULL) {

        printf("队列不存在，获取第一个元素失败！\n");

        return NULL;

    }

    if(Q->length == ) {

        printf("队列是空队列，获取第一个元素失败！\n");

        return NULL;

    }

    return Q->firstNode;

}

// 查看队列中的最后一个元素

QueueNode* getLastElem(Queue* Q) {

    if(Q->data == NULL) {

        printf("队列不存在，获取最后一个元素失败！\n");

        return NULL;

    }

    if(Q->length == ) {

        printf("队列是空队列，获取最后一个元素失败！\n");

        return NULL;

    }

    return Q->lastNode;

}

// 元素入队列

Status appendElem(Queue* Q, ElemType e) {

    QueueNode* newNode;

    if(Q->data == NULL) {

        printf("队列不存在，元素入队列失败！\n");

        return FAILURE;

    }

    newNode = (QueueNode*)malloc(sizeof(QueueNode));

    if(newNode == NULL) {

        printf("元素入队列失败！\n");

        return FAILURE;

    }

    newNode->value = e;

    newNode->nextNode = NULL;

    if(Q->data->nextNode == NULL) {

        Q->data->nextNode = newNode;

        Q->firstNode = newNode;

    } else {

        Q->lastNode->nextNode = newNode;

    }

    Q->lastNode = newNode;

    Q->length++;

    return SUCCESS;

}

// 元素出队列

QueueNode* retrieveElem(Queue* Q) {

    QueueNode* node;

    if(Q->data == NULL) {

        printf("队列不存在，元素出队列失败！\n");

        return NULL;

    }

    if(Q->length == ) {

        printf("队列是空队列，元素出队列失败！\n");

        return NULL;

    }

    node = Q->data->nextNode;

    Q->data->nextNode = node->nextNode;

    Q->length--;

    return node;

}

// 遍历队列中的元素

void traverseQueue(Queue* Q) {

    QueueNode* node;

    if(Q->data == NULL) {

        printf("队列不存在，遍历失败！\n");

        exit();

    }

    if(Q->length == ) {

        printf("队列是空队列，遍历失败！\n");

        exit();

    }

    printf("遍历队列：");

    node = Q->data;

    while((node = node->nextNode) != NULL) {

        printf("%-4d", node->value);

    }

    printf("\n");

}

// 测试队列的方法

int testQueue() {

    // 各种对象的声明

    Queue queue;

    QueueNode* node;

    int i = ;

    // 初始化队列

    if(initQueue(&queue) == SUCCESS) {

        printf("队列初始化成功！\n");

    }

    // 入队列

    for(i = ; i <= ; i++) {

        if(appendElem(&queue, i) == SUCCESS) {

            printf("元素%d入队列成功！\n", i);

        }

    }

    // 出队列

    if((node = retrieveElem(&queue)) != NULL) {

        printf("元素%d被移除队列\n", node->value);

    }

    // 查看队列中的第一个元素

    if((node = getFirstElem(&queue)) != NULL) {

        printf("队列中第一个元素的值是：%d\n", node->value);

    }

    // 查看队列中的最后一个元素

    if((node = getLastElem(&queue)) != NULL) {

        printf("队列中最后一个元素的值是：%d\n", node->value);

    }

    // 获取队列中元素的个数

    printf("队列中元素的个数：%d\n", getQueueSize(&queue));

    // 遍历队列中的元素

    traverseQueue(&queue);

    // 判断队列是否为空

    printf("队列是否为空？%s\n", isQueueEmpty(&queue) == TRUE ? "是" : "否");

    // 清空队列

    if(clearQueue(&queue) == SUCCESS) {

        printf("清空队列成功！\n");

    }

    // 销毁队列

    if(destroyQueue(&queue) == SUCCESS) {

        printf("队列销毁成功！\n");

    }

}

　　常量类 Constant.h 中定义了一些常量，其代码如下：

#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define SUCCESS 1

#define FAILURE 0

typedef int Status;

　　主函数所在的文件 main.c 中的代码如下：

#include <Queue.h>

int main() {

    testQueue();

    return ;

}

　　运行结果如下：

队列初始化成功！

元素1入队列成功！

元素2入队列成功！

元素3入队列成功！

元素4入队列成功！

元素5入队列成功！

元素1被移除队列

队列中第一个元素的值是：1

队列中最后一个元素的值是：5

队列中元素的个数：4

遍历队列：2   3   4   5

队列是否为空？否

清空队列成功！

队列销毁成功！

Process returned 0 (0x0)   execution time : 1.743 s

Press any key to continue.

巴特西

【数据结构】之队列（C语言描述）

最新文章

热门文章