-
【数据结构初阶】队列&&队列的面试题
大家好我是沐曦希💕
1.队列
1.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
1.2 队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
Queue.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include#include #include #include typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; // 初始化队列 void QueueInit(Queue* qp); // 销毁队列 void QueueDestroy(Queue* qp); // 队尾入队列 void QueuePush(Queue* qp, QDataType data); // 队头出队列 void QueuePop(Queue* qp); // 检测队列是否为空，如果为空返回true，如果非空返回false bool QueueEmpty(Queue* qp); // 获取队列头部元素 QDataType QueueFront(Queue* qp); // 获取队列队尾元素 QDataType QueueBack(Queue* qp); // 获取队列中有效元素个数 int QueueSize(Queue* qp); - 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
test.c
#include"Queue.h" void test1() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); printf("%d\n", QueueFront(&q)); printf("%d\n", QueueBack(&q)); printf("%d\n", QueueSize(&q)); QNode* cur = q.head; while (cur) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); QueuePop(&q); QueuePop(&q); QueuePop(&q); QueuePop(&q); printf("%d\n", QueueFront(&q)); printf("%d\n", QueueBack(&q)); printf("%d\n", QueueSize(&q)); cur = q.head; while (cur) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); QueueDestroy(&q); } int main() { test1(); 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
Queue.c
#include"Queue.h" void QueueInit(Queue* qp) { qp->head = NULL; qp->tail = NULL; qp->size = 0; } void QueueDestroy(Queue* qp) { assert(qp); QNode* cur = qp->head; while (cur) { QNode* dele = cur; cur = cur->next; free(dele); dele = NULL; } qp->head = NULL; qp->tail = NULL; qp->size = 0; } void QueuePush(Queue* qp, QDataType data) { assert(qp); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("perror fail"); exit(-1); } else { newnode->val = data; newnode->next = NULL; } if (qp->tail == NULL) { qp->head = newnode; qp->tail = newnode; } else { qp->tail->next = newnode; qp->tail = newnode; } ++qp->size; } void QueuePop(Queue* qp) { assert(qp); assert(!QueueEmpty(qp)); if (qp->head->next == NULL) { free(qp->head); qp->head = NULL; qp->tail = NULL; qp->size = 0; } else { QNode* cur = qp->head; qp->head = qp->head->next; free(cur); cur = NULL; --qp->size; } } bool QueueEmpty(Queue* qp) { assert(qp); return qp->head == NULL && qp->tail == NULL; } QDataType QueueFront(Queue* qp) { assert(qp); assert(!QueueEmpty(qp)); return qp->head->val; } QDataType QueueBack(Queue* qp) { assert(qp); assert(!QueueEmpty(qp)); return qp->tail->val; } int QueueSize(Queue* qp) { assert(qp); /*QNode* cur = qp->head; int n = 0; while (cur) { n++; cur = cur->next; } return n;*/ return qp->size; }- 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
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
1.3 循环队列
扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
2.队列的面试题
2.1 用队列实现栈
题目链接：223.用队列实现栈
因为C语言没有队列，那么就需要手动写一个队列出来。
因为要求两个队列，那么可以定义一个结构体，结构体成员是两个队列结构体。typedef struct { Queue q1; Queue q2; } MyStack;- 1
- 2
- 3
- 4
要实现栈的性质：后入先出，而队列的性质：先入先出。
那么可以保持一个队列为空，要出数据时候，把有数据的队列的数据导入（n-1）个数据到没有数据的队列中，返回最后一个数据，并pop该数据。从而实现栈的后入先出。
代码
#include#include #include #include //队列函数的声明 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; // 初始化队列 void QueueInit(Queue* qp); // 销毁队列 void QueueDestroy(Queue* qp); // 队尾入队列 void QueuePush(Queue* qp, QDataType data); // 队头出队列 void QueuePop(Queue* qp); // 检测队列是否为空，如果为空返回true，如果非空返回false bool QueueEmpty(Queue* qp); // 获取队列头部元素 QDataType QueueFront(Queue* qp); // 获取队列队尾元素 QDataType QueueBack(Queue* qp); // 获取队列中有效元素个数 int QueueSize(Queue* qp); //队列的实现 void QueueInit(Queue* qp) { qp->head = NULL; qp->tail = NULL; qp->size = 0; } void QueueDestroy(Queue* qp) { assert(qp); QNode* cur = qp->head; while (cur) { QNode* dele = cur; cur = cur->next; free(dele); dele = NULL; } qp->head = NULL; qp->tail = NULL; qp->size = 0; } void QueuePush(Queue* qp, QDataType data) { assert(qp); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("perror fail"); exit(-1); } else { newnode->val = data; newnode->next = NULL; } if (qp->tail == NULL) { qp->head = newnode; qp->tail = newnode; } else { qp->tail->next = newnode; qp->tail = newnode; } ++qp->size; } void QueuePop(Queue* qp) { assert(qp); assert(!QueueEmpty(qp)); if (qp->head->next == NULL) { free(qp->head); qp->head = NULL; qp->tail = NULL; qp->size = 0; } else { QNode* cur = qp->head; qp->head = qp->head->next; free(cur); cur = NULL; --qp->size; } } bool QueueEmpty(Queue* qp) { assert(qp); return qp->head == NULL && qp->tail == NULL; } QDataType QueueFront(Queue* qp) { assert(qp); assert(!QueueEmpty(qp)); return qp->head->val; } QDataType QueueBack(Queue* qp) { assert(qp); assert(!QueueEmpty(qp)); return qp->tail->val; } int QueueSize(Queue* qp) { assert(qp); /*QNode* cur = qp->head; int n = 0; while (cur) { n++; cur = cur->next; } return n;*/ return qp->size; } //创建一个结构体成员为两个队列的结构体 typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*) malloc (sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { //在非空的队列中入数据 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { //从非空队列向空队列导入(n-1)个数据。 int top = 0; if(!QueueEmpty(&obj->q1)) { //q1为非空，q2为空，从q1向q2导入(n-1)数据，同时pop while(QueueSize(&obj->q1)>1) { QueuePush(&obj->q2,QueueFront(&obj->q1)); QueuePop(&obj->q1); } //q1最后一个数据为top，同时pop该数据 top = QueueFront(&obj->q1); QueuePop(&obj->q1); } else { //q2为非空，q1为空，从q2向q1导入(n-1)数据，同时pop while(QueueSize(&obj->q2)>1) { QueuePush(&obj->q1,QueueFront(&obj->q2)); QueuePop(&obj->q2); } //q2最后一个数据为top，同时pop该数据 top = QueueFront(&obj->q2); QueuePop(&obj->q2); } return top; } //求栈的top数据 int myStackTop(MyStack* obj) { //判断哪个队列不为空，输出该队列的最后一个数据即为栈的top if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { //判断栈是否为空，就需要判断两个队列是否同时为空 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { //要释放队列的动态空间再释放obj的空间，否则内存泄漏 QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); } - 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
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
2.2 用栈实现队列
题目链接:232.用栈实现队列
因为C语言没有栈，那么就需要手动写一个栈出来。
因为要求两个栈，那么可以定义一个结构体，结构体成员是两个栈结构体。
一个栈专门用来将数据入栈pushST，另一个专门用来将数据出栈popST。typedef struct { ST pushST; ST popST; } MyQueue;- 1
- 2
- 3
- 4
要实现队列的性质：先入先出。，而栈的性质：先入后出。
那么可以指定一个栈pushST专门入栈数据，要出栈时候，先判断popST是否为空，为空则将pushST中的数据导入到popST中;如果不为空，则先popST先出空。
代码
#include#include #include #include //栈函数的声明 typedef int STDataType; typedef struct stack { STDataType* a; int top; int capacity; }ST; // 初始化栈 void StackInit(ST* ps); //销毁栈 void StackDestory(ST* ps); // 入栈 void StackPush(ST* ps, STDataType data); // 出栈 void StackPop(ST* ps); //检测栈是否为空 bool StackEmpty(ST* ps); // 获取栈顶元素 STDataType StackTop(ST* ps); // 获取栈中有效元素个数 int StackSize(ST* ps); //栈的实现 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->capacity = 0; ps->top = 0; ps->a = NULL; } void StackPush(ST* ps, STDataType data) { assert(ps); if (ps->capacity == ps->top) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->capacity = newcapacity; ps->a = tmp; } ps->a[ps->top] = data; ++ps->top; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } //创建一个结构体成员为两个栈的结构体 typedef struct { ST pushST; ST popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->pushST); StackInit(&obj->popST); return obj; } void myQueuePush(MyQueue* obj, int x) { //向pushST入栈数据 StackPush(&obj->pushST,x); } int myQueuePop(MyQueue* obj) { //先判断popST是否为空 //popST为空，则将pushST的数据入栈进popST，同时pop一下，最后进入的即为top，同时pop一下 //popST不为空，则popST的最后一个数据即为top，同时pop一下 int top = 0; if(!StackEmpty(&obj->popST)) { top = StackTop(&obj->popST); StackPop(&obj->popST); return top; } else { while(StackSize(&obj->pushST)>0) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } top = StackTop(&obj->popST); StackPop(&obj->popST); return top; } } int myQueuePeek(MyQueue* obj) { //先判断popST是否为空，如果popST为空,则将pushST的数据导入到popST中 //popST最后一个数据即为top if(StackEmpty(&obj->popST)) { while(StackSize(&obj->pushST)>0) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST); } bool myQueueEmpty(MyQueue* obj) { //判断队列是否为空，就需要判断两个栈是否同时为空 return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST); } void myQueueFree(MyQueue* obj) { //要释放两个栈的动态空间再释放obj的空间，否则内存泄漏 StackDestory(&obj->pushST); StackDestory(&obj->popST); free(obj); } - 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
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
2.3 设计循环队列
题目链接：622.设计循环队列
循环链表特点是长度固定，空间满了就不能加入数据，空间可以重复利用。
front指向队列的头，back指向队尾的下一个位置。
代码
typedef struct { int* a; int front; int back; int N; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = (int*)malloc(sizeof(int)*(k+1)); obj->N = k+1; obj->front = 0; obj->back = 0; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->back; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return ((obj->back+1)%obj->N) == obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->a[obj->back] = value; obj->back++; obj->back = obj->back%obj->N; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front = (obj->front+1)%obj->N; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[(obj->back-1+obj->N)%obj->N]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }- 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
3.概念选择题
3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。 经过一系列正常的入队与退队操作后， front=rear=99 ， 则循环队列中的元素个数为（ ） A 1 B 2 C 99 D 0或者100- 1
- 2
- 3
- 4
- 5
- 6
- 7
答案：D
4.以下( )不是队列的基本运算？ A 从队尾插入一个新元素 B 从队列中删除第i个元素 C 判断一个队列是否为空 D 读取队头元素的值- 1
- 2
- 3
- 4
- 5
队列是先入先出，不能直接删除中间任意一个数据
答案:B5.现有一循环队列，其队头指针为front，队尾指针为rear； 循环队列长度为N。其队内有效长度为？(有一个空间不存储数据) A (rear - front + N) % N + 1 B (rear - front + N) % N C ear - front) % (N + 1) D (rear - front + N) % (N - 1)- 1
- 2
- 3
- 4
- 5
- 6
答案:B
4.写在最后
那么队列就到这里结束啦！
-
相关阅读:
(三) Spring Security Oauth2.0 源码分析--认证中心全流程分析
自动化测试2:selenium常用API
【开发】微服务整合Sentinel
nginx启动报thread.exdata错误的解决方案
数学物理方程：球函数
内网渗透代理转发详解及工具介绍
【深度学习】pix2pix GAN理论及代码实现
CSS多行省略的几种方法
Emgu CV4图像处理之方框滤波和均值滤波12(C#)
VINS中的观测性问题
- 原文地址：https://blog.csdn.net/m0_68931081/article/details/126180345