【数据结构】队列的基本原理与实现

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

1. 队列的定义

队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端插入，而在表的另一端删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队。特性就是先进先出-FIFO（First In First Out）。

队头（Front）。允许删除的一端，又称队首。

队尾（Rear）。允许插入的一端。

重要术语：队头、队尾、空队列。

2. 队列的顺序存储实现

1. 循环队列

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; // 数组，存储MaxSize-1个元素
    int front,rear; // 队列头和队列尾
}SqQueue;

SqQueue Q;

解读：循环队列依靠front和rear两个指针同时工作，当front和rear同时指向同一个位置时，说明是初实化状态，队列为空，但是对于d1图的情况，指向同一个位置，但是并不是为空。所以采用的方法就是d2的情况，牺牲一个存储单元。

注意：通过模运算将存储空间在逻辑变成了“环状”。

2. 队列初始化

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;  // 初始化两个指针相等且为0
}

3. 判空

bool isEmpty(SqQueue &Q){
    if(Q.rear==Q.front){  // 不需要为0
        return true;
    } else{
        return false;
    }
}

4. 元素入队

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){ // 判断是否队满
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

5. 元素出队

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front){  // 判断队空
        return false;
    }
    x=Q.data[Q.front]; // 先进先出
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

6. 获取队头元素值

bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear==Q.front){  // 判断队空
        return false;
    }
    x=Q.data[Q.front]; // 先进先出
    return true;
}

7. 其他方案

如何判断队列已满/已空：

• 新加一个size用于记录队列的长度，初始为0，每次入队使size加1，每次出队使size减1，当size==0是表示队空；当size==MaxSize时，表示队列满。
• 或者新加一个tag标记，初始为0，入队成功都令tag=1，每次出队成功都令tag=0。当front==rear && tag==0时表示队空；当front==rear && tag==1时表示队满。

3. 队列的链式存储实现

队列的链式表示称为链队列。它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;  // 链表结点的结构体
typedef struct{
    LinkNode *front,*rear; // 链表头，链表尾
}LinkQueue; // 先进先出
LinkQuete Q;

模拟动画链接： https://www.cs.usfca.edu/~galles/visualization/QueueLL.html

1. 队列初始化

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*) malloc(sizeof(LinkNode)); // 头和尾指向同一个结点
    Q.front->next=NULL; // 头结点的next指针为NULL
}

2. 元素入队

// 入队 尾部插入法
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; // rear始终指向尾部
    Q.rear=s;
}

3. 元素出队

// 出队 头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear){
        return false; // 队列为空
    }
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;  // 断链
    if(Q.rear==p){
        Q.rear=Q.front; // 队列置为空
    }
    free(p);
    return true;
}

注意：链式存储一般不会队满，除非内存不足。

4. 实战

顺序存储实现

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; // 数组，存储MaxSize-1个元素
    int front,rear; // 队列头，队列尾
}SqQueue;

// 队列初始化
void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;  // 初始化两个指针相等且为0
}

// 判空
bool isEmpty(SqQueue &Q){
    if(Q.rear==Q.front){  // 不需要为0
        return true;
    } else{
        return false;
    }
}

// 入队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){ // 判断是否队满
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

// 出队
bool DeQueue(SqQueue &Q,ElemType &x){
    bool ret;
    ret=isEmpty(Q);
    if(ret){
        return false;
    }
    x=Q.data[Q.front]; // 先进先出
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
int main() {
    SqQueue Q;
    bool ret; // 存储返回值
    InitQueue(Q);  // 队列初始化
    ret=isEmpty(Q); // 判空
    if(ret){
        printf("queue is empty\n");
    } else{
        printf("queue is not empty\n");
    }
    ret=EnQueue(Q,3);
    ret=EnQueue(Q,4);
    ret=EnQueue(Q,5);
    ret=EnQueue(Q,6); // 最大入队MaxSize-1个元素
    if(ret){
        printf("enqueue success\n");
    } else{
        printf("enqueue failed\n");
    }
    ret=EnQueue(Q,7); // 超过最大MaxSize-1，无法入队
    if(ret){
        printf("enqueue success\n");
    } else{
        printf("enqueue failed\n");
    }
    ElemType e; // 保存出队元素
    ret=DeQueue(Q,e);
    if(ret){
        printf("deque success %d\n",e);
    } else{
        printf("deque failed\n");
    }
    ret=DeQueue(Q,e);
    if(ret){
        printf("deque success %d\n",e);
    } else{
        printf("deque failed\n");
    }
    return 0;
}

F:\Computer\Project\practice\13\13.3-cycle-queue\cmake-build-debug\13_3_cycle_queue.exe
queue is empty
enqueue success
enqueue failed
deque success 3
deque success 4

进程已结束，退出代码为 0

链式存储实现

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

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear; // 链表头，链表尾
}LinkQueue; // 先进先出

// 初始化队列
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*) malloc(sizeof(LinkNode)); // 头和尾指向同一个结点
    Q.front->next=NULL; // 头结点的next指针为NULL
}

// 入队 尾部插入法
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; // rear始终指向尾部
    Q.rear=s;
}

// 出队 头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear){
        return false; // 队列为空
    }
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;  // 断链
    if(Q.rear==p){
        Q.rear=Q.front; // 队列置为空
    }
    free(p);
    return true;
}
int main() {
    LinkQueue Q;
    InitQueue(Q);  // 初始化队列
    EnQueue(Q,3);  // 入队
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    bool ret;
    ElemType e; // 存储出队元素
    ret=DeQueue(Q,e);
    if(ret){
        printf("dequeue success %d\n",e);
    } else{
        printf("dequeue failed\n");
    }
    return 0;
}

F:\Computer\Project\practice\13\13.5-queue-cycle\cmake-build-debug\13_5_queue_cycle.exe
dequeue success 3

进程已结束，退出代码为 0