/* 队列 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 4

typedef int tEleme;
typedef struct List {
    tEleme data[MAX_SIZE];      // 元素
    int front;                  // 队头指针
    int rear;                   // 队尾指针
    int length;                 // 队列长度
} List,*pList;


/*
 * 初始化
 * 步骤：
 *  判断队列是否为空，若为空为其申请空间。
 *  申请空间后将队列的队头指针，队尾指针，队列长度均初始化为 0。
 *  返回队列
*/
pList InitList(pList Queue)
{
    if(Queue == NULL)
    {
        Queue = (pList) malloc(sizeof(List));
    }
    Queue->front = 0;
    Queue->rear = 0;
    Queue->length = 0;
    return Queue;
}


/*
 * 获取队列长度
 * 步骤：
 *  返回队列的 length
*/
int getLength(pList Queue)
{
    return Queue->length;
}


/*
 * 打印队列
 * 步骤：
 *  令变量 i 等于队列的队头指针。
 *  判断队列长度是否为零，若为零表示队列是空的，无需打印。否则遍历队列，输出每一个元素。
*/
void printList(pList Queue)
{
    int i = Queue->front;
    if(Queue->length == 0)
    {
        printf("队列为空！\n");
    }
    else
    {
        while (i <= Queue->length)
        {
            printf("队列第 %d 个元素是：%d\n",i,Queue->data[i]);
            i++;
        }
    }
}


/*
 * 判断元素 e 是否在队列中。
 * 步骤：
 *  令变量 i 等于 -1。
 *  令变量 j 等于队列的队头指针。
 *  遍历队列，若队列中某个值等于元素 e 则该元素在队列中。
*/
int listIsIn(pList Queue,tEleme e)
{
    int i = -1;
    int j = Queue->front;
    while (j < Queue->length)
    {
        if(Queue->data[j] == e) i = j;
        j ++;
    }
    return i;
}


/*
 * 入列
 * 步骤：
 *  先判断队列是否已满。
 *  若队列没满，将元素插入的队列的尾部，同时把队列的队尾指针向后移动一位，队列的长度加一。
*/
pList intoList(pList Queue,tEleme e)
{
    if((Queue->rear + 1) % MAX_SIZE == Queue->front)
    {
        printf("元素 %d 入列失败。队列已满，无法入列！\n",e);
        return Queue;
    }
    else
    {
        Queue->data[Queue->rear] = e;
        Queue->rear ++;
        Queue->length ++;
        printf("元素 %d 入列成功！\n",e);
        return Queue;
    }
}


/*
 * 出列
 * 步骤：
 *  先判断元素在队列中的位置。
 *  位置等于 -1 表示元素不在队列中。
 *  位置不等于队列的队头指针表示元素不是队列的第一个元素。
 *  否则将队列原队头指针数据归 0，队头指针自增，长度减一。
 *
*/
pList outList(pList Queue,tEleme e)
{
    int state = listIsIn(Queue,e);
    if(state == -1)
    {
        printf("元素 %d 不在队列里，无法出列！\n",e);
        return Queue;
    }

    if(state != Queue->front)
    {
        printf("元素 %d 不是第一个元素，无法出列！\n",e);
        return Queue;
    }
    else
    {
        Queue->data[Queue->front] = 0;
        Queue->front ++;
        Queue->length--;
        printf("元素 %d 出列成功！\n",e);
        return Queue;
    }
}


/*
 * 清空队列
 * 步骤：
 *  先判断队列是否为空。
 *  若不为空将队头指针，队尾指针，队列长度均清为 0。
*/
pList ClearList(pList Queue)
{
    if(Queue->length == 0)
    {
        printf("队列为空！\n");
        return Queue;
    }

    Queue->front = Queue->rear = Queue->length = 0;
    printf("清空成功！\n");
    return Queue;
}


/*
 * 销毁队列
 * 步骤：
 *  释放队列空间。
*/
pList DestroyList(pList Queue)
{
    free(Queue);
    printf("销毁成功！\n");
}

int main()
{
    pList list = NULL;
    list = InitList(list);
    printf("队列的长度为：%d\n\n",getLength(list));

    list = intoList(list,10);
    list = intoList(list,20);
    list = intoList(list,30);
    list = intoList(list,40);
    printList(list);
    printf("\n");

    list = outList(list,10);
    printList(list);
    printf("\n");

    list = ClearList(list);
    printList(list);
    printf("\n");

    DestroyList(list);
}