[数据结构与算法]数据结构与算法（C语言）代码实现-队列的相关操作代码实现（链队列）

队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

我们可以把队列理解成生活中排队做核酸的场景，站在第一个位置的人叫队头，站在最后一个位置的人叫队尾。出队就是做完核酸，入队就是来新的要做核酸的人，出队只能在队头出，即每次做核酸的只能是站在最前面的人做，入队要在队尾入，即后来者只能排在后面，不能进行插队。

链队列

使用链表实现的队列。

头指针：指向链表的头节点
尾指针：指向链表的最后一个节点
队空情况：头指针和尾指针指向同一位置

实现的操作概览

• 初始化队列
  InitLinkQueue(LinkQueue &queue);
• 销毁队列
  DestroyLinkQueue(LinkQueue &queue);
• 判断队列是否为空
  LinkQueueEmpty(LinkQueue queue);
• 获取队列的长度
  LinkQueueLength(LinkQueue queue);
• 获取队头元素
  GetHead(LinkQueue queue, ElemType &e);
• 清空队列
  ClearLinkQueue(LinkQueue &queue);
• 入队操作
  EnLinkQueue(LinkQueue &queue, ElemType e);
• 出队操作
  DeLinkQueue(LinkQueue &queue, ElemType &e);

C代码实现

#include <stdio.h>
#include <cstdlib>

//###一些常量
//函数结果状态码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//队列的最大容量
#define MAXSIZE 5


//函数类型
typedef int Status;
//队列的元素类型
typedef char ElemType;


//定义链队结点结构体
typedef struct LinkQueueNode{
    //节点数据域的类型
    ElemType data;
    //next指针域
    struct LinkQueueNode *next;
}LinkQueueNode, *QueuePointer;
typedef struct{
    //头指针，指向的是头结点，下一个才是队列的首元节点
    QueuePointer front;
    //尾指针
    QueuePointer rear;
    //记录队列的长度
    int length;
}LinkQueue;

//----------------------------------------------
//初始化队列
Status InitLinkQueue(LinkQueue &queue);
//销毁队列
Status DestroyLinkQueue(LinkQueue &queue);
//判断队列是否为空
Status LinkQueueEmpty(LinkQueue queue);
//获取队列的长度
int LinkQueueLength(LinkQueue queue);
//获取队头元素
void GetHead(LinkQueue queue, ElemType &e);
//清空队列
Status ClearLinkQueue(LinkQueue &queue);
//入队操作
Status EnLinkQueue(LinkQueue &queue, ElemType e);
//出队操作
Status DeLinkQueue(LinkQueue &queue, ElemType &e);
//----------------------------------------------

int main(){
    //初始化队列
    LinkQueue *queue = new LinkQueue;
    InitLinkQueue(*queue);
    //准备元素
    ElemType e1 = 'a', e2 = 'b', e3 = 'c', e4 = 'd', e5 = 'e', e6 = 'f';
    //入队
    EnLinkQueue(*queue, e1);
    EnLinkQueue(*queue, e2);
    EnLinkQueue(*queue, e3);
    EnLinkQueue(*queue, e4);
    EnLinkQueue(*queue, e5);
    EnLinkQueue(*queue, e6);
    //判断队列是否为空
    Status isEmpty = LinkQueueEmpty(*queue);
    printf("队列是否为空：%d\n", isEmpty);//0
    //出队
    DeLinkQueue(*queue, e1);
    printf("出队元素：%c\n", e1);//a
    //出队
    DeLinkQueue(*queue, e1);
    printf("出队元素：%c\n", e1);//b
    //队列的长度
    int length = LinkQueueLength(*queue);
    printf("队列的长度：%d\n", length);//4
    //获取队头元素
    GetHead(*queue, e1);
    printf("队列头元素：%c\n", e1);//c
    //清空队列
    ClearLinkQueue(*queue);
    //出队列
    DeLinkQueue(*queue, e1);//队列为空，出队失败！
    //销毁队列
    DestroyLinkQueue(*queue);
}

/**
 * 初始化队列，构造一个空队列
 * @param queue 队列
 * @return
 */
Status InitLinkQueue(LinkQueue &queue){
    //创建链表头结点
    LinkQueueNode *node = new LinkQueueNode;
    node->next = NULL;
    //头指针和尾指针都指向头结点，形成空队
    queue.front = queue.rear = node;
    //初始化队列长度为0
    queue.length = 0;
    return OK;
}

/**
 * 判断队列是否为空，是空队列返回TRUE
 * @param queue 队列
 * @return
 */
Status LinkQueueEmpty(LinkQueue queue){
    //根据队列长度判断
    return queue.length? FALSE: TRUE;
}

/**
 * 获取队列的长度
 * @param queue 队列
 * @return
 */
int LinkQueueLength(LinkQueue queue){
    //返回length属性
    return queue.length;
}

/**
 * 清空队列
 * @param queue
 */
Status ClearLinkQueue(LinkQueue &queue){
    //将队尾指向头结点，重置队列length属性
    queue.rear = queue.front;
    queue.length = 0;
    return OK;
}

/**
 * 销毁队列
 * @param queue
 */
Status DestroyLinkQueue(LinkQueue &queue){
    //定义一个队列指针，指向队头
    QueuePointer queuePointer = queue.front->next;
    for(QueuePointer p = queuePointer; p; p=queuePointer){
        //指针后移
        queuePointer = queuePointer->next;
        //销毁p指向的节点
        delete p;
    }
    //重置队列length属性
    queue.length = 0;
    return OK;
}

/**
 * 获取队头元素
 * @param queue
 * @param e ：用来存放队头的元素
 */
void GetHead(LinkQueue queue, ElemType &e){
    //队头指针的next才是头元素所在的节点
    e = queue.front->next->data;
}

/**
 * 入队操作
 * @param queue 队列
 * @param e 要入队的元素
 */
Status EnLinkQueue(LinkQueue &queue, ElemType e){
    //创建新节点
    LinkQueueNode *node =  new LinkQueueNode;
    node->data = e;
    node->next = NULL;
    //插入节点
    queue.rear->next = node;
    //尾指针后移
    queue.rear = node;
    //更新长度
    queue.length++;
    return OK;
}

/**
 * 出队操作
 * @param queue 队列
 * @param e 用来接收出队的元素
 */
Status DeLinkQueue(LinkQueue &queue, ElemType &e){
    //判断是否是空队列
    if(queue.front == queue.rear){
        printf("队列为空，出队失败！\n");
        return ERROR;
    }
    //记录出队的元素节点
    LinkQueueNode *node = queue.front->next;
    //将出队的元素给e
    e = node->data;
    //移动头指针的next指针域
    queue.front->next = node->next;
    //销毁出队的节点
    delete node;
    //更新长度
    queue.length--;
    return OK;
}