【C/C++】C语言实现队列（循环队列+链式队列）

  • 开发
  • 27

C语言实现队列（循环队列+链式队列）

简单描述

  • 用codeblocks编译通过
  • 源码参考连接

https://gitee.com/IUuaena/data-structures-c.git

代码

  • common.h
#ifndef COMMON_H_INCLUDED
#define COMMON_H_INCLUDED

#define QUEUE_ELEM int  //!< 队列元素类型

/*! @brief 函数返回值枚举 */
typedef enum
{
    OK = 0,             //!< 正确
    NON_ALLOCATED = 1,  //!< 内存分配失败
    NON_EXISTENT = 2,   //!< 不存在
    OVERFLOW = 3,       //!< 溢出
    ERROR = 4           //!< 其他类型错误
} status_t;


#endif // COMMON_H_INCLUDED

链式队列

  • linked_queue.h
#ifndef LINKED_QUEUE_H_INCLUDED
#define LINKED_QUEUE_H_INCLUDED

#include "common.h"

/*! @brief 链式队列结点 */
typedef struct linked_queue_node_t
{
    QUEUE_ELEM                  data;   //!< 数据项
    struct linked_queue_node_t* next;   //!< 下一结点
} linked_queue_node_t;

/*! @brief 链式队列 */
typedef struct linked_queue_t
{
    linked_queue_node_t*    front;  //!< 队头指针
    linked_queue_node_t*    rear;   //!< 队尾指针
} linked_queue_t;


// 链式队列初始化
status_t LinkedQueueInit(linked_queue_t* link_queue);

// 链式队列入队
status_t LinkedQueueEnQueue(linked_queue_t* link_queue, QUEUE_ELEM elem);

// 链式队列出队
status_t LinkedQueueDeQueue(linked_queue_t* linked_queue, QUEUE_ELEM* elem);

// 链式队列长度
int LinkedQueueLength(linked_queue_t linked_queue);

// 打印队列
void LinkedQueuePrint(linked_queue_t* linked_queue);

#endif // LINKED_QUEUE_H_INCLUDED
  • linked_queue.c
/*!
 * @file link_queue.c
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 链式队列源文件
 * @version 1.0.0
 * @date 2022-07-10
 * @copyright Copyright (c) 2021
 *  CyberDash计算机考研
 */

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


/*!
 * @brief **链式队列初始化**
 * @param link_queue 链式队列(指针)
 * @return 执行结果
 * @note
 * 链式队列初始化
 * ------------
 * ------------
 *
 * ------------
 * ###1 链式队列rear分配内存###
 * &emsp; **if** 如果malloc失败 :\n
 * &emsp;&emsp; 返回NON_ALLOCATED\n
 * ###2 链式队列front处理###
 * &emsp; front指向rear\n
 * &emsp; front->next = NULL\n
 */
status_t LinkedQueueInit(linked_queue_t* link_queue)
{
    // ----- 1 链式队列rear分配内存 -----
    link_queue->rear = (linked_queue_node_t*)malloc(sizeof(linked_queue_node_t));
    if (!link_queue->rear)      // if 如果malloc失败
    {
        return NON_ALLOCATED;   // 返回NON_ALLOCATED
    }

    // ----- 2 链式队列front处理 -----
    link_queue->front = link_queue->rear;   // front指向rear
    link_queue->front->next = NULL;         // front->next = NULL

    return OK;
}


/*!
 * @brief **链式队列销毁**
 * @param link_queue 链式队列(指针)
 * @return 执行结果
 * @note
 * 链式队列销毁
 * ----------
 * ----------
 *
 * ----------
 */
status_t LinkedQueueDestroy(linked_queue_t* link_queue)
{
    while (link_queue->front)
    {
        link_queue->rear = link_queue->front->next;
        free(link_queue->front);

        link_queue->front = link_queue->rear;
    }

    return OK;
}


/*!
 * @brief **链式队列入队**
 * @param link_queue 链式队列(指针)
 * @param elem 入队元素
 * @return 执行结果
 * @note
 * 链式队列入队
 * ----------
 * ----------
 *
 * ----------
 * ###1 新结点内存分配###
 * &emsp; **if** 如果malloc失败 :\n
 * &emsp;&emsp; 返回NON_ALLOCATED\n
 * ###2 新节点结构体变量赋值###
 * ###3 rear指针处理###
 * - **I**&nbsp;&nbsp; rear->next指向新节点
 * - **II**&nbsp; rear指向新节点
 */
status_t LinkedQueueEnQueue(linked_queue_t* link_queue, QUEUE_ELEM elem)
{
    // ----- 1 新结点内存分配 -----
    linked_queue_node_t* new_node = (linked_queue_node_t*)malloc(sizeof(linked_queue_node_t));
    if (!new_node)      // if 如果malloc失败
    {
        return NON_ALLOCATED;   // 返回NON_ALLOCATED
    }

    // ----- 2 新节点结构体变量赋值 -----
    new_node->data = elem;
    new_node->next = NULL;

    // ----- 3 rear指针处理 -----
    link_queue->rear->next = new_node;  // rear->next指向新节点
    link_queue->rear = new_node;        // rear指向新节点

    return OK;
}


/*!
 * @brief **链式队列出队**
 * @param linked_queue 顺序队列(指针)
 * @param elem 出队元素保存变量(指针)
 * @return 执行结果
 * @note
 * 链式队列出队
 * ----------
 * ----------
 *
 * ----------
 * ###1 空队判断###
 * &emsp; **if** front等于rear : \n
 * &emsp;&emsp; 空队, 返回NON_EXISTENT\n
 * ###2 出队###
 * - **I**&nbsp;&nbsp; 出队结点数据项赋值给*elem
 * - **II**&nbsp; front->next指向出队结点的next
 * - **III** 释放出队结点
 */
status_t LinkedQueueDeQueue(linked_queue_t* linked_queue, QUEUE_ELEM* elem)
{
    // ----- 1 空队判断 -----
    if (linked_queue->front == linked_queue->rear)      // if front等于rear
    {
        return NON_EXISTENT;    // 空队, 返回NON_EXISTENT
    }

    // ----- 2 出队 -----
    linked_queue_node_t* dequeue_node = linked_queue->front->next;
    *elem = dequeue_node->data; // 出队结点数据项赋值给*elem

    linked_queue->front->next = dequeue_node->next; // front->next指向出队结点的next

    free(dequeue_node); // 释放出队结点
    dequeue_node = NULL;

    return OK;
}


/*!
 * @brief **链式队列长度**
 * @param linked_queue 链式队列
 * @return 长度
 * @note
 * 链式队列长度
 * ----------
 * ----------
 *
 * ----------
 */
int LinkedQueueLength(linked_queue_t linked_queue)
{
    linked_queue_node_t* cur = linked_queue.front;
    int length = 0;

    while (cur != linked_queue.rear)
    {
        length++;
        cur = cur->next;
    }

    return length;
}


/*!
 * @brief **打印队列**
 * @param linked_queue 链式队列
 * 打印队列
 * -------
 * -------
 *
 * -------
 */
void LinkedQueuePrint(linked_queue_t* linked_queue)
{
    printf("从队头向队尾打印元素(队头 ... 队尾): \n");

    linked_queue_node_t *cur = linked_queue->front->next;
    while (cur != NULL)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }

    printf("\n");
}

循环队列

  • circular_queue.h
#ifndef CIRCULAR_QUEUE_H_INCLUDED
#define CIRCULAR_QUEUE_H_INCLUDED


#include "common.h"

#define MAX_SIZE    100 //!< 队列最大长度


/*! @brief 循环队列结构体 */
typedef struct
{
    QUEUE_ELEM* elements;   //!< 队列元素数组
    int front;              //!< 队头
    int rear;               //!< 队尾
} circular_queue_t;


// 循环队列初始化
status_t CircularQueueInit(circular_queue_t* circular_queue);

// 循环队列长度
int CircularQueueLength(circular_queue_t circular_queue);

// 循环队列入队
status_t CircularQueueEnQueue(circular_queue_t* circular_queue, QUEUE_ELEM elem);

// 循环队列出队
status_t CircularQueueDeQueue(circular_queue_t* circular_queue, QUEUE_ELEM* elem);

// 循环队列屏幕打印
void CircularQueuePrint(circular_queue_t* circular_queue);


#endif // CIRCULAR_QUEUE_H_INCLUDED
  • circular_queue.c
/*!
 * @file circular_queue.c
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 循环队列源文件
 * @version 1.0.0
 * @date 2022-07-10
 * @copyright Copyright (c) 2021
 *  CyberDash计算机考研
 */


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


/*!
 * @brief **循环队列初始化**
 * @param circular_queue 循环队列(指针)
 * @return 执行结果
 * 循环队列初始化
 * ------------
 * ------------
 *
 * ------------
 * ###1 循环队列数组分配内存###
 * &emsp; **if** 如果malloc失败 :\n
 * &emsp;&emsp; 返回NON_ALLOCATED\n
 * ###2 队头队尾初始化###
 * &emsp; front初始化为0\n
 * &emsp; rear初始化为0\n
 */
status_t CircularQueueInit(circular_queue_t* circular_queue)
{

    // ----- 1 循环队列数组分配内存 -----

    circular_queue->elements = (QUEUE_ELEM*)malloc(MAX_SIZE * sizeof(QUEUE_ELEM));
    if (!circular_queue->elements)      // if 如果malloc失败
    {
        return NON_ALLOCATED;   // 返回NON_ALLOCATED
    }

    // ----- 2 队头队尾初始化 -----
    circular_queue->front = 0;  // front初始化为0
    circular_queue->rear = 0;   // rear初始化为0

    return OK;
}


/*!
 * @brief **循环队列长度**
 * @param circular_queue 循环队列
 * @return 长度
 * @note
 * 循环队列长度
 * ----------
 * ----------
 *
 * ----------
 * 长度等于(rear - front + MAX_SIZE) % MAX_SIZE\n
 */
int CircularQueueLength(circular_queue_t circular_queue)
{
    // 长度等于(rear - front + MAX_SIZE) % MAX_SIZE
    return (circular_queue.rear - circular_queue.front + MAX_SIZE) % MAX_SIZE;
}


/*!
 * @brief **循环队列入队**
 * @param circular_queue 循环队列(指针)
 * @param elem 入队元素
 * @return 执行结果
 * @note
 * 循环队列入队
 * ----------
 * ----------
 *
 * ----------
 * ### 1 判断队列是否满 ###
 * &emsp; **if** 队列满 :\n
 * &emsp;&emsp; 返回OVERFLOW\n
 * ###2 元素elem插入到队尾###
 * - **I**&nbsp;&nbsp; elements数组rear索引位置赋值\n
 * - **II**&nbsp; rear调整数值\n
 */
status_t CircularQueueEnQueue(circular_queue_t* circular_queue, QUEUE_ELEM elem)
{

    // ----- 1 判断队列是否满 -----
    if ((circular_queue->rear + 1) % MAX_SIZE == circular_queue->front)     // if 队列满
    {
        return OVERFLOW;    // 返回OVERFLOW
    }

    // ----- 2 元素elem插入到队尾 -----
    circular_queue->elements[circular_queue->rear] = elem;          // elements数组rear索引位置赋值
    circular_queue->rear = (circular_queue->rear + 1) % MAX_SIZE;   // rear调整数值

    return OK;
}


/*!
 * @brief **循环队列出队**
 * @param circular_queue 循环队列(指针)
 * @param elem 出队元素保存变量(指针)
 * @return 执行结果
 * @note
 * 循环队列出队
 * ----------
 * ----------
 *
 * ----------
 * ###1 空队判断###
 * &emsp; **if** front等于rear : \n
 * &emsp;&emsp; 空队, 返回NON_EXISTENT\n
 * ###2 出队###
 * - **I**&nbsp;&nbsp; elements数组front索引位置元素赋给*elem
 * - **II**&nbsp; front调整数值
 */
status_t CircularQueueDeQueue(circular_queue_t* circular_queue, QUEUE_ELEM* elem)
{
    // ----- 1 空队判断 -----
    if (circular_queue->front == circular_queue->rear)      // if front等于rear
    {
        return ERROR;   // 空队, 返回NON_EXISTENT
    }

    // ----- 2 出队 -----
    *elem = circular_queue->elements[circular_queue->front];    // elements数组front索引位置元素赋给*elem
    circular_queue->front = (circular_queue->front + 1) % MAX_SIZE; // front调整数值

    return OK;
}


/*!
 * @brief **打印循环队列**
 * @param circular_queue 循环队列(指针)
 * @note
 * 打印循环队列
 * ----------
 * ----------
 *
 * ----------
 * &emsp; 从队头front向队尾rear打印队列元素, 相邻元素以空格分隔
 */
void CircularQueuePrint(circular_queue_t* circular_queue)
{
    printf("从队头向队尾打印元素(队头 ... 队尾):\n");

    int cur = circular_queue->front;
    while (cur < circular_queue->rear)
    {
        printf("%d ", circular_queue->elements[cur]);
        cur++;
    }

    printf("\n");
}
  • main.c
#include <stdio.h>
#include <stdlib.h>


#include "linked_queue.h"
#include "circular_queue.h"


/*!
 * @brief **测试循环队列入队/出队**
 * @note
 * 测试循环队列入队/出队
 * ------------------
 * ------------------
 */
void TestCircularQueueEnQueueAndDeQueue()
{
    printf("\n");
    printf("------------------------- CyberDash -------------------------\n");
    printf("                Test SeqQueue EnQueue/DeQueue                \n");
    printf("                      测试顺序队列入队/出队                     \n\n\n");

    circular_queue_t seq_queue;
    status_t status = CircularQueueInit(&seq_queue);

    QUEUE_ELEM elements[8] = { 3, 1, 4, 1, 5, 9, 2, 6 };
    for (int i = 0; i < sizeof(elements) / sizeof(int); i++)
    {
        printf("入队: %d\n", elements[i]);
        CircularQueueEnQueue(&seq_queue, elements[i]);
    }

    CircularQueuePrint(&seq_queue);

    printf("\n出队5次后:\n\n");

    QUEUE_ELEM top_elem;
    for (int i = 0; i < 5; i++)
    {
        CircularQueueDeQueue(&seq_queue, &top_elem);
    }

    CircularQueuePrint(&seq_queue);

    printf("----------------------------------------\n");
}


/*!
 * @brief **测试链式队列入队/出队**
 * @note
 * 测试链式队列入队/出队
 * ------------------
 * ------------------
 */
void TestLinkQueueEnQueueAndDeQueue()
{
    printf("\n");
    printf("------------------------- CyberDash -------------------------\n");
    printf("                Test linked_queue_t EnQueue/DeQueue               \n");
    printf("                      测试链式队列入队/出队                     \n\n\n");

    linked_queue_t link_queue;
    status_t status = LinkedQueueInit(&link_queue);

    QUEUE_ELEM elements[8] = { 3, 1, 4, 1, 5, 9, 2, 6 };
    for (int i = 0; i < sizeof(elements) / sizeof(int); i++)
    {
        printf("入队: %d\n", elements[i]);
        LinkedQueueEnQueue(&link_queue, elements[i]);
    }

    LinkedQueuePrint(&link_queue);

    printf("\n出队5次后:\n\n");

    QUEUE_ELEM top_elem;
    for (int i = 0; i < 5; i++)
    {
        LinkedQueueDeQueue(&link_queue, &top_elem);
    }

    LinkedQueuePrint(&link_queue);

    printf("----------------------------------------\n");
}



int main()
{
    printf("!循环队列 + 链式队列\n");

    /// - 测试循环队列入队/出队
    TestCircularQueueEnQueueAndDeQueue();

    /// - 测试链式队列入队/出队
    TestLinkQueueEnQueueAndDeQueue();
    return 0;
}

运行结果

!循环队列 + 链式队列

------------------------- CyberDash -------------------------
                Test SeqQueue EnQueue/DeQueue
                      测试顺序队列入队/出队


入队: 3
入队: 1
入队: 4
入队: 1
入队: 5
入队: 9
入队: 2
入队: 6
从队头向队尾打印元素(队头 ... 队尾):
3 1 4 1 5 9 2 6

出队5次后:

从队头向队尾打印元素(队头 ... 队尾):
9 2 6
----------------------------------------

------------------------- CyberDash -------------------------
                Test linked_queue_t EnQueue/DeQueue
                      测试链式队列入队/出队


入队: 3
入队: 1
入队: 4
入队: 1
入队: 5
入队: 9
入队: 2
入队: 6
从队头向队尾打印元素(队头 ... 队尾):
3 1 4 1 5 9 2 6

出队5次后:

从队头向队尾打印元素(队头 ... 队尾):
9 2 6
----------------------------------------

Process returned 0 (0x0)   execution time : 0.091 s
Press any key to continue.
阅读全部

相关推荐

  1. 【C/C++】C语言实现队列（循环队列+链式队列）

    2024-04-02 00:20:03       28 阅读

  6. golang实现循环队列

    2024-04-02 00:20:03       38 阅读

  7. rust实现循环队列

    2024-04-02 00:20:03       36 阅读

  8. 循环队列实现（python）

    2024-04-02 00:20:03       41 阅读

  9. golang实现循环队列

    2024-04-02 00:20:03       29 阅读

  10. 数据结构——队列链式存储实现

    2024-04-02 00:20:03       71 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-02 00:20:03       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-02 00:20:03       106 阅读

  9. 在Django里面运行非项目文件

    2024-04-02 00:20:03       87 阅读

  19. Python语言-面向对象

    2024-04-02 00:20:03       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-02 00:20:03       91 阅读

热门阅读

  9. vue.router和vue.route

    2024-04-02 00:20:03       35 阅读

  10. vue 插槽（二）

    2024-04-02 00:20:03       40 阅读

  12. 前端Vue根据List中的某个字段排序

    2024-04-02 00:20:03       36 阅读

  14. linux 没有rc.local文件的解决方法

    2024-04-02 00:20:03       32 阅读

  23. 算法D59 | 单调栈2 | 503.下一个更大元素II 42. 接雨水

    2024-04-02 00:20:03       43 阅读

  27. strstr 的使用和模拟实现

    2024-04-02 00:20:03       41 阅读

  28. 开闭原则（Open Closed Principle）

    2024-04-02 00:20:03       41 阅读

  29. C++经典面试题目（十七）

    2024-04-02 00:20:03       33 阅读