链式环形队列实现/*
** 链式环形队列实现
*/

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

typedef int Queue_Type;

// 定义队列节点结构
typedef struct CQUEUE_NODE
{
    Queue_Type value;
    struct CQUEUE_NODE *next;
}QNode, *PNode;

// 定义队列结构
typedef struct CQUEUE
{
    unsigned int size;
    PNode front, retail;
}LQueue;


//创建环形队列
void Create_Queue(LQueue *L, int n)
{
    PNode front = (PNode)malloc(sizeof(QNode));
    PNode retail = (PNode)malloc(sizeof(QNode));
    if(front == NULL || retail == NULL)
    exit(1);

    scanf("%d", &front->value);
    front->next = NULL;

    // 只有一个节点的时候，头尾指向同一个点
    retail = front;

    // 多个点情况
    int i;
    for(i = 1; i < n; i++)
    {
        PNode p = (PNode)malloc(sizeof(QNode));
        if(p == NULL)
        exit(1);
        scanf("%d", &p->value);
        retail->next = p;
        retail = p;
    }
    // 结束后，尾节点指向头节点
    retail->next = front;

    L->front = (PNode)malloc(sizeof(QNode));
    L->retail = (PNode)malloc(sizeof(QNode));
    if(L->front == NULL || L->retail == NULL)
    exit(1);
    L->front = front;
    L->retail = retail;
    L->size = n;
}

// 销毁队列
void Destory_Queue(LQueue *L)
{
    // 如果队列为空
    if(L->front == NULL)
    exit(1);

    // 这里注意必须重新申请一个节点
    // 直接使用L->retail->next会有类型不能识别的错误
    PNode p = (PNode)malloc(sizeof(QNode));
    if(p == NULL)
    exit(1);
    p = L->front;
    int size = L->size;

    // 队列是多个节点情况
    while(size != 0)
    {
        L->front = p->next;
        free(p);
        p = L->front;
        size--;
    }

    // 这里一定要记得处理
    // 将front retail指向NULL 在上面的处理过程中，只是free并没有指向NULL
    // 如果不指向NULL, front,retail将是野指针
    // 还要记得将L->size重新赋值，上面size只是读取size，并不改变size的值
    L->front = NULL;
    L->retail = NULL;
    L->size = size;
}

// 入列操作 在尾节点插入
void Enqueue(LQueue *L, Queue_Type value)
{
    PNode p = (PNode)malloc(sizeof(QNode));
    if(p == NULL)
    exit(1);
    p->value = value;
    int size = L->size;

    //如果队列是个空队列
    if(size == 0)
    {
        L->front = (PNode)malloc(sizeof(QNode));
        L->retail = (PNode)malloc(sizeof(QNode));
        L->front = p;
        L->retail = p;
        p->next = NULL;
        size ++;
    }

    // 如果队列不是空队列
    // 头节点倒是没有必要重新开辟空间
    PNode p1 = (PNode)malloc(sizeof(QNode));
    if(p1 == NULL)
    exit(1);
    p1 = L->retail;
    p1->next = p;
    p->next = L->front;
    L->retail = p; //这里没发现啊，害我找了很久
    size++;
    L->size = size;
}

// 出列操作
Queue_Type Dequeue(LQueue *L)
{
    int size = L->size;
    Queue_Type n;

    //如果队列为空
    if(size == 0)
    {
        printf("The queue is empty.\n");
        exit(1);
    }

    PNode p = (PNode)malloc(sizeof(QNode));
    if(p == NULL)
    exit(1);
    p = L->front;

    //如果队列只有一个节点
    if(size == 1)
    {
        n = p->value;
        free(p);
        L->front = L->retail = NULL;
        p = NULL;
        size--;
        L->size = size;
        return n;
    }

    if(size == 2)
    {
        n = p->value;
        L->front = L->retail;
        free(p);
        p = NULL;
        size--;
        L->size = size;
        return n;
    }

    // 头节点倒是没有必要重新开辟空间
    PNode p1 = (PNode)malloc(sizeof(QNode));
    if(p1 == NULL)
    exit(1);
    p1 = L->retail;

    n = p->value;
    L->front = p->next;
    p1->next = L->front;
    free(p);
    p = NULL;
    size--;
    L->size = size;
    return n;
}

// 判断队列是否为空
bool Is_Empty(LQueue L)
{
    if(L.size == 0)
    return false;
    else
    return true;
}

// 打印队列
void Print_Queue(LQueue L)
{
    // 如果队列为空
    if(L.size == 0)
    {
        printf("The size of the queue is: %d\n", L.size);
        exit(1);
    }

    printf("The size of the queue is: %d\n", L.size);
    printf("The following are the elements of the queue:\n");

    PNode p = (PNode)malloc(sizeof(QNode));
    if(p == NULL)
    exit(1);
    p = L.front;

    while(p != L.retail)
    {
        printf("%d\n", p->value);
        p = p->next;
    }
    if(p == L.retail)
    {
        printf("%d\n", p->value);
    }
}

int main()
{
    LQueue L;
    int n;
    printf("Input the number of the nodes of the queue:\n");
    scanf("%d", &n);
    printf("-------------------------------------------\n");
    Create_Queue(&L, n);
    printf("-------------------------------------------\n");
    Print_Queue(L);
    printf("-------------------------------------------\n");
    printf("Enqueue a node:\n");
    int n1, n2,n3;
    scanf("%d", &n1);
    Enqueue(&L, n1);
    printf("-------------------------------------------\n");
    Print_Queue(L);
    printf("Dequeue one node  -------------------------\n");
    n2 = Dequeue(&L);
    printf("Node1 is %d\n",n2);
    Print_Queue(L);
    printf("Dequeue another node  -------------------------\n");
    n3 =Dequeue(&L);
    printf("Node2 is %d\n",n3);
    Print_Queue(L);
    printf("-------------------------------------------\n");
    printf("Destory the queue---------------------------\n");
    Destory_Queue(&L);
    Print_Queue(L);
    return 0;
}