『队列』(Queue)，简称「队」，也是一种操作受限的线性表，只允许在表的一端进行插入，表的另一端进行删除。插入操作称为「进队」或「入队」，删除操作称为「出队」或「离队」。FIFO(First In First Out)。

对头(Front),又称为「队首」。
队尾(Rear)

队列

一般使用链表实现，也可以用数组实现。

链队

带头结点

不带头结点

::: datails
仅完成 入队操作，其余待补充

C++ 个人案例

#include <stdlib.h>
#include <stdio.h>

#define ElementType int

// 定义链表结点的结构体
typedef struct QueueNode{
    ElementType data;
    struct QueueNode *next;
}QueueNode,*pQueueNode;
//
typedef struct {
//    QueueNode *front,*rear; // 链式链队头尾指针
    pQueueNode front,rear; // 等价于 QueueNode *front,*rear;
}QueueLink;

void InitQueueLink(QueueLink &q){
    if (!q.front){ // 未申请过空间
        q.front = q.rear = (pQueueNode)malloc(sizeof(QueueNode)); // 申请 结点空间
        q.front->next = NULL; // 头指针为空
    }else{ // 已申请过空间

    }
}
bool IsEmpty(QueueLink q){
    if (q.front == q.rear){
        return true;
    }
    return false;
}
void printLine(){
    printf("—————————————————————————————————— \n");
}
void clearIO(){
    fflush(stdin);
    fflush(stdout);
}
// 尾插法 入队
bool enReQueue(QueueLink &q,ElementType e){
    pQueueNode temp = (pQueueNode)malloc(sizeof(QueueNode));// 给新结点申请空间
    temp->data =e;
    temp->next = NULL;
    q.rear->next = temp;
    q.rear = temp;
    return true;
}

// 头删法 出队
ElementType deReQueue(QueueLink &q){
    if (IsEmpty(q)){
        return NULL;
    }
    QueueNode *temp = q.front->next; // 获取第一个结点指针
    ElementType e=temp->data; // 取出数据
    q.front->next = temp->next; // 头指针后移
    if (q.rear == temp){ // 出队已到队尾位置
        q.rear = q.front; // 置空队列
    }
    free(temp); // 一定要释放空间
    return e;
}
void PrintQueueLink(QueueLink q){
    if(IsEmpty(q)){
        printf("链队为空！\n");
    }else{
        printf("链表数据为：\n");
        printf("   ");
        pQueueNode temp = q.front->next;
        while (temp != NULL){
            if (temp == q.front->next){
                printf("%d",temp->data);
            }else{
                printf(",%d",temp->data);
            }
            temp = temp->next;
        }
        printf("\n");
    }
}
void EnData(QueueLink &q){
    int x;
    printf("请输入插入队尾的数据(输入9999,即可返回首页)：\n");
    clearIO();
    scanf("%d",&x);
    while (x!=9999){
        enReQueue(q,x);
        printLine();
        PrintQueueLink(q);
        printLine();
        printf("请输入插入队尾的数据(输入9999,即可返回首页)：\n");
        clearIO();
        scanf("%d",&x);
    }
}

void DeData(QueueLink &q){
    char c;
    printf("输入字符'y'或'Y'将进行出队操作，其他字符将返回首页：\n");
    clearIO();
    c = getchar();
    while (c == 'y' || c =='Y'){
        deReQueue(q);
        printLine();
        PrintQueueLink(q);
        printLine();
        printf("输入字符'y'或'Y'将进行出队操作，其他字符将返回首页：\n");
        clearIO();
        c = getchar();
    }
}
void Home(QueueLink &q){
    printf("请选择链队程序模式(输入对应数字即可)：\n");
    printf("1.入队    2.出队    3.初始化   4.退出\n");
    printLine();
    char x;
    x = getchar();
    clearIO();
    while (x != '4'){
        switch (x) {
            case '1':
                EnData(q);
                break;
            case '2':
                DeData(q);
                break;
            case '3':
                InitQueueLink(q);
                printf("链队以初始化，即将返回首页！\n");
                break;
            default:
                break;
        }
        printf("请选择链队程序模式(输入对应数字即可)：\n");
        printf("1.入队    2.出队    3.初始化   4.退出\n");
        printLine();
        clearIO();
        x = getchar();
    }
}
int main() {
    QueueLink Q;
    InitQueueLink(Q);
    Home(Q);
    printf("程序结束");
    return 0;
}

:::

循环队列

循环队列能存储的数据个数为队列长度-1。「队尾(rear)」入队，「对头(front)」出队。一般使用数组来实现。

数组形式

点击查看

C++ 语言的循环队列个人案列，请大佬指点。

#include <stdio.h>

#define MaxSize 10
#define ElementType int

typedef struct {
    ElementType data[MaxSize]; // 数组形式实现循环队列
    int front,rear; // 头尾指针以 int 形式表现
}ReQueue;

void InitReQueue(ReQueue &q){
    q.front = q.rear = 0;
}

bool IsEmpty(ReQueue q){
    if(q.front == q.rear){
        return true;
    }
    return false;
}
bool IsFull(ReQueue q){
    if((q.rear+1)%MaxSize == q.front){
        return true;
    }
    return false;
}
void printLine(){
    printf("—————————————————————————————————— \n");
}
void clearIO(){
    fflush(stdout);
    fflush(stdin);
}
ElementType EnReQueue(ReQueue &q,ElementType e){
    if(IsFull(q)){
        return NULL;
    }
    q.data[q.rear] =e;
    q.rear=(q.rear+1)%MaxSize;
    return e;
}

void PrintReQueue(ReQueue q){
    if(IsEmpty(q)){
        printf("空队！\n");
    } else{
        printf("队列数据为：\n");
        for (int i = q.front; i < q.rear; ++i) {
            if(i == q.front){
                printf("%4d",q.data[i]);
            }else{
                printf(",%d",q.data[i]);
            }
        }
        printf("\n");
        if(IsFull(q)){
            printf("队满，队长为：%d！\n",q.rear-q.front);
        }
    }
}

ElementType DeReQueue(ReQueue &q){
    if(IsEmpty(q)){
        return NULL;
    }
    ElementType e;
    e=q.data[q.front];
    q.front=(q.front+1)%MaxSize;
    return e;
}

void EnData(ReQueue &q){
    int x;
    printf("请输入插入队尾的数据(输入9999,即可返回首页)：\n");
    clearIO();
    scanf("%d",&x);
    while (x!=9999){
        if(EnReQueue(q,x)){
            printf("循环队列长度为：%4d, 队尾数据为：%d。\n",q.rear-q.front,q.data[q.rear-1]);
        }else{
            printf("插入失败，请重试!");
        }
        printLine();
        PrintReQueue(q);
        printLine();
        printf("请输入插入队尾的数据(输入9999,即可返回首页)：\n");
        clearIO();
        scanf("%d",&x);
    }
}

void DeData(ReQueue &q){
    char c;
    printf("输入字符'y'或'Y'将进行出队操作，其他字符将返回首页：\n");
    clearIO();
    c = getchar();
    while (c == 'y' || c =='Y'){
        if(DeReQueue(q)){
            printf("循环队列长度为：%4d, 队首数据为：%d。\n",q.rear-q.front,q.data[q.front]);
        }else{
            printf("出队失败，请重试！\n");
        }
        printLine();
        PrintReQueue(q);
        printLine();
        printf("输入字符'y'或'Y'将进行出队操作，其他字符将返回首页：\n");
        clearIO();
        c = getchar();
    }
}

void Home(ReQueue &q){
    printf("请选择循环队列程序模式(输入对应数字即可)：\n");
    printf("1.入队    2.出队    3.初始化   4.退出\n");
    printLine();
    clearIO();
    char x;
    x = getchar();
    while (x != '4'){
        switch (x) {
            case '1':
                EnData(q);
                break;
            case '2':
                DeData(q);
                break;
            case '3':
                InitReQueue(q);
                printf("循环队列以初始化，即将返回首页！\n");
                break;
            default:
                break;
        }
        printf("请选择循环队列程序模式(输入对应数字即可)：\n");
        printf("1.入队    2.出队    3.初始化   4.退出\n");
        printLine();
        clearIO();
        x = getchar();
    }
}

int main() {
    ReQueue Q;
    InitReQueue(Q);
    Home(Q);
    printf("程序结束");
    return 0;
}

链表形式

使用同时带有头指针和尾指针的单链表来实现。尾插入队，头删出队。

双端队列

允许从两端插入、两端删除的队列。

输入受限的双端队列

输出受限的双端队列

队列应用

树的层次遍历

图的广度优先遍历

操作系统中的应用 FCFS 先来先服务

打印缓冲区