双向循环链表队列的接口设计

/********************************************************************************************************
 *
 *
 * 该程序实现循环队列元素的增删改查，目的是提高设计程序的逻辑思维，另外为了提高可移植性，所以循环队列中元素
 * 的数据类型为DataType_t，用户可以根据实际情况修改循环队列中元素的类型。
 *
 * 另外，为了方便管理循环队列,所以用户设计SeqList_t结构体，该结构体中包含三个成员：地址+容量+有效元素的下标
 *
 *
 *
 * Copyright (c)  2023-2024   [email protected]   All right Reserved
 * ******************************************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 指的是循环队列中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造记录循环队列LinkQueue各项参数(循环队列的首地址 + 循环队列的容量 + 循环队列队尾下标+队首下标)的结构体
typedef struct LinkQueue
{
    DataType_t *data;       // 记录循环队列首地址
    struct LinkQueue *prev; // 循环队列节点的直接前驱
    struct LinkQueue *next; // 循环队列节点的直接后继

} LkQueue_t;

// 创建循环队列并对循环队列进行初始化
LkQueue_t *LkQueue_Create(void)
{
    // 1.利用calloc为循环队列的管理结构体申请一块堆内存
    LkQueue_t *Head = (LkQueue_t *)calloc(1, sizeof(LkQueue_t));

    if (NULL == Head)
    {
        perror("calloc memory for Head is failed");
        exit(-1); // 程序异常终止
    }

    // 3.对管理循环队列的结构体进行初始化
    Head->data = NULL; // 头节点不存数据
    Head->prev = Head; // 前驱和后继指向自己体现循环
    Head->next = Head;

    return Head;
}

// 创建一个新的链式队列节点
LkQueue_t *LkQueue_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    LkQueue_t *New = (LkQueue_t *)calloc(1, sizeof(LkQueue_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 2.对新结点的数据域和指针域进行初始化
    New->data = data;
    New->next = New;// 前驱和后继指向自己体现循环
    New->prev = New;

    return New;
}

// 判断循环队列是否为空
bool LkQueue_IsEmpty(LkQueue_t *Head)
{
    return (Head->next == Head) ? true : false;
}

// 入队
bool LkQueue_Enqueue(LkQueue_t *Head, DataType_t data)
{
    LkQueue_t *Phead = Head->next;
    LkQueue_t *New = LkQueue_NewNode(data);

    // 1.判断链表是否为空
    if (LkQueue_IsEmpty(Head))
    {
        Head->next = New;
    }
    else // 尾插入队
    {
        New->next = Phead;
        New->prev = Phead->prev;

        Phead->prev->next = New;
        Phead->prev = New;
    }

    return true;
}

// 出队
DataType_t LkQueue_Dequeue(LkQueue_t *Head)
{
    DataType_t temp = 0;
    LkQueue_t *Phead = Head->next;
    // 1.判断循环队列是否为空
    if (LkQueue_IsEmpty(Head))
    {
        printf("LkQueue is Empty!\n");
        return false;
    }
    // 2.判断是否只有首节点一个元素
    if (Phead->next == Phead)
    {
        Head->next = Head;
    }
    else
    {
        // 4.对头节点进行取值删除操作

        Phead->prev->next = Phead->next;
        Phead->next->prev = Phead->prev;
        Head->next = Phead->next;
    }

    temp = Phead->data;

    Phead->prev = NULL;
    Phead->next = NULL;
    free(Phead);

    return temp;
}

// 遍历顺序表的元素
void LkQueue_Print(LkQueue_t *Head)
{
    LkQueue_t *Phead = Head->next;
	
    while (Phead->next != Head->next)
    {
        printf("data=%d\n", Phead->data);
        Phead = Phead->next;
    }
    printf("data=%d\n", Phead->data);
}

int main(int argc, char const *argv[])
{

    // 1.创建双向循环链表队列
    LkQueue_t *Head = LkQueue_Create();

    // 2.向队列中插入新元素
    printf("*********************************入栈********************************\n");
    LkQueue_Enqueue(Head, 5);
    LkQueue_Enqueue(Head, 2);
    LkQueue_Enqueue(Head, 1);
    LkQueue_Enqueue(Head, 4);
    LkQueue_Enqueue(Head, 6);

    // //3.遍历队列
    LkQueue_Print(Head); // -- 5 2 1 4 6
    printf("\n");
    // 4.将已有队列中的内容输出
    printf("*********************************出栈********************************\n");
    printf("出队元素为%d\n", LkQueue_Dequeue(Head));
    printf("出队元素为%d\n", LkQueue_Dequeue(Head));
    printf("出队元素为%d\n", LkQueue_Dequeue(Head));
    printf("出队元素为%d\n", LkQueue_Dequeue(Head));
    printf("出队元素为%d\n", LkQueue_Dequeue(Head));

    // //5.遍历队列
    LkQueue_Print(Head); // --空
    printf("\n");

    // 2.向队列中插入新元素
    printf("*********************************入栈********************************\n");
    LkQueue_Enqueue(Head, 6);
    LkQueue_Enqueue(Head, 4);
    LkQueue_Enqueue(Head, 1);
    LkQueue_Enqueue(Head, 2);
    LkQueue_Enqueue(Head, 5);

    // //3.遍历队列
    LkQueue_Print(Head); // -- 6 4 1 2 5
    printf("\n");
    return 0;
}