目录
有效的括号
有效的括号【代码】
用队列实现栈
用队列实现栈【代码】
用栈实现队列
用栈实现队列【代码】
设计循环队列
有效的括号
https://leetcode.cn/problems/valid-parentheses/submissions/551394950/
思路：把左括号放到栈里，取出来栈顶和右括号匹配，匹配上了就出栈，然后在取出栈顶和下一个右括号匹配，一直匹配下去，
创建一个栈用来存放左括号，然后把字符串的首地址s给ps，让ps遍历到\0。
来看看循环里面，
第一步：判断把左括号全部放进栈里。
第二步：判断栈里是不是空，是空就没必要匹配了，没有左括号，直接返回false。
第三步：走到第三步，说明左括号全部放进栈里了，然后取出栈顶给ch，
然后左括号和右括号进行匹配，匹配成功就出栈，匹配不成功就销毁，然后返回false。
解决只有一个左括号的情况。
布尔判断栈里是不是空,是空把true给tab，不是空返回false给tab。
销毁空间后，返回tab。
有效的括号【代码】
typedef char data;typedef struct stack{data* arr;int koj;//空间大小int top;//栈顶}SL;//初始化void csh(SL* r){r->arr = NULL;r->koj = r->top = 0;}//入栈void push(SL* r, data x){//判断空间够不够if (r->koj == r->top){int koj1 = r->koj == 0 ? 4 : 2 * r->koj;SL* tab = (SL*)realloc(r->arr, koj1 * sizeof(SL));if (tab == NULL){perror("realloc");exit(1);}r->arr = tab;r->koj = koj1;}r->arr[r->top] = x;r->top++;}bool buer(SL* r){assert(r);return r->top == 0;}//出栈void pop(SL* r){assert(r);assert(!buer(r));--r->top;}//取栈顶data qzd(SL* r){assert(r);assert(!buer(r));return r->arr[r->top-1];}//取有效个数data size(SL* r){assert(r);return r->top;}//销毁void xiaoh(SL* r){assert(r);if (r->arr != NULL){free(r->arr);}r->arr = NULL;r->koj = r->top = 0;}//上面是栈需要的函数//下面是实现代码bool isValid(char* s) { //创建一个栈 SL add; //把s给ps char*ps=s; //循环让ps往后走 while(*ps!='\0') { //判断把左括号放进栈里 if(*ps=='(' || *ps=='[' || *ps=='{') { push(&add,*ps); } else { //判断栈顶是不是空，是空返回false。 if(buer(&add)) { return false; } //取出左括号放进ch来 char ch = qzd(&add); //判断左括号和右括号匹不匹配 if((*ps==')'&&ch=='(') ||( *ps==']'&&ch=='[') || (*ps=='}'&& ch=='{')) { //匹配出栈 pop(&add); } else {//不匹配直接销毁返回false xiaoh(&add); return false; } } ps++; } //布尔判断栈里是不是为空，是空把true赋值给tab。 char tab = buer(&add) == true; xiaoh(&add); return tab;}用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
实现前先导入队列的函数
思路：创建2个队列
入栈不为空的队列Q1。
出栈的话把Q1的size-1的数据1和2插入Q2的队列，我们就可以把3出栈了。
https://leetcode.cn/problems/implement-stack-using-queues/
第一步：先创建2个队列来实现栈。
第二步：创建ps指向栈，然后初始化这2个队列。
入栈，为不为空的队列，入数据到队列。
if用布尔判断Q1队列是不是空，是空往Q2队列入数据，调用入队列函数。
第一步：把Q1给空队列，把Q2给不为空的队列。
第二步：判断Q1如果不为空，2个交换，把Q1给buko，把Q2给ko。
第三步：循环把有效个数-1的数据，给到为空的队列。
取出队头数据给tab,然后入队到空队列，再把不为空的队列出队。
第四步：把队列的最后一个数据，保存到pop，然后出队列，返回pop。
布尔判断，找不为空的队列，取出队尾数据，返回队尾。
布尔判断2个队列是不是空，2个都为真返回true,有1个或2个为假，返回false。
销毁直接调用销毁队列的函数就行了，然后把obj销毁,把obj置为NULL。
用队列实现栈【代码】
typedef int data;typedef struct queuedata//单链表{data arr;//存放的数据struct queuedata* p;//指向下一个节点}queuedata;typedef struct Queue{queuedata* to; //队头——单链表的 头节点queuedata* wei;//队尾——单链表的 尾节点int size; //有效个数}Queue;//初始化void csh(Queue* r){assert(r);r->to = r->wei = NULL;r->size = 0;}//入队尾void dui_wei(Queue* r,data x){assert(r);//申请单链表空间queuedata* tab = (queuedata*)malloc(sizeof(queuedata));if (tab == NULL){perror("malloc");exit(1);}//把x赋值给新申请空间的arrtab->arr = x;tab->p = NULL;//入队//判断队尾是不是空if (r->wei == NULL){//是空，队头队尾指向新申请的空间r->to = r->wei = tab;}else//不是空{//队尾p指向新申请的空间r->wei->p = tab;//队尾走到新申请的空间r->wei = r->wei->p;}//有效个数加1r->size++;}//布尔类型bool buer(Queue* r){assert(r);return r->to == NULL;}//出队,头void dui_to(Queue* r){assert(r);//布尔类型，！把真变假，把假变真assert(!buer(r));//判断队头等于队尾，就说明只有一个节点if (r->to == r->wei){//直接释放空间free(r->to);//把队头和队尾置为空r->to = r->wei = NULL;}else{//把队头的下一个节点给tabqueuedata* tab = r->to->p;//释放当前队头节点free(r->to);//把tab节点给队头r->to = tab;}//有效个数减1--r->size;}//取队头数据data qto(Queue* r){assert(r);assert(!buer(r));return r->to->arr;}//取尾data qwei(Queue* r){assert(r);assert(!buer(r));return r->wei->arr;}//有效个数data size(Queue* r){assert(r);return r->size;}//销毁void xiaoh(Queue* r){assert(r);//assert(!buer(r));//把队头给tabqueuedata* tab = r->to;//循环销毁单链表while (tab != NULL){//add保存头节点的下一个节点queuedata* add = tab->p;//释放头节点free(tab);//把add给tabtab = add;}//把队头和队尾置为空r->to = r->wei = NULL;//有效个数赋值为0r->size = 0;}//上面是队列的函数///下面是实现代码typedef struct { //创建2个队列来实现栈 Queue Q1; Queue Q2;} MyStack;//栈初始化MyStack* myStackCreate() { //创建ps指向栈 MyStack*ps=(MyStack*)malloc(sizeof(MyStack)); //初始化这2个队列 csh(&ps->Q1); csh(&ps->Q2); return ps;}//入栈void myStackPush(MyStack* obj, int x) { //往不为空的队列插入数据 if(!buer(&obj->Q1)) { dui_wei(&obj->Q1, x); } else { dui_wei(&obj->Q2, x); }}//出栈int myStackPop(MyStack* obj) { //空 Queue* ko = &obj->Q1; //不为空 Queue* buko = &obj->Q2; //找不为空的队列 if(!buer(&obj->Q1)) { buko = &obj -> Q1; ko = &obj -> Q2; } //把有数据的队列中size-1个数据导入到空队列中 while(size(buko) > 1) { //取队头给tab int tab = qto(buko); //把tab的数据给 ko空队列 dui_wei(ko , tab); //出队，头 dui_to(buko); } //不为空的队列还剩下一个数据，给pop int pop = qto(buko); //最后一个数据出栈 dui_to(buko); //返回pop return pop;}//取栈顶元素int myStackTop(MyStack* obj) { //找不为空的队列，取出队尾数据 if(!buer(&obj->Q1)) { return qwei(&obj->Q1); } else { return qwei(&obj->Q2); }}bool myStackEmpty(MyStack* obj) { //用布尔判断2个队列是不是空 return buer(&obj->Q1) && buer(&obj->Q2);}//销毁void myStackFree(MyStack* obj) { //直接调用销毁队列的函数就行了 xiaoh(&obj->Q1); xiaoh(&obj->Q2); //把我们申请的ps销毁，obj就是ps，返回了ps然后obj接收。 free(obj); //置为空 obj=NULL;}/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj);*/用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
实现前先导入栈的函数
思路：用2个栈Q1,Q2，
入队列：往Q1导入数值，
出队列（头）：判断Q2是不是空，是就循环取出Q1栈顶，导入到Q2，Q2再出栈，出的就是队头了，对了还要先保存队头，再返回队头的数据。
取队头数据：判断Q2是不是空，不是空就说明数据已经导入到Q2了，直接取栈顶。
myQueueEmpty：判断队列是不是空。
销毁：调用销毁函数，销毁2个栈，再把申请的obj空间释放，然后置为空。
第一步：创建2个栈。
第二步：创建ps空间指向Q1和Q2，
然后初始化这2个栈，返回ps。
直接调用，入栈函数，为Q1导入数据就行了。
判断Q2栈是不是空，是空的话循环把Q1的全部数值，导入到Q2，
取出Q2栈顶给tab，Q2出栈，返回tab。
判断Q2栈是不是空，是空的话循环把Q1的全部数值，导入到Q2
返回Q2栈顶的元素就行了。
判断队列是不是空，是空返回false，不是空返回true。
把Q1和Q2的栈销毁，然后销毁obj，把obj置为空。
用栈实现队列【代码】
typedef int data;typedef struct stack{data* arr;//存放数值int koj; //空间int top; //栈顶}stack;//初始化void stack_csh(SL* r){assert(r);r->arr = NULL;r->koj = r->top = 0;}//入栈void stack_push(stack* r, data x){assert(r);//空间大小等于栈顶，就说明空间不够if (r->koj == r->top){int koj1 = r->koj == 0 ? 4 : 2 * r->koj;stack* tab = (stack*)realloc(r->arr, sizeof(stack));if (tab == NULL){perror("realloc");exit(1);}//把新申请的空间给rr->arr = tab;r->koj = koj1;}//空间够直接入栈r->arr[r->top] = x;r->top++;}//布尔类型bool buer(stack* r){assert(r);return r->top == 0;}//出栈void stack_pop(stack* r){assert(r);//布尔类型assert(!buer(r));r->top--;}//取出栈顶data stack_top(stack* r){assert(r);assert(!buer(r));return r->arr[r->top - 1];}//有效个数data stack_size(stack* r){assert(r);return r->top;}//销毁void xiaoh(stack* r){assert(r);if (r->arr != NULL){free(r->arr);}r->arr = NULL;r->koj = r->top = 0;}//上面是栈的函数///下面是实现代码typedef struct { //创建2个栈 stack Q1; stack Q2;} MyQueue;//初始化MyQueue* myQueueCreate() { //创建指针指向Q1和Q2 MyQueue* ps = (MyQueue*)malloc(sizeof(MyQueue)); //初始化2个栈 stack_csh(&ps->Q1); stack_csh(&ps->Q2); //返回ps return ps;}//入栈（入队列）void myQueuePush(MyQueue* obj, int x) { //调用入栈函数，为Q1入栈 stack_push(&obj->Q1 , x);}//出栈（出队列，头）int myQueuePop(MyQueue* obj) { //判断Q2是不是空，不是空说明Q2栈里有数据 if( buer(&obj->Q2) ) { //是空，循环取出Q1的数值，导入Q2栈里 while(!buer(&obj->Q1)) { //入栈到Q2 取出Q1栈顶 stack_push(&obj->Q2,stack_top(&obj->Q1)); //Q1出栈 stack_pop(&obj->Q1); } } //取出Q2的栈顶给tab（取队头） int tab = stack_top(&obj->Q2); //Q2出栈 stack_pop(&obj->Q2); return tab; }//取栈顶（队头）int myQueuePeek(MyQueue* obj) { //判断Q2是不是空，不是空说明Q2栈里有数据 if( buer(&obj->Q2) ) { //是空，循环取出Q1的数值，导入Q2栈里 while(!buer(&obj->Q1)) { //入栈到Q2 取出Q1栈顶 stack_push(&obj->Q2,stack_top(&obj->Q1)); //Q1出栈 stack_pop(&obj->Q1); } } //返回Q2的栈顶（返回队头） return stack_top(&obj->Q2);}bool myQueueEmpty(MyQueue* obj) { //判断这2个栈是不是都为空（判断队列是不是空） return buer(&obj->Q1) && buer(&obj->Q2);}void myQueueFree(MyQueue* obj) { //销毁 xiaoh(&obj->Q1); xiaoh(&obj->Q2); //也把obj销毁 free(obj); obj=NULL;}/** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj);*/设计循环队列
https://leetcode.cn/problems/design-circular-queue/description/
这个队列底层使用数组，比较好实现。
结构体的参数，数组，头，尾，空间大小。
申请ps的一个结构体，
给arr申请一个数值的空间，我们申请的数值空间必须多一块空间，方便5%5等于0。
初始化：把头尾初始化为0，空间大小初始化为k，k就是4。
第一步：先判断队列是不是满了，满了直接返回false，没有满插入数据。
第二步：为arr数组wei下标位置插入数据，然后++，参考【1%5=1, 2%5=2 ，3%5=3, 4%5=4, 5%5=0】。
当wei走到下标为5，5%5=0,所以就会回到0，返回true。
第一步：判断队列是不是空，是空直接返回false。
第二步：头直接++就好了，1%5=1, 2%5=2 ，3%5=3, 4%5=4, 5%5=0
当to走到下标为5，5%5=0,所以就会回到0，返回true。
先判断是不是空，不是空返回头，是空返回-1。
第一步：判断队列是不是空。
第二步：把wei-1的数据赋值tab，为什么是wei-1呢？
上面这一张图，我们可以看到插入数据后就++了，所以我们取队尾，wei-1。
第三步：判断尾下标是不是0，这里是一种特殊情况0-1=-1,-1没有下标，
我们直接把空间大小给tab就是下标为4这个元素了。
返回arr下标为tab的数值。
设计循环队列代码
typedef struct { int *arr; int to;//头 int wei;//尾 int kojdax;//空间大小} MyCircularQueue;//初始化MyCircularQueue* myCircularQueueCreate(int k) { //申请空间 MyCircularQueue* ps = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); // 4 * 5 = 20,就是5个空间 ps->arr = (int*)malloc(sizeof(int) * (k + 1)); //初始化 ps->to = ps->wei = 0; ps->kojdax = k; return ps;}bool myCircularQueueIsFull(MyCircularQueue* obj) { //判断队列是不是满了，等于头就说明满了 return (obj->wei+1) % (obj->kojdax+1) == obj->to;}//入队列bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //队列满了不能插入数据 if(myCircularQueueIsFull(obj)) { return false; } //在wei位置插入数据，然后++ obj->arr[obj->wei++] = value; //5 % 5 = 0，rear走到5下标的时候回到下标为0的位置。 obj->wei %= obj->kojdax + 1; return true;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) { //等于就说明队列是空 return obj->to == obj->wei;}//出队列bool myCircularQueueDeQueue(MyCircularQueue* obj) { //队列为空 if(myCircularQueueIsEmpty(obj)) { return false; } //队列不为空 //头往后走就行 obj->to++; //会越界所以:5 % 5 = 0，to走到5下标的时候回到下标为0的位置。 obj->to %= obj->kojdax + 1; return true;}//取队头int myCircularQueueFront(MyCircularQueue* obj) { //判断队列是不是空 if(myCircularQueueIsEmpty(obj)) { return -1; } //返回头 return obj->arr[obj->to];}//取队尾int myCircularQueueRear(MyCircularQueue* obj) { //判断队列是不是空 if(myCircularQueueIsEmpty(obj)) { return -1; } //把wei-1的数据给tab int tab = obj->wei - 1; //尾等于下标0 if(obj->wei == 0) { //把有效个数4给tab tab = obj -> kojdax; } //返回tab return obj->arr[tab];}//销毁void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); free(obj); obj=NULL;}