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

队列的概念

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

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

顺序队列

顺序队列是队列的顺序存储结构。和顺序表一样，顺序队列用数组来存放当前队列中的元素，这里我选择采用循环队列来实现相关代码。

头指针：指向队列的第一个元素
尾指针：指向队列最后一个元素的下一个位置
队空情况：头指针和尾指针指向同一位置
队满情况：尾指针的下一个位置就是头指针

实现的操作概览

• 初始化队列
  InitQueue(Queue &queue);
• 销毁队列
  DestroyQueue(Queue &queue);
• 判断队列是否为空
  QueueEmpty(Queue queue);
• 获取队列的长度
  QueueLength(Queue queue);
• 获取队头元素
  GetHead(Queue queue, ElemType &e);
• 清空队列
  ClearQueue(Queue &queue);
• 入队操作
  EnQueue(Queue &queue, ElemType e);
• 出队操作
  DeQueue(Queue &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{
    //存储队列元素的数组
    ElemType *base;
    //指向队头的指针
    int front;
    //指向队尾下一个位置的指针
    int rear;
}Queue;

//----------------------------------------------
//初始化队列
Status InitQueue(Queue &queue);
//销毁队列
Status DestroyQueue(Queue &queue);
//判断队列是否为空
Status QueueEmpty(Queue queue);
//获取队列的长度
int QueueLength(Queue queue);
//获取队头元素
void GetHead(Queue queue, ElemType &e);
//清空队列
Status ClearQueue(Queue &queue);
//入队操作
Status EnQueue(Queue &queue, ElemType e);
//出队操作
Status DeQueue(Queue &queue, ElemType &e);
//----------------------------------------------

int main(){
    //初始化队列
    Queue *queue = new Queue;
    InitQueue(*queue);
    //准备元素
    ElemType e1 = 'a', e2 = 'b', e3 = 'c', e4 = 'd', e5 = 'e', e6 = 'f';
    //入队
    EnQueue(*queue, e1);
    EnQueue(*queue, e2);
    EnQueue(*queue, e3);
    EnQueue(*queue, e4);
    EnQueue(*queue, e5);//队列已经满了，入队失败！
    EnQueue(*queue, e6);//队列已经满了，入队失败！
    //判断队列是否为空
    Status isEmpty = QueueEmpty(*queue);
    printf("队列是否为空：%d\n", isEmpty);//0
    //出队
    DeQueue(*queue, e1);
    printf("出队元素：%c\n", e1);//a
    //出队
    DeQueue(*queue, e1);
    printf("出队元素：%c\n", e1);//b
    //队列的长度
    int length = QueueLength(*queue);
    printf("队列的长度：%d\n", length);//2
    //获取队列顶元素
    GetHead(*queue, e1);
    printf("队列顶元素：%c\n", e1);//c
    //清空队列
    ClearQueue(*queue);
    //出队列
    DeQueue(*queue, e1);//队列为空，出队失败！
    //销毁队列
    DestroyQueue(*queue);
}

/**
 * 初始化队列，构造一个空队列
 * @param queue 队列
 * @return
 */
Status InitQueue(Queue &queue){
    //创建一个数组，用来存放队列元素
    queue.base = new ElemType[MAXSIZE];
    //头指针和尾指针都指向0，空队列
    queue.front = queue.rear = 0;
    return OK;
}

/**
 * 判断队列是否为空，是空队列返回TRUE
 * @param queue 队列
 * @return
 */
Status QueueEmpty(Queue queue){
    //队列头指针和尾指针指向同一位置即为空队列
    return queue.front == queue.rear? TRUE: FALSE;
}

/**
 * 获取队列的长度
 * @param queue 队列
 * @return
 */
int QueueLength(Queue queue){
    //循环队列当尾指针在头指针前面时，队列长度 = 队尾指针位置+数组长度 - 队头指针位置
    return queue.rear < queue.front? (queue.rear+MAXSIZE)-queue.front: queue.rear-queue.front;
}

/**
 * 清空队列
 * @param queue
 */
Status ClearQueue(Queue &queue){
    //将队列的头指针和尾指针都指向第一个位置，形成空队列
    queue.front = queue.rear = 0;
    return OK;
}

/**
 * 销毁队列
 * @param queue
 */
Status DestroyQueue(Queue &queue){
    //将队列的头指针和尾指针都指向第一个位置
    queue.front = queue.rear = 0;
    //销毁存储队列元素的数组
    delete queue.base;
    return OK;
}

/**
 * 获取队头元素
 * @param queue
 * @param e ：用来存放队头的元素
 */
void GetHead(Queue queue, ElemType &e){
    e = queue.base[queue.front];
}

/**
 * 入队操作
 * @param queue 队列
 * @param e 要入队的元素
 */
Status EnQueue(Queue &queue, ElemType e){
    //判断队列是否已经满了
    //尾指针下一个的位置
    int rearNextIndex = (queue.rear + 1) % MAXSIZE;
    //尾指针下一位置与队列的头指针相同，说明队列已满
    if(rearNextIndex == queue.front){
        printf("队列已经满了，入队失败！\n");
        return ERROR;
    }
    //插入
    //存放元素
    queue.base[queue.rear] = e;
    //更新尾指针位置
    queue.rear = rearNextIndex;
    return OK;
}

/**
 * 出队操作
 * @param queue 队列
 * @param e 用来接收出队的元素
 */
Status DeQueue(Queue &queue, ElemType &e){
    //判断是否是空队列
    if(queue.front == queue.rear){
        printf("队列为空，出队失败！\n");
        return ERROR;
    }
    //出队
    e = queue.base[queue.front];
    //移动头指针
    queue.front = (queue.front+1) % MAXSIZE;
    return OK;
}