#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef short ElemType;
typedef short Status;
struct QNode/* 链队列的结点 */
{
    ElemType data;
    struct QNode *next;
};
struct QueueInfo/* 链队列的头尾指针 */
{
    QNode *Qfront;/* 队头指针 */
    QNode *Qrear; /* 队尾指针 */
};
/* */
Status InitQueue(QueueInfo* &q);
Status EnQueue(QueueInfo* &q, ElemType e);
Status DeQueue(QueueInfo* &q, ElemType &e);
ElemType GetHead(struct QueueInfo* &q);
Status MenuPrint();
Status QueueLength(struct QueueInfo* &q);
Status Operation(struct QueueInfo* &q);
/* */
int main()
{
    QueueInfo Q;
    QueueInfo *W = &Q;
    InitQueue(W);/* 初始化队列头结点 */
    MenuPrint();
    Operation(W);
}
/* 顶层操作函数 */
Status Operation(struct QueueInfo* &q)
{
    short choice;
    ElemType e;
    printf("Please input your choice from 1 to 5: ");
    while(scanf("%hd", &choice) != 1)
    {
        while(getchar() != '\n') ;
        printf("Now the input buffer has been cleaned, please input a valid number not a character.\n");
        printf("Please input your choice from 1 to 5: ");
    }
    while(1)
    {
        if(choice == 5)
        {
            printf("Thanks for your using, see you.\n");
            break;
        }
        switch(choice)
        {
            case 1:
                printf("Please input the value of the element that will enter the queue: ");
                scanf("%hd", &e);
                if(EnQueue(q, e) == ERROR)
                {
                    printf("The queue has already been full, so the element can not enter into it.\n");
                }
                break;
            case 2:
                if(DeQueue(q, e) == OK)
                {
                    printf("The element that have just been deleted from the queue is %hd.\n", e);
                }
                else
                {
                    printf("The queue is now empty, so there is no element that can be deleted from it.\n");
                }
                break;
            case 3:
                printf("The length of the queue is %hd now.\n", QueueLength(q));
                break;
            case 4:
                e = GetHead(q);
                if(e != ERROR)
                {
                    printf("The front element of the queue is %hd.\n", e);
                }
                else
                {
                    printf("The queue is empty now, so there is no element in it.\n");
                }
                break;
            default:
                printf("Please input a valid number from 1 to 5.\n");
                break;
        }
        printf("Please input your choice from 1 to 5: ");
        while(scanf("%hd", &choice) != 1)
        {
            while(getchar() != '\n') ;
            printf("Now the input buffer has been cleaned, please input a valid number not a character.\n");
            printf("Please input your choice from 1 to 5: ");
        }
    }
    return OK;
}
/* 打印操作菜单 */
Status MenuPrint()
{
    printf("--------------------------顺序队列基本操作模拟系统--------------------------\n");
    printf("--------------------------1. 入队-------------------------------------------\n");
    printf("--------------------------2. 出队-------------------------------------------\n");
    printf("--------------------------3. 求队列长度-------------------------------------\n");
    printf("--------------------------4. 取队列的队头元素-------------------------------\n");
    printf("--------------------------5. 退出系统---------------------------------------\n");
    return OK;
}
/* 求队列长度 */
Status QueueLength(struct QueueInfo* &q)
{
    short len = 0;
    struct QNode *p = q -> Qfront -> next;
    while(p != NULL)
    {
        len ++;
        p = p -> next;
    }
    return len;
}
/* 取队头元素 */
ElemType GetHead(struct QueueInfo* &q)
{
    if(q -> Qfront == q -> Qrear)
    {
        /* 队空 */
        return ERROR;
    }
    return q -> Qfront -> next -> data;
}
/* 出队 */
Status DeQueue(QueueInfo* &q, ElemType &e)
{
    struct QNode *p;
    if(q -> Qfront == q -> Qrear)
    {
        /* 队空 */
        return ERROR;
    }
    p = q -> Qfront -> next;/* p指向队头元素 */
    e = p -> data;/* e保存队头元素的值 */
    q -> Qfront -> next = p -> next;/* 修改头结点的指针域 */
    if(p == q -> Qrear)
    {
        /* 最后一个元素被删除, 队尾指针指向头结点 */
        q -> Qrear = q -> Qfront;
    }
    free(p);
    return OK;
}
/* 入队 */
Status EnQueue(QueueInfo* &q, ElemType e)
{
    struct QNode *p = (struct QNode*)malloc(sizeof(struct QNode));
    if(p == NULL)
    {
        /* 申请动态内存失败 */
        exit(0);
    }
    p -> data = e;/* 将新结点数据域置为e */
    p -> next = NULL;
    q -> Qrear -> next = p;/* 将新结点插入到队尾 */
    q -> Qrear = p;
    return OK;
}
/* 初始化链队列 */
Status InitQueue(QueueInfo* &q)
{
    /* 链队的初始化操作就是构造一个只有一个头结点的空队 */
    /* 生成新结点作为头结点, 一开始队头和队尾指针都指向此结点 */
    q -> Qfront = (struct QNode*)malloc(sizeof(struct QNode));
    if(q -> Qfront == NULL)
    {
        /* 申请动态内存失败 */
        exit(0);
    }
    q -> Qrear = q -> Qfront;
    q -> Qfront -> next = NULL;
    return OK;
}