C 语言实现队列

定义

1. 队列是只允许在一端插入，一端删除的特殊线性表
2. 队列先进先出 First In First Out，简称 FIFO
3. 允许插入的一端叫做 队尾元素，插入操作叫做 入队
4. 允许删除的一端叫做 队头元素，插入操作叫做 出队

操作

1. initQueue 初始化
2. destroyQueue 销毁队列
3. clearQueue 清空队列数据
4. emptyQueue 判断队列是否为空
5. inQueue 入队
6. outQueue 出队
7. getLength 获取队列长度
8. getFront 返回队头元素

注：

1. 这种方式很像我们生活中的派对，排在第一个的优先出队，排到最后的，最后出队
2. 插入操作在队尾进行，删除操作在队头进行

C 语言实现

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

typedef struct node{
    int data;
    struct node *next;
}node_t;

typedef struct linkQueue{
    node_t *front;  // 队头
    node_t *rear;   // 队尾
    int length; // 长度
}linkQueue_t;

// 创建队列节点
node_t *createNode(int data);

// 创建队列头结点
linkQueue_t *createQueue(void);

// 入队
int inQueue(linkQueue_t *queue, node_t *node);

// 出队
node_t *outQueue(linkQueue_t *queue);

// 判断队列是否为空
int emptyQueue(linkQueue_t *queue);

// 打印队列元素
void printQueue(linkQueue_t *queue);

// 销毁队列
void destroyQueue(linkQueue_t *queue);

// 清空队列
int clearQueue(linkQueue_t *queue);

// 获取队列长度
int getLength(linkQueue_t *queue);

// 获取队头元素
node_t *getFront(linkQueue_t *queue);

// 创建节点
node_t *createNode(int data)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    if (NULL == node) {
        return NULL;
    }
    node->data = data;
    node->next = NULL;
    return node;
}

linkQueue_t *createQueue(void)
{
    linkQueue_t *queue = (linkQueue_t *)malloc(sizeof(linkQueue_t));
    if (NULL == queue) {
        return NULL;
    }
    node_t *node = (node_t *)malloc(sizeof(node_t));
    if (NULL == node) {
        free(queue);
        return NULL;
    }
    // 空队列头尾节点都指向自己
    queue->front = node;
    queue->rear = node;
    queue->length = 0;
    return queue;
}

int inQueue(linkQueue_t *queue, node_t *node)
{
    if (NULL == queue || NULL == node) {
        return 0;
    }
    // 队尾操作
    queue->rear->next = node;
    queue->rear = node;
    queue->length++;
    return 1;
}

node_t *outQueue(linkQueue_t *queue)
{
    if (emptyQueue(queue)) {
        return NULL;
    }
    // 队头操作
    node_t *node = NULL;
    node = queue->front;
    queue->front = node->next;
    queue->length--;
    return node;
}

int emptyQueue(linkQueue_t *queue)
{
    if (NULL == queue) {
        return 1;
    }
    // 头尾节点地址相同，为空栈
    if (queue->front == queue->rear) {
        return 1;
    }
    return 0;
}

void destroyQueue(linkQueue_t *queue)
{
    if (emptyQueue(queue)) {
        return;
    }
    while (queue->front) {
        queue->rear = queue->front->next;
        free(queue->front);
        queue->front = queue->rear;
    }
    free(queue);
    queue = NULL;
}

int clearQueue(linkQueue_t *queue)
{
    if (emptyQueue(queue)) {
        return 0;
    }
    // 从头结点 next 开始循环清楚
    node_t *node = queue->front->next;
    while (NULL != node) {
        node->data = 0;
        node = node->next;
    }
    return 1;
}

void printQueue(linkQueue_t *queue)
{
    if (emptyQueue(queue)) {
        return;
    }
    node_t *node = queue->front->next;
    while (node != NULL) {
        printf("%d\n", node->data);
        node = node->next;
    }
}

int getLength(linkQueue_t *queue)
{
    if (emptyQueue(queue)) {
        return 0;
    }
    return queue->length;
}

// 获取队头元素
node_t *getFront(linkQueue_t *queue)
{
    if (emptyQueue(queue)) {
        return NULL;
    }
    return queue->front->next;
}


int main(void)
{
    linkQueue_t *queue = createQueue();
    if (NULL != queue) {
        int i = 0;
        node_t *node = NULL;
        for (; i < 5; i++) {
            node = createNode(i);
            if (NULL == node) {
                continue;
            } else {
                inQueue(queue, node);
                node = NULL;
            }
        }
        node = outQueue(queue);
        printf("queue:%d\n", node->data);
        printf("length:%d\n", getLength(queue));
        node = getFront(queue);
        printf("front:%d\n", node->data);
        printQueue(queue);
        clearQueue(queue);
        printf("clear queue\n");
        printQueue(queue);
        destroyQueue(queue);
    }
    return 0;
}

©版权声明：原创作品，允许转载，转载时请务必以超链接形式标明文章 原始出处 & 作者信息。

End