​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

OJ题

1.有效的括号

链接：20. 有效的括号

描述：
给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例1：
输入：s = “()”
输出：true

示例2：
输入：s = “()[]{}”
输出：true

示例3：
输入：s = “(]”
输出：false

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

1.1 思路：

这道题目的解题思路是十分符合 栈 的。

首先，我们先要实现一个栈，并创建变量和初始化。题目要求 左括号 需要以正确的顺序闭合，且左右括号成对，那么我们可以遍历字符串 s。

遍历过程中让 左括号入栈，一旦遇到 右括号 便 取栈顶元素 和右括号匹配，并 出栈元素。

一旦匹配失败，便返回 false。如果匹配成功，则让 s++ 往后走。

当字符串遍历结束时，判断栈是否为空，如果栈空，则说明为有效的括号；如果栈非空，则说明有左括号没有匹配，那么返回false。(这里需要返回栈是否为空的值)

1.2 易错情况

1.字符串遍历结束，栈中仍有元素：

输入：s = “() [] {”
输出：false

2.只有右括号，无左括号，栈空，取元素时越界访问：

输入：s = “) ] }”
输出：false

注：只有右括号时为提前返回状况。提前返回需要注意栈的销毁，否则会内存泄漏 ！内存泄漏不会报错，一定要仔细！[如果在公司里面就可能造成事故，奖金没了(bushi) ]

typedef char STDataType;//栈中存储的元素类型

typedef struct Stack
{
STDataType* a;//栈
int top;//栈顶
int capacity;//容量，方便增容
}Stack;

//初始化栈
void StackInit(Stack* pst)
{
assert(pst);

pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素
pst->top = 0;//初始时栈中无元素，栈顶为0
pst->capacity = 4;//容量为4
}

//销毁栈
void StackDestroy(Stack* pst)
{
assert(pst);

free(pst->a);//释放栈
pst->a = NULL;//及时置空
pst->top = 0;//栈顶置0
pst->capacity = 0;//容量置0
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
assert(pst);

if (pst->top == pst->capacity)//栈已满，需扩容
{
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
pst->a = tmp;
pst->capacity *= 2;//栈容量扩大为原来的两倍
}
pst->a[pst->top] = x;//栈顶位置存放元素x
pst->top++;//栈顶上移
}

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
assert(pst);

return pst->top == 0;
}

//出栈
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));//检测栈是否为空

pst->top--;//栈顶下移
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));//检测栈是否为空

return pst->a[pst->top - 1];//返回栈顶元素
}

//获取栈中有效元素个数
int StackSize(Stack* pst)
{
assert(pst);

return pst->top;//top的值便是栈中有效元素的个数
}
/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/
bool isValid(char * s){
    Stack st;//创建一个栈
    StackInit(&st);//初始化栈
    char* cur = s;//cur用于遍历字符串
    while(*cur)
    {
        if(*cur == '('||*cur == '{'||*cur == '[')//前括号统一入栈
        {
            StackPush(&st, *cur);
            cur++;
        }
        else
        {
            if(StackEmpty(&st))//若遇到后括号，且栈为空，则字符串无效
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);//获取栈顶元素
            if((top == '('&&*cur != ')')
            ||(top == '{'&&*cur != '}')
            ||(top == '['&&*cur != ']'))//后括号与栈顶的前括号不匹配
            {
                StackDestroy(&st);
                return false;
            }
            else//匹配
            {
                StackPop(&st);
                cur++;
            }
        }
    }
    bool ret = StackEmpty(&st);//检测栈是否为空
    StackDestroy(&st);
    return ret;//栈为空返回true，栈不为空返回false
}

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

2.用队列实现栈

链接：225. 用队列实现栈

描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

2.1思路：

队列 是 先进先出，栈 是 后进先出，要用队列实现栈，那么就要使用两个队列完成后进先出的操作。

栈的结构设计就是两个队列 q1、q2。而实现栈，我们的重点就在于 后进先出。

可以这样思考：
1.1 我们需要时刻需要保持一个队列为空。

1.2 入数据时，往不为空的队列入数据，如果两个队列都为空，则入任意一个。

2. 出数据时，将不为空的队列中的元素转移到空队列中直到队列中元素只剩一个，出栈原先非空队列的数据，原先非空队列变为空，出栈数据就是模拟栈的栈顶数据。
   

typedef int QDataType;//队列中存储的元素类型

typedef struct QListNode
{
struct QListNode* next;//指针域
QDataType data;//数据域
}QListNode;

typedef struct Queue
{
QListNode* head;//队头
QListNode* tail;//队尾
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
//起始时队列为空
pq->head = NULL;
pq->tail = NULL;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);

QListNode* cur = pq->head;//接收队头
//遍历链表，逐个释放结点
while (cur)
{
QListNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;//队头置空
pq->tail = NULL;//队尾置空
}

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);

QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申请新结点
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;//新结点赋值
newnode->next = NULL;//新结点指针域置空
if (pq->head == NULL)//队列中原本无结点
{
pq->head = pq->tail = newnode;//队头、队尾直接指向新结点
}
else//队列中原本有结点
{
pq->tail->next = newnode;//最后一个结点指向新结点
pq->tail = newnode;//改变队尾指针指向
}
}

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);

return pq->head == NULL;
}

//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));//检测队列是否为空

if (pq->head->next == NULL)//队列中只有一个结点
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else//队列中有多个结点
{
QListNode* next = pq->head->next;
free(pq->head);
pq->head = next;//改变队头指针指向
}
}

//获取队列头部元素
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;//返回队尾指针指向的数据
}

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);

QListNode* cur = pq->head;//接收队头
int count = 0;//记录结点个数
while (cur)//遍历队列
{
count++;
cur = cur->next;
}
return count;//返回队列中的结点数
}
/*---以上代码是队列的基本功能实现，以下代码是题解主体部分---*/
typedef struct {
Queue q1;//第一个队列
Queue q2;//第二个队列
} MyStack;

/** Initialize your data structure here. */
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//申请一个MyStack类型的栈
QueueInit(&pst->q1);//初始化第一个队列
QueueInit(&pst->q2);//初始化第二个队列

return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
//数据压入非空的那个队列
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
Queue* pEmpty = &obj->q1;//记录空队列
Queue* pNoEmpty = &obj->q2;//记录非空队列
if (!QueueEmpty(&obj->q1))//&obj->q1 q1,q2是结构体，结构体传参取地址&
{
pEmpty = &obj->q2;
pNoEmpty = &obj->q1;
}
while (QueueSize(pNoEmpty) > 1)//pEmpty,pNoEmpty本身就是结构体的指针了，指针传参不用取地址了，可以直接传
{
QueuePush(pEmpty, QueueFront(pNoEmpty));
QueuePop(pNoEmpty);
}//将非空队列中的数据放入空队列中，只留下一个数据
int front = QueueFront(pNoEmpty);//获取目标数据
QueuePop(pNoEmpty);//删除目标数据
return front;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
//获取非空队列的队尾数据
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
//两个队列均为空，则MyStack为空
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);//释放第一个队列
QueueDestroy(&obj->q2);//释放第二个队列
free(obj);//释放MyStack
}

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

3.用栈实现队列

链接：232. 用栈实现队列

描述：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例1：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
思路：

队列 要求先进先出，而 栈 为后进先出。

我们将队列的结构设定为两个栈，接下来思考该如何实现操作？

我们把两个栈分别叫做 pushST 和 popST。

1.当入队列时，就把数据入到 pushST 中。

2.当出队列时，如果 popST 中无数据，就把 pushST 中元素导入 popST 中，出栈；如果有数据则直接出栈。

这样就保证了入队列数据在 pushST 中，只要出队列，那么就把元素全部导入 popST 中出掉，栈在出数据时会改变顺序，恰好就对应了队列的规律。

typedef int STDataType;//栈中存储的元素类型

typedef struct Stack
{
STDataType* a;//栈
int top;//栈顶
int capacity;//容量，方便增容
}Stack;

//初始化栈
void StackInit(Stack* pst)
{
assert(pst);

pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素
pst->top = 0;//初始时栈中无元素，栈顶为0
pst->capacity = 4;//容量为4
}

//销毁栈
void StackDestroy(Stack* pst)
{
assert(pst);

free(pst->a);//释放栈
pst->a = NULL;//及时置空
pst->top = 0;//栈顶置0
pst->capacity = 0;//容量置0
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
assert(pst);

if (pst->top == pst->capacity)//栈已满，需扩容
{
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
pst->a = tmp;
pst->capacity *= 2;//栈容量扩大为原来的两倍
}
pst->a[pst->top] = x;//栈顶位置存放元素x
pst->top++;//栈顶上移
}

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
assert(pst);

return pst->top == 0;
}

//出栈
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));//检测栈是否为空

pst->top--;//栈顶下移
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));//检测栈是否为空

return pst->a[pst->top - 1];//返回栈顶元素
}

//获取栈中有效元素个数
int StackSize(Stack* pst)
{
assert(pst);

return pst->top;//top的值便是栈中有效元素的个数
}
/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/
typedef struct {
    Stack pushST;//插入数据时用的栈
    Stack popST;//删除数据时用的栈
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//申请一个队列类型
    StackInit(&obj->pushST);//初始化pushST
    StackInit(&obj->popST);//初始化popST

    return obj;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);//插入数据，向pushST插入
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))//popST为空时，需先将pushST中数据导入popST
    {
        while(!StackEmpty(&obj->pushST))//将pushST数据全部导入popST
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);//返回popST栈顶的元素
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int top = myQueuePeek(obj);
    StackPop(&obj->popST);//删除数据，删除popST中栈顶的元素
    return top;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);//两个栈均为空，则“队列”为空
}

void myQueueFree(MyQueue* obj) {
    //先释放两个栈，再释放队列的结构体类型
    StackDestroy(&obj->pushST);
    StackDestroy(&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

4.设计循环队列

链接：622. 设计循环队列

描述：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

4.1思路：

在本题中，循环队列的大小是固定的，可重复利用之前的空间。接下来，就开始分析结构。

结构分析：

题目给定循环队列的大小为 k ，不论数组和链表，构建的大小为 k ，可行吗？

给定 front 和 rear 为0，front 标识队头，rear 标识队尾的下一个数据的位置，每当 入数据， rear++，向后走。

由于是循环队列，空间可以重复利用，当放置完最后一个数据后，rear需要回到头部。

那么问题来了，如何判空和判满 ？无论队列空或满，front 和 rear 都在一个位置。

1.解决方法一：
结构设计时，多加一个 size ，标识队列数据个数。
size=0为空，size=k就是满

2.解决方法二 ：
创建队列时，额外创建一个空间。

缺陷:单链表取尾不好取

数组：

对于数组，那么我们就开上 k + 1 个空间。

front 和 rear 分别标识队头和队尾。

每当入数据，rear 向后走一步，front 不动；每当出数据，front 向后走一步，rear 不动。当走过下标 k 处后，front 和 rear 的位置需要加以调整。比如，rear 下一步应该走到第一个空间：下标0位置。

队列空 时，front == rear。

队列满 时， rear 的下一个位置是 front 。平常只需要看 rear + 1 是否等于 front 即可。但是 放置的元素在 k 下标处时，此刻的 rear 需要特殊处理，rear 的位置会移动到 0 下标。经公式推导：(rear + 1) % (k + 1) == front 时，队列满，平常状况也不会受到公式影响。

入数据时，在 rear 位置入数据，然后 rear 向后移动，同样的，当入数据时到 k 下标的空间后，rear 需要特殊处理：rear %= k + 1。

出数据时，将 front 向后移动，当出数据到 k 下标的空间后，front 需要特殊处理：front %= k + 1。

取队头数据时，不为空取 front 处元素即可。

取队尾数据时，需要取rear 前一个位置，当队列非空时且 rear 不在 0下标时，直接取前一个；当队列非空且 rear 在 0 位置时，需要推导一下公式，前一个数据的下标为：(rear-1 + k+1) % (k + 1)，两种情况都适用。

typedef struct 
{
    int* a;//数组模拟环形队列
    int front;队头
    int rear;//队尾
    int k;//队列可存储的有效数据总数
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //申请一个环形队列
    obj->a = (int*)malloc(sizeof(int) * (k + 1));//开K=1层//开辟队列空间
    obj->front = obj->rear = 0;
    //初始时，队头和队尾均为0
    obj->k = k;//设置队列可存储的有效数据个数
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->rear;
    //当front和rear指向同一位置时，队列为空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if (myCircularQueueIsFull(obj))
    //队列已满，不能再插入数据
        return false;
    //插入数据
    obj->a[obj->rear++] = value;//放数据
    obj->rear %= (obj->k + 1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    //当队列为空时，无法再删除数据
        return false;
    //删除数据
    obj->front++;
    obj->front %= (obj->k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    //当队列为空时，无数据可返回
        return -1;
    else
    //返回队头指向的数据
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    //当队列为空时，无数据可返回
        return -1;
    else
    //返回rear指向位置的数据
        return obj->a[(obj->rear-1 + obj->k+1) % (obj->k + 1)];
    //可读性更强的方法
    //int x=obj->rear==0?obj->k:obj->rear-1;
    //rear=0 返回k的位置 反之返回rear-1
    //return obj->a[x];
}

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

链表：

其实对于循环队列而言，使用链表来构建是最清晰的。

注意 当构建链表时，构建的是 k + 1 个节点的 单向循环链表

front 和 rear 分别标识 队头 和 队尾。

队列空，front == rear 。

队列满，rear 的下一个节点就是 front 节点，rear->next == front。

入数据时，比数组设计简单很多，就直接让rear 迭代到下一个节点就可以。

出数据时，队列非空时，直接让front 迭代到下一个节点。

取队头元素时，如果非空，直接取 front 节点处的值。

取队尾元素时，如果非空，则从头开始迭代到rear 的前一个节点，取出元素。

需要注意 销毁的时候，由于链表不带头，所以销毁的时候可以从第二个节点开始迭代销毁，然后销毁第一个节点，最后销毁队列本身。这里比较细节，过会可以看一下代码。

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

typedef struct 
{
    CQNode* front;
    CQNode* rear;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj); 
// 创建节点
CQNode* BuyNode()
{
    CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
    newnode->next = NULL;
    
    return newnode;
}

MyCircularQueue* myCircularQueueCreate(int k) 
{
    // 构建长度 k + 1 的单向循环链表
    // 多开一个空间，防止边界问题
    CQNode* head = NULL, *tail = NULL;
    int len = k + 1;
    while (len--)
    {
        CQNode* newnode = BuyNode();
        if (tail == NULL)
        {
            head = tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
        tail->next = head;
    }
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front = cq->rear = head;
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if (myCircularQueueIsFull(obj))
        return false;
    // 直接插入在rear位置，rear后移
    obj->rear->data = value;
    obj->rear = obj->rear->next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front = obj->front->next;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->front->data;
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    // 取rear前一个元素
    CQNode* cur = obj->front;
    while (cur->next != obj->rear)
    {
        cur = cur->next;
    }
    return cur->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return obj->rear->next == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    // 销毁需要逐个销毁
    CQNode* cur = obj->front->next;
    // 从第二个节点开始，防止找不到头
    while (cur != obj->front)
    {
        CQNode* next = cur->next;
        free(cur);
        cur = next;
    }
    // 销毁
    free(cur);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(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

5.总结：

今天我们分析并完成栈和队列相关OJ题，通过分析明白了原理，愿这篇博客能帮助大家理解这些OJ题，因为栈和队列相关OJ题是还是有一些难度和细节需要注意。希望我的文章和讲解能对大家的学习提供一些帮助。之后会继续更新二叉树的相关知识点。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~