大家好啊✨
先简单介绍一下自己💎
本人目前大二在读，专业是计算机科学与技术。
写博客的目的是督促自己记好每一章节的笔记，同时也希望结交更多同仁，大家互相监督，一起进步！☀️

---

说明：本来是想着就不写栈和队列这一节的内容了，但仔细想想，还是把一个专栏完完整整地写下来比较好，所以还是补充一篇！
👀本篇博客除了会对栈和队列的各种接口和性质进行讲解之外，还会有几道选择题和Leetcode的OJ题，帮助大家更好地理解，也帮助大家更好地将书面内容转化到实战！
👀本篇博客的每句话都是博主认真思考的结果，如有不严谨之处，望各位小伙伴不吝斧正，一起进步☀️

一、🔭栈

1.1💻栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

切记，这里的栈和博主之前的博客"函数栈帧的创建与销毁"中的栈并不相同，它们分别为数据结构和操作系统中的栈，是两个学科中的两个不同事物，只是名字相同❗️❗️❗️

1.2💻栈的实现

在实现栈之前，大家先思考一个问题，我们应该采取哪种结构存储栈中的数据呢？（单链表or数组）？😕

答案是数组！
原因如下：
1.考虑到栈的后进先出的特性，插入数据时要从尾部插入，出数据时也要从尾部出。如果采用单链表，则需要在每次操作前遍历链表以找到尾，时间复杂度为O(N)，而数组的时间复杂度为O(1)。
2.栈中的数据要求连续存储，这样数组当仁不让。
3.采用数组实现，其缓存利用率更高。

接下来，就开始上具体的代码了！
首先，老规矩，还是先定义一个结构体👇👇👇

typedef int STDataType;

typedef struct Stack
{
	STDataType* val;//指向存储数据数组的指针
	int top;//栈顶元素下标+1
	int capacity;//存储数据的数组的容量
}ST;
1
2
3
4
5
6
7
8

接下来，就是实现栈需要的一些接口👇👇👇

// 初始化栈 
void StackInit (Stack* ps ) ; 
// 入栈 
void StackPush (Stack* ps , STDataType data ) ; 
// 出栈 
void StackPop (Stack* ps ) ; 
// 获取栈顶元素 
STDataType StackTop (Stack* ps ) ; 
// 获取栈中有效元素个数 
int StackSize (Stack* ps ) ; 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps ) ; 
// 销毁栈 
void StackDestroy(Stack* ps ) ; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

首先是栈的初始化，初始化时不需要给数组开辟空间（也可以开辟一段很小的空间，根据个人习惯安排即可）

void StackInit(ST* ps)
{
	assert(ps);
	ps->val = NULL;
	ps->capacity = ps->top = 0;
}
1
2
3
4
5
6

与初始化对应的是栈的销毁----将所开辟空间释放并置空，将数组空间置零

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->val);
	ps->val = NULL;
	ps->capacity = ps->top = 0;
}
1
2
3
4
5
6
7

接下来就是入栈

在此之前，还要再补充一个东西。不同的人对栈顶的定义是不同的，通常分为两种（栈顶在最后一个元素下标+1处，栈顶在最后一个元素下标处）
当然，这两种方式都是可以的，这里采用第一种。

由上面这段话，我们还应该知道，在以后的代码生涯中，不管结构体接口实现有多么简单，都不能直接在接口外对结构体数据进行操作，必须要使用已经实现的接口！

就以这个接口为例，如果在不知道接口实现者采用哪种方式表示栈顶的情况下，直接用"top是否为0’'来判断栈是否为空，则答案可能是错的。因为如果采用第二种方式，栈为空时，top应该为-1.

好的，我们继续来实现入栈的接口！

入栈之前需要检查一下开辟空间是否已经存满，若满，则需扩容！

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->val, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->val = tmp;
		ps->capacity = newcapacity;
	}
	ps->val[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上面这个接口需要调用另一个接口----判断栈是否为空

这个接口非常简单，只需检查一下top即可

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//为空则返回true，相反则返回false
}
1
2
3
4
5

删除栈顶元素

当然也需要检查栈是否为空，为空则不能删除

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
1
2
3
4
5
6

下面是返回栈顶元素

这个的实现要注意top位置的选举，小伙伴们可以自行选择！

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->val[ps->top - 1];
}
1
2
3
4
5
6

最后一个返回栈中数据个数也很简单

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5

二、🔭队列

2.1💻队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

队列根栈不同之处就在于出数据时的位置

2.2💻队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

接下来，我们来看一下实现队列所需要的一些接口

typedef int QDataType;
//链式结构，表示队列
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;//队列的头
	QNode* tail;//队列的尾
	int size;//队列中有效数据的个数
}Queue;

//初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//返回队列头部的数据
QDataType QueueFront(Queue* pq);
//返回队列尾部的数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队列中数据个数
int QueueSize(Queue* pq);
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

为了方便大家理解，我们可以将队列想象成银行排队叫号办理业务。
大家每拿一个新的号码，就相当于往队列中入一个数据，当窗口叫号时，就往队列外出一个数据。
为了知道下次拿新号码时该拿几，我们应该知道目前最后一个拿号的人，也就是队列的最后一个数据。
但是，我们并不需要直接叫最后一个人去办理业务，所以也就没必要在队列中加入“删除最后一个数据”的接口。

队列的初始化

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

1
2
3
4
5
6
7

队列的销毁

注意，队列的销毁和栈的销毁不同，队列的结构是单链表结构，如果直接释放头结点，则找不到剩余结点的位置，也就无法释放内存，故队列的销毁要逐个遍历数据，将其逐个释放。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

向队列中插入数据

向队列中插入数据要先创建一个新的结点，然后判断队列的头指针和尾指针是否为NULL，若为NULL，则将新结点赋给它们，若不为NULL，则将新节点插在尾结点的后面，并将其变为尾结点。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->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

弹出队列的第一个数据

与销毁队列相同，我们在弹出第一个数据之前，要找到第一个结点的下一个结点，当队列只剩一个数据时，就不能再访问下一个，会造成野指针的问题！

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
	pq->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剩下四个接口比较简单，就一起放在这里啦！

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->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

三、🔭栈和队列面试题

好了，理论知识都已经写完了。光说不练假把式，接下来有四道Leetcode的OJ题和五道选择题，我们一起来练练手吧💪💪💪

3.1💻括号匹配问题

链接：力扣20.有效的括号

面对这样一道题，我们首先要想到不满足题意的几种情况：
1.括号个数为奇数个，必定不匹配
2.括号个数为偶数个，但每种括号并不是成双成对
3.括号个数为偶数个，且每种括号个数都成双成对，但顺序不同

那么，这道题跟栈和队列有什么关系呢？
其实，可以利用栈的先进后出的特性很方便的解决这个问题

首先我们要清楚什么时候入栈，什么时候出栈
如果在给定的字符串中读到了左括号，就将其入栈，接着读取下一个；如果读到了右括号，就将栈顶的元素出栈并判断它们是否匹配
如果匹配就接着往下执行，若不匹配，直接中断程序，返回false

当然，在给定字符串读完之后，还要判断栈是否为空，若不为空，则证明右括号数量少于左括号，这种情况也要返回false

由于这里我们仅用C语言，而不用C++，C语言库中还是没有栈的，所以写题时，我们需要将我们前面实现的栈的接口粘贴过去

//以下为复制粘贴栈的接口代码
typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	--ps->top;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top==0;
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

//以下为题解过程
bool isValid(char * s){
    ST st;
    StackInit(&st);//先对栈进行初始化
    while(*s)//依次读取字符串中数据
    {
        if(*s=='('||*s=='['||*s=='{')
        {//若为左括号，则入栈
            StackPush(&st,*s);
        }
        else
        {
            //取到右括号，栈为空，说明前面左括号数量不匹配
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            //不为空，则将其与栈顶元素比较
            char top=StackTop(&st);
            StackPop(&st);
            if((top!='{'&&*s=='}')
            ||(top!='('&&*s==')')
            ||(top!='['&&*s==']'))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    //栈不为空，左右括号数量不匹配
    bool flag=StackEmpty(&st);
    StackDestroy(&st);
    return flag;
}
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

注意，最后一定要将自己创建的栈销毁，虽然力扣可能无法检测出这个错误，但我们也要养成这个好习惯，避免在将来的工作中由于相同的错误导致内存泄漏❗️❗️❗️

3.2💻用队列实现栈

链接：力扣225.用队列实现栈

题目要求我们用两个队列来实现栈的各种接口，我们首先要考虑到栈和队列先进后出和先进先出的区别。由此来实现栈的时候，我们可以采用“倒数据”的方式。
即出数据时，我们可以将不为空的那个队列中的数据依次pop到为空的那个队列中，到最后一个数据时，直接弹出即可。
入数据时，将其插入到不为空的那个队列中即可。
其他的接口难度都不大，注意要时刻保持两个队列中有一个为空❗️❗️❗️

与第一道题类似，用C语言实现的时候，我们仍需要将我们自己实现的队列接口复制粘贴过去

//以下为复制粘贴队列接口
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;

		free(del);
		del = NULL;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL && pq->tail == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->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) {
    //找出哪一个队列不为空
    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    //将不为空的那一个队列中数据依次倒入为空的那一个，直至剩下最后一个
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int top=QueueFront(nonempty);
    QueuePop(nonempty);
    return top;
}

int myStackTop(MyStack* obj) {
    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) {
    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

3.3💻用栈实现队列

链接：力扣232.用栈实现队列

其实这道题比上面的那道更简单
我们只需要先向其中一个栈中插入数据，需要弹出数据的时候，只需先将其中一个栈中的数据依次pop到另一个中，这样就在栈顶得到了队列的第一个数据，再将其弹出即可。
若再向其中插入数据，只需向空的那一个栈中插入即可，再弹出时，仍弹出另一个栈中的数据，知道其为空，之后再将有数据的那一个倒入空的那一个，循环往复。

//以下为复制粘贴栈的接口
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	// 
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	//assert(!StackEmpty(ps));
	
	--ps->top;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	//assert(!StackEmpty(ps));
	
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}
//以下为题目实现
typedef struct {
    ST pop;
    ST push;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pop);
    StackInit(&obj->push);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->push,x);
}

int myQueuePop(MyQueue* obj) {
    //弹出不为空的那一个栈的数据
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int ret= StackTop(&obj->pop);
    StackPop(&obj->pop);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    //先倒数据，得到第一个数据，再将其弹出
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pop);
    StackDestroy(&obj->push);
    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

3.4💻设计循环队列

链接：力扣622.设计循环队列

为了写这道题，我们先要了解一下什么是循环队列
环形队列可以使用数组实现，也可以使用循环链表实现。

这道题大家可以选择数组或者循环链表，两种方法各有千秋，这里采用数组的方式。

我们要知道这道题的几个重点
首先，循环队列的大小即空间是定长，我们不需要频繁地开辟空间。
其次，我们要区分清楚空和满的情况。
最后，我们要清楚地表示空和满是头和尾的下标。

那么现在我们来思考一个问题，当循环队列所给的空间都存储满数据时，头和尾便重合了，那这种情况怎么和队列为空的情况区分呢？

答案是确实不能很有效地区分这两种情况。
为了解决这个问题，我们不得不另寻他法。
我们不妨在给定的空间之外，再多开辟一个空间，这样，当队列满时，尾就会指向多出来的那一个空间，就不会和头重叠了！

下面来看代码实现

typedef struct {
    int* a;//标记开辟的空间
    int front;//头
    int back;//尾
    int n;//给定的空间+1
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->back=0;
    obj->n=k+1;
    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->n;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //队列不为空才出数据
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front%=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
58
59
60

四、🔭概念选择题

4.1💻选择题一

这道题很简单，根据栈的先进后出特性，直接将入数据的顺序反过来即可，故选B选项

4.2💻选择题二

这道题只需要根据选项依次进行插入、弹出数据即可，不匹配的那个就是答案

A选项顺序为：进1->出1->进2、3、4->出4、3、2
B选项顺序为：进1->进2->出2->进3->出3->进4->出4->出1
C选项明显是错的
D选项顺序为：进1->进2->进3->出3->进4->出4->出2->出1

4.3💻选择题三

这道题跟上面那道编程题有些许不同，这道题并没有增加多出的一个空间，所以不能区分满和空的情况（两种情况头和尾都重叠），故结果是D（空和满）

4.4💻选择题四

这道题根据队列的定义和我们之前实现的接口可知B选项并没有什么用处，我们也未曾实现这个接口。

4.5💻选择题五

这里的N可以理解为循环队列增加一个空间之后的总空间大小，有效长度指当前队列中存储数据的个数
这道题和上面的编程题就是一样的了，答案是B
选择加N之后再除N取模的目的是为了解决尾的下标比头的下标小（相减之后是负数）的情况。

五、🔭总结

👀本篇博客分为知识点讲解和题目讲解两部分
👀小伙伴们在日常的学习中要学会将得到的知识在具体的题目中展现出来，上面各种接口的实现也一定要自己动手敲出来，这样才算真的会了！
👀博主也在学习当中，如果对上面所讲知识点有任何疑问都可以来私信告诉博主，如果有不严谨的地方，也希望各位不吝指出，大家一起进步！