#include<stdio.h>
#include<malloc.h>


typedef int Elemtype;
typedef struct qnode
{
    Elemtype data;
    struct qnode* next;
}DataNode;

typedef struct
{
    DataNode* front;
    DataNode* rear;

}Lq;



//队列的链式存储
//队空的条件  q -> rear == NULL(或者q -> front == NULL)
//进栈操作：新建一个结点（s->data = e)，并将新结点插入到链尾
//出队操作：取出队首结点并删除




//初始化
void InitQueue(Lq*& q)
{
    q = (Lq*)malloc(sizeof(Lq));
    q->front = q->rear = NULL;
}

//进队(尾插法)
bool Enqueue(Lq*& q, Elemtype e)
{
    DataNode* s;
    s = (DataNode*)malloc(sizeof(DataNode));
    s->data = e;
    s->next = NULL;
    if (q->rear == NULL)//原队列为空
    {
        q->front = q->rear = s;//让头指针和尾指针同时指向头结点

    }
    else
    {
        q->rear->next = s;//将新结点连接到队尾，并让rear指向它
        q->rear = s;
    }
}

//出队（头删法）
bool Dequeue(Lq*& q, Elemtype& e)
{
    DataNode* T;
    if (q->rear == NULL) //原队列为空
    {
        return false;
    }
    T = q->front;
    if (q->front == q->rear)//队列中只有一个结点
    {
        q->front = q->rear = NULL;
    }
    else
    {
        q->front = q->front -> next;//删除元素并将头指针往后移
    }
    e = T->data;
    free(T);
    return true;
}