链队

1.队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出
2.为了操作方便，我们将队头指针指向链队列的头结点，队尾指针指向终端结点，如下图所示：

链式队列
3.空队列时，front和rear都指向头结点，如下图所示
空队列
4.队列的入队操作相当于在链表尾部插入结点（注意空队列插入时要修改队头指针），队列的出队操作相当于删除头结点的后继元素结点（注意队列中只有一个元素时要修改队尾指针），具体可看链表操作总结（https://www.jianshu.com/p/faa15e9c7da1）。
LinkQueue.h

#pragma once

#define MAXSIZE 10
// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef int QElemType;

//链式队列定义
typedef struct Qnode
{
    QElemType data;
    Qnode* next;
}QNode, * QueuePtr;

typedef struct
{
    QueuePtr front; //队头指针,指向头结点
    QueuePtr rear;  //队尾指针
}LinkQueue;

//链队初始化
Status InitQueue(LinkQueue& Q);

//链队销毁
Status DestroyQueue(LinkQueue& Q);

//入队
Status EnQueue(LinkQueue& Q, QElemType e);

//出队
Status DeQueue(LinkQueue& Q, QElemType& e);

//取队头元素
Status GetHead(LinkQueue Q, QElemType& e);

LinkQueue.cpp

#include "LinkQueue.h"

#include <iostream>
using namespace std;

//链队初始化
Status InitQueue(LinkQueue& Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));

    if (!Q.front)
    {
        cout << "初始化失败" << endl;
        exit(OVERFLOW);
    }

    Q.front->next = NULL;
    return OK;
}

//链队销毁
Status DestroyQueue(LinkQueue& Q)
{
    QueuePtr p;
    while (Q.front)
    {
        p = Q.front->next;
        free(Q.front);
        Q.front = p;
    }
    return OK;
}

//入队
Status EnQueue(LinkQueue& Q, QElemType e)
{
    QueuePtr n = (QueuePtr)malloc(sizeof(QNode));
    if (!n)
    {
        cout << "入队失败" << endl;
        exit(OVERFLOW);
    }
    n->data = e;
    n->next = NULL;

    if (Q.front == Q.rear)  //当队列为空时，还需要修改队头指针
    {
        Q.front->next = n;
        Q.rear = n;
        return OK;
    }
    Q.rear->next = n;
    Q.rear = n;

    return OK;
}
//出队
Status DeQueue(LinkQueue& Q, QElemType& e)
{
    if (Q.front == Q.rear)
    {
        cout << "队空" << endl;
        return ERROR;
    }

    QueuePtr p = Q.front->next;
    e = p->data;

    Q.front->next = p->next;

    if (Q.rear == p)            //如果队列中只有一个元素，则头指针的next域恰好为尾指针指向的结点，还需要修改尾指针指向头结点（队列为空）
    {
        Q.rear = Q.front;
    }

    free(p);

    return OK;
}

//取队头元素
Status GetHead(LinkQueue Q, QElemType& e)
{
    if (Q.front == Q.rear)
    {
        cout << "队空" << endl;
        return ERROR;
    }
    e = Q.front->next->data;
    return OK;
}

main.cpp

#include "LinkQueue.h"
#include <iostream>

using namespace std;

int main(int argc, char** argv)
{

    LinkQueue Q;
    InitQueue(Q);

    for (int i = 0; i < 4; i++)
    {
        EnQueue(Q, i);
    }

    QElemType e;
    GetHead(Q, e);
    cout << "队头元素：" << e << endl;
    for (int i = 0; i < 4; i++)
    {
        DeQueue(Q, e);
        cout << e << endl;
    }
    DeQueue(Q, e);          //队空

    return 0;
}