C语言-队列_c语言里面有队列么

---

一、队列

1、和栈一样，对数据的存和取有严格要求的线性存储结构
2、称进数据的一端为队尾，出数据的一端为对头，数据元素进队列的过程称为入队，出队列的过程称为出队
3、栈是一端封口，先进后出，队列是两端都开口，先进先出（一端进，一端出）
4、分为顺序队列、链队列

---

二、顺序队列

1、基础版

（1）顺序队列底层是数组，需要提前申请一个足够大的内存空间初始化顺序队列；
（2）为了满足顺序队列中数据从队头进，队尾出的要求，需要定义两个指针 top 和 rear（两个变量，存储数组下标）用来指向顺序队列中的对头元素和队尾元素
（3）有数据元素进队列时，rear+1，有对头元素出队时，top+1
图示：
元素1进队：

元素2，3，4进队：

元素1出队：

元素2，3出队：

当 4 也出队时，会发现 top 和 rear 重合了，top 和 rear 都指向了a[4]的位置；
整个顺序队列在数据不断的 进队出队 过程中不断后移；
影响：
顺序队列之前的数组存储空间讲无法再使用，造成了空间浪费；
如果申请的空间不足够大，可能造成程序中数组 溢出；

//
// Created by 醉人饮梦 on 2023/2/25.
//

#include <stdio.h>

int enQueue(int* a,int rear,int data)
{
    a[rear] = data;
    rear++;
    return rear;
}
void deQueue(int* a,int top,int rear)
{
    // top==rear，表示队列为空
    while (top!=rear){
        printf("队列元素：%d\n",a[top]);
        top++;
    }
}

int main()
{
    int a[100];
    int top,rear;
    //设置对头指针和队尾指针，当队列中没有元素，对头队尾指向同一块地址
    top = rear = 0;
    // 入队
    rear = enQueue(a,rear,1);
    rear = enQueue(a,rear,2);
    rear = enQueue(a,rear,3);
    rear = enQueue(a,rear,4);
    // 出队
    deQueue(a,top,rear);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

2、改造版

结合上述情况可以将顺序表改造成一个环状表
图示：想象图，实际并不是这样，只是为了理解

//
// Created by 醉人饮梦 on 2023/2/26.
//

#include <stdio.h>

#define MAX 5

// 入队
int enQueue(int* a, int top, int rear, int data)
{
    // 队尾的 下一个位置 等于 队头的位置 则空间已满
    if((rear+1)%MAX == top){
        printf("空间已满 ");
        return rear;
    }
    // 到这里则证明 空间未满，到达最后一个下标后 重置 队尾的位置
    a[rear%MAX]=data;
    rear++;
    // 时刻记住队尾的位置
    return rear;
}

// 出队
int deQueue(int* a, int top, int rear)
{
    // 队头的位置 等于 队尾的位置 则 证明空间已为空，没有数据了
    if(top == rear % MAX){
        printf("队列为空 ");
        return top;
    }
    printf("%d ", a[top]);
    // 到这里 说明还有数据，若 队头 到达最后一个下标时 重置 对头的位置
    top = (top + 1) % MAX;
    // 时刻记住队头的位置
    return top;
}

int main()
{
    int a[MAX];
    int top,rear;
    // 设置队头 队尾指针，当队列中没有元素时，队头队尾指向同一个地址
    top = rear = 0;
    // 入队
    rear = enQueue(a, top, rear, 1);
    rear = enQueue(a, top, rear, 2);
    rear = enQueue(a, top, rear, 3);
    rear = enQueue(a, top, rear, 4);
    // 出队
    top = deQueue(a, top, rear); // 1
    // 入队
    rear = enQueue(a, top, rear, 5);
    // 出队
    top = deQueue(a, top, rear); // 2
    // 入队
    rear = enQueue(a, top, rear, 6);
    // 队列已满，再插入一个试试
    rear = enQueue(a, top, rear, 7);
    // 出队
    top = deQueue(a, top, rear); // 3
    top = deQueue(a, top, rear); // 4
    top = deQueue(a, top, rear); // 5
    // 最后一个元素出栈
    top = deQueue(a, top, rear); // 6
    // 没有元素了
    top = deQueue(a, top, rear);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

---

三、链队列（含头结点）

无头结点的还不会

1、入队

元素 1 入队
（1）直接前驱元素 指向 新结点
（2）rear 指针指向 新结点
元素 2，3 入队

QNode *enQueue(QNode* rear,int data)
{
    QNode *enElem = malloc(sizeof(QNode));
    enElem->data = data;
    enElem->next = NULL;
    // 尾指针 的指针域 指向 新结点
    rear->next = enElem;
    // 尾指针 指向 新结点；
    rear = enElem;
    // 返回新的 尾指针
    return rear;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

2、出队

（1）通过 top 指针找到队头结点，创建一个新指针指向 出队结点
（2）top 指向下一个结点的下一个结点
不要忘记判断删除的是否是链队列中最后一个结点
如果是需要将 rear 指向 top：代表链队列为空
元素 1 出队

元素 2 不演示了，元素 3 出队

注意是双重指针，在函数中改变原指针的指向，需要用指向指针的指针作参数才行

void deQueue(QNode* top,QNode** rear)
{
    QNode *p = NULL;
    // 通过判断头结点 的 指针域 是否为空 来判读队列是否为空
    if(top->next == NULL){
        printf("队列为空 ");
        return;
    }
    p = top->next;
    printf("%d ",p->data);
    // 删除结点
    top->next = p->next;
    // 判断删除的 是否 是最后一个结点，如果是的话，rear指向头结点，避免 rear 成为野指针
    if(*rear == p){
        *rear = top;
    }
    free(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

3、全部代码

//
// Created by 醉人饮梦 on 2023/2/25.
//

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

typedef struct QNode{
    int data;
    struct QNode* next;
}QNode;

// 创建
QNode *initQueue()
{
    // 头结点
    QNode *queue = malloc(sizeof(QNode));
    queue->next = NULL;
    return queue;
}

// 入队
QNode *enQueue(QNode* rear,int data)
{
    QNode *enElem = malloc(sizeof(QNode));
    enElem->data = data;
    enElem->next = NULL;
    // 尾指针 的指针域 指向 新结点
    rear->next = enElem;
    // 尾指针 指向 新结点；
    rear = enElem;
    // 返回新的 尾指针
    return rear;
}

// 出队（二级指针，在函数中更改指针的指向不能直接更改，要使用指向指针的指针）
void deQueue(QNode* top,QNode** rear)
{
    QNode *p = NULL;
    // 通过判断头结点 的 指针域 是否为空 来判读队列是否为空
    if(top->next == NULL){
        printf("队列为空 ");
        return;
    }
    p = top->next;
    printf("%d ",p->data);
    // 删除结点
    top->next = p->next;
    // 判断删除的 是否 是最后一个结点，如果是的话，rear指向头结点，避免 rear 成为野指针
    if(*rear == p){
        *rear = top;
    }
    free(p);
}

int main()
{
    QNode *top = NULL, *rear = NULL;
    // 队头指针 和 队尾指针 指向头结点
    top  = rear = initQueue();
    // 入栈
    rear = enQueue(rear,1);
    rear = enQueue(rear,2);

    // 出栈
    deQueue(top, &rear); // 1
    deQueue(top, &rear); // 2
    // 没有元素，看会显示什么
    deQueue(top, &rear);

    // 入栈
    rear = enQueue(rear,4);
    rear = enQueue(rear,5);
    rear = enQueue(rear,6);
    // 出栈
    deQueue(top, &rear); // 4
    deQueue(top, &rear); // 5

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

---

结语

个人记录学习所用，如有错误之处还请指出，谢谢