#include<stdlib.h>
#include<stdio.h>
/*************************************
 * 出隊列操作
 * 隊首（頭指針）---元素1----元素2---元素3---.....
 * 將隊首指向元素2，釋放掉元素1
 * 注意1：隊列原本為空隊列，直接返回
 * 注意2：釋放掉第一個元素後，隊列變為空隊列，別忘了讓隊尾 = 隊首
 * ***************************************************************/
//typedef char ElemType;
typedef struct QNode 
{
    char date;
    struct QNode *next;
}QNode , *QueuePtr;
typedef struct 
{
    QueuePtr front , rear;
}LinkQueue;
/////////////////////////////////////////////////////////////////////
//創建一個隊列
void initQueue(LinkQueue *q)
{
    q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!q->front)
    {
        exit(0);
    }
    q->front->next = NULL;//這時頭結點後面連接的是NULL，但本身不是NULL
}
/////////////////////////////////////////////////////////////////////
//入隊列操作
void EnQueue(LinkQueue *q , char e)
{
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!q->front)
    {
        exit(0);
    }
    p->date = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}
////////////////////////////////////////////////////////////////////
//出隊列操作
void DeQueue(LinkQueue *q , char *e)
{
    if (q->front == q->rear)//判斷是否為空隊列
    {
        return;
    }
    QueuePtr p;
    p = q->front->next;
    *e = p->date;
    q->front->next = p->next;
    if (q->rear == p)
    {
        q->front = q->rear;
    }
    free(p);
}
/////////////////////////////////////////////////////////////////////
//計算隊列長度
int LenLinkQueue(LinkQueue *q)
{
    int len,i;
    QueuePtr p = q->front->next;
    for (i = 0; p!=NULL;i++)
    {
        p = p->next;
    }
    return i;
}

int main()
{
    LinkQueue q;
    char e;
    //創建隊列
    initQueue(&q);
    printf("隊列創建中，請稍後...\n隊列創建成功！\n");
    //入隊列操作
    printf("請輸入要插入隊列的字元：");
    while ((e = getchar())!= '\n')
    {
        if (e!='\n')
        {
            EnQueue(&q , e);
        }
    }
    //列印隊列
    printf("插入成功，正在列印隊列字元...\n");
    printf("當前隊列為：");
    int len = LenLinkQueue(&q);//隊伍長度
    QueuePtr p = q.front->next;//鏈表不同於順序表，地址不連續，所以不能通過指針的增減來列印，需要複製一個鏈表遍歷
    for (size_t i = 0;i<len ; i++)
    {
        printf("%c" , p->date);
        p = p->next;
    }
    putchar('\n');
    //出隊伍
    printf("請輸入需要幾個元素從隊首出隊列：");
    int n;
    scanf("%d",&n);
    while (n)
    {
        DeQueue(&q , &e);
        printf("%c已從隊首出隊列\n" ,e);
        n--;
    }
    //列印隊伍
    printf("插入成功，正在列印隊列字元...\n");
    printf("當前隊列為：");
    p = q.front->next;
    for (size_t i = 0;i<len ; i++)
    {
        printf("%c" , p->date);
        p = p->next;
    }
    putchar('\n');
    return 0;
}