【栈和队列OJ题】有效的括号用队列实现栈用栈实现队列设计循环队列
📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待
文章目录
- OJ题
- 1.有效的括号
- 1.1 思路：
- 1.2 易错情况
- 2.用队列实现栈
- 2.1思路：
- 3.用栈实现队列
- 4.设计循环队列
- 4.1思路：
- 结构分析：
- 数组：
- 链表：
- 5.总结：
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
}
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 入数据时，往不为空的队列入数据，如果两个队列都为空，则入任意一个。
- 出数据时，将不为空的队列中的元素转移到空队列中直到队列中元素只剩一个，出栈原先非空队列的数据，原先非空队列变为空，出栈数据就是模拟栈的栈顶数据。
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
}
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);
}
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);//再释放动态开辟的结构体
}
链表：
其实对于循环队列而言，使用链表来构建是最清晰的。
注意 当构建链表时，构建的是 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);
*/
5.总结：
今天我们分析并完成栈和队列相关OJ题，通过分析明白了原理，愿这篇博客能帮助大家理解这些OJ题，因为栈和队列相关OJ题是还是有一些难度和细节需要注意。希望我的文章和讲解能对大家的学习提供一些帮助。之后会继续更新二叉树的相关知识点。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
