栈的括号匹配与循环队列

括号匹配与循环队列是栈与队列这一部分的难点也是必须要学会的内容，这一篇博客我们就来带领大家完成这两个内容。

（一）栈的括号匹配

（1）题目描述

首先我们分析一下题目，题目意思也就是我们先输入一个字符串，然后我们需要判断其中的括号是否匹配，例如‘{’与‘}’这一对是匹配的。

（2）思路

首先这道题用栈来解决，因为栈可以实现后进的先出，我们的思路是左括号就一直入栈，当遇到右括号的时候就将栈顶元素取出，然后判断与右括号是否匹配，一直重复上述操作，但这里需要注意的是这里有多种情况

第一种情况不用说，符合上面的逻辑，
第二种情况我们就需要判断当前栈为不为空，如果当前栈空了，且右括号还有，则匹配失败，
第三种情况当入完我们的栈，但一直没有与右括号消掉，所以我们需要额外判断栈是否为空，如果出了循环且栈不为空，则匹配失败，
第四种情况再消掉几组后与第二种情况一致，
第五种情况消掉几组后与第二种情况一致，
这就是我们这道题的全部思路过程。

（3）代码实现

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef char type;
typedef struct Stack
{type* arr;int size;int capacity;
}ST;
void StackInit(ST* ptr)
{ptr->arr = NULL;ptr->size = ptr->capacity = 0;
}
void StackDestory(ST* ptr)
{free(ptr->arr);ptr->arr = NULL;ptr->capacity = ptr->size = 0;
}
void StackPush(ST* ptr, type x)
{if (ptr->capacity == ptr->size){int newcapacity = ptr->capacity == 0 ? 4 : 2 * ptr->capacity;type* tep = (type*)realloc(ptr->arr, sizeof(int) * newcapacity);if (tep == NULL){perror("realloc");return;}ptr->arr = tep;ptr->capacity = newcapacity;}ptr->arr[ptr->size++] = x;
}
void StackPop(ST* ptr)
{ptr->size--;
}
type StackTop(ST* ptr)
{return ptr->arr[ptr->size - 1];
}
bool StackEmpty(ST* ptr)
{return ptr->size == 0;
}int main()
{char arr[100];gets(arr);ST st;StackInit(&st);int k = 0;int flag = 1;while (arr[k] != '\0'){if (arr[k] == '{' || arr[k] == '(' || arr[k] == '['){StackPush(&st, arr[k++]);}else if (arr[k] == '}' || arr[k] == ')' || arr[k] == ']'){if (!StackEmpty(&st)){char ch = StackTop(&st);StackPop(&st);if ((ch == '{' && arr[k] != '}') || (ch == '(' && arr[k] != ')') || (ch == '[' && arr[k] != ']')){flag = 0;break;}}else{flag = 0;break;}k++;}elsek++;}if (flag == 1){if (!StackEmpty(&st))printf("0");elseprintf("1");}else{printf("0");}StackDestory(&st);return 0;
}

上面是栈的实现，下面是匹配的逻辑过程，此外flag是用来判断栈是否为空的标志。

（4）题目链接

https://leetcode.cn/problems/valid-parentheses/

这道题与上面不是同一道题目，但是思路是一样的，大家只需要稍微更改一下即可。

（二）循环队列的实现

（1）题目描述

（2）思路

这里我们有两种思路可以实现我们的循环队列，
（1）、一种是像顺序表一样设一个size来记录当前队列里的元素个数，当size=0队列为空，size=k队列满，通过size来检查队列当前的状态
（2）、另一种方式是多开一个空间，也就是我们开了k+1个空间，但我们只存放k个元素，

（3）代码实现

typedef struct 
{int*arr;int front;int tail;int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue*ptr=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));ptr->arr=(int*)malloc(sizeof(int)*(k+1));ptr->front=ptr->tail=0;ptr->k=k+1;return ptr;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj->tail+1)%obj->k==obj->front)return true;return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(myCircularQueueIsFull(obj))return false;obj->arr[obj->tail++]=value;obj->tail%=obj->k;return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(obj->front==obj->tail)return false;obj->front++;obj->front%=obj->k;return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->arr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->tail==0?obj->arr[obj->k-1]:obj->arr[obj->tail-1];
}
void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->arr);obj->arr=NULL;obj->front=obj->tail=0;obj->k=0;
}

这里需要注意的是，原来的题目中判满与判空都在后面的函数，如果我们想要在前面的插入删除使用这两个函数的话有两种方式：1、

（4）题目链接

https://leetcode.cn/problems/design-circular-queue/