本节小编选了两道题来加深对栈和队列的认识理解！
有效的括号
方法1：直接用栈的结构（动态数组）
本题可以用栈这个结构来解答，将'(','{','[' 左括号压入栈中，然后取出栈顶元素与右括号')','}',']'匹配。不匹配的话，返回false,我们同时也要考虑空集的情况，即栈中元素为空，则返回false。
因为本题使用c语言写的，所以需要手撕栈的结构，可以运用上篇博客所写的栈的代码。
typedef char datatype; typedef struct stack { datatype* a; int top;//栈顶 int capacity; }ST; void STInit(ST* pst){ assert(pst); pst->a = NULL; //top指向栈顶数据的下一个位置,可以理解为下标 pst->top = 0; pst->capacity = 0; } void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } //容量检查 void Checkcapacity(ST* pst) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity==0?4:pst->capacity * 2; datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype)); if (temp == NULL) { perror("relloc fail"); return; } pst->a = temp; pst->capacity = newcapacity; } } //入栈和出栈 void STPush(ST* pst, datatype x) { assert(pst); Checkcapacity(pst); pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top>0); pst->top--; } //获取栈顶数据 datatype STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top-1]; } //判空 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0;//表达式判断 } //栈的数据个数 int STSize(ST* pst) { assert(pst); return pst->top; } bool isValid(char* s) { ST st; STInit(&st); while(*s){ //左括号入栈 if(*s=='('||*s=='{'||*s=='['){ STPush(&st,*s); } else{ //空集的情况，入栈结束后检查是否为空， if(STEmpty(&st)){ STDestory(&st); return false; } char top=STTop(&st); STPop(&st); //通过括号不匹配的情况判断 if((top=='('&& *s!=')') ||(top=='['&& *s!=']')||(top=='{'&& *s!='}')){ STDestory(&st); return false; //STPop(&st); } } s++; } //看最后是否栈为空，探讨左右括号数量不匹配的情况。 bool ret=(STEmpty(&st)); STDestory(&st); return ret; }
方法2：通过数组模拟栈来实现
使用一个字符数组作为栈，通过使用top标记栈顶的位置来实现栈的操作。在遍历字符串的过程中，遇到左括号就将其压入栈中，遇到右括号就与栈顶元素进行匹配。如果匹配成功，则将栈顶元素出栈，否则返回false。最后，如果栈为空，则说明所有的括号都匹配成功，返回true；否则，返回false。
bool isValid(char* s) { char stack[10000]; int top = -1; int len = strlen(s); for (int i = 0; i < len; i++) { if (s[i] == '(' || s[i] == '{' || s[i] == '[') { stack[++top] = s[i]; } else { if (top == -1) { return false; } if ((s[i] == ')' && stack[top] == '(') || (s[i] == '}' && stack[top] == '{') || (s[i] == ']' && stack[top] == '[')) { top--; } else { return false; } } } return top == -1; }
设计循环队列
方法1:使用动态数组
通过画图发现，当head==tail时，既是队列为空的条件，也是队列满的条件，所以我们可以通过增加一个空间来辅助判满，当tail+1=head时。还有另外一个方法，通过定义size变量，当size大小等于k时，也是队列满的时候。
在后续解决回绕的问题时，我们多次采用取模的方法，因为一个数除以比他大的数，取模后大小不变，当相等时，模为0，刚好回到起点处，完美的解决了回绕问题。
//循环队列先进先出 typedef struct { int *arr; int head; int tail;//指向尾下一个 int k; } MyCircularQueue; //创建循环队列 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //多开辟一个空间 obj->arr=(int*)malloc(sizeof(int)*(k+1)); obj->head=0; obj->tail=0; obj->k=k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { //头尾相等时队列为空 return (obj->head)==obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { //当tail+1=head时，为满，通过取模解决回绕问题 return((obj->tail+1)%(obj->k+1))==obj->head; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //队列满的时候，返回false if(myCircularQueueIsFull(obj)) return false; //插入一个数据，tail后移 obj->arr[obj->tail]=value; obj->tail++; //解决回绕，重头再来 obj->tail %=(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; //head前进，删除数据 obj->head++; //解决回绕问题 obj->head %=(obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->arr[obj->head]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else //分类讨论取尾元素 return obj->tail==0?obj->arr[obj->k]:obj->arr[obj->tail-1]; //return obj->arr[(obj->tail-1+obj->k+1)%(obj->k+1)];//取模的方法很巧妙 } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); free(obj); }
方法2：双向链表实现
使用双向链表实现，其中每个节点（Node）包含一个整数值（val），以及指向前一个节点和后一个节点的指针（prev和next）。循环队列（MyCircularQueue）包含一个指向队列头部和尾部的指针（head和tail），以及队列的大小（size）和容量（capacity）。
//节点建立 typedef struct Node { int val; struct Node* prev; struct Node* next; } Node; //双向链表实现队列 typedef struct { Node* head; Node* tail; int size; int capacity; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->head = NULL; obj->tail = NULL; obj->size = 0; obj->capacity = k; return obj; } //判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->size == 0; } //判满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size == obj->capacity; } //插入数据 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) { return false; } Node* newNode = (Node*)malloc(sizeof(Node)); newNode->val = value; newNode->prev = NULL; newNode->next = NULL; //队列为空时 if (myCircularQueueIsEmpty(obj)) { obj->head = newNode; obj->tail = newNode; newNode->next = newNode; newNode->prev = newNode; } // 不为空时 else { newNode->prev = obj->tail; newNode->next = obj->head; obj->tail->next = newNode; obj->head->prev = newNode; obj->tail = newNode; } obj->size++; return true; } //数据的删除 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return false; } Node* del = obj->head; if (obj->size == 1) { obj->head = NULL; obj->tail = NULL; } else { obj->head = obj->head->next; obj->head->prev = obj->tail; obj->tail->next = obj->head; } obj->size--; free(del); return true; } //头数据 int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->head->val; } //尾数据 int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->tail->val; } //队列销毁 void myCircularQueueFree(MyCircularQueue* obj) { Node* curr = obj->head; while (curr != obj->tail) { Node* next = curr->next; free(curr); curr = next; } obj->tail=NULL; free(obj); }
补充方法3：
使用链表（单链表）-投机取巧哈哈哈
不过这种方法没有关系到循环队列，也能通过该题目。
可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在 O(1)时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。
循环队列的属性如下:
head：链表的头节点，队列的头节点。
tail：链表的尾节点，队列的尾节点。
capacity：队列的容量，即队列可以存储的最大元素数量。
size：队列当前的元素的数量。
相比较与数组，我们使用了size的方法来判断队列为空为满的状态，
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //中间节点创建和函数主体 typedef struct node { int val; struct node* next; } node; //循环队列先进先出 typedef struct { node* head; node* tail; int size; int capacity; } MyCircularQueue; //创建循环队列 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->head=obj->tail=NULL; obj->size=0; obj->capacity=k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj->size==0) return true; else return false; //return obj->size==0; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size==obj->capacity; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; node* newnode=(struct node*)malloc(sizeof(node)); newnode->val=value; newnode->next=NULL; if(obj->size==0) { obj->head=newnode; obj->tail=newnode; } else{ obj->tail->next=newnode; obj->tail=newnode; } obj->size++; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; node*del=obj->head; obj->head=obj->head->next; free(del); obj->size--; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->head->val; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->tail->val; } void myCircularQueueFree(MyCircularQueue* obj) { node* curr = obj->head; while (curr != NULL) { node* next = curr->next; free(curr); curr = next; } obj->size = obj->capacity = 0; obj->head = obj->tail = NULL; free(obj); } //手动测试部分 int main() { MyCircularQueue* obj = myCircularQueueCreate(5); myCircularQueueEnQueue(obj, 1); myCircularQueueEnQueue(obj, 2); myCircularQueueEnQueue(obj, 3); myCircularQueueEnQueue(obj, 4); myCircularQueueEnQueue(obj, 5); printf("%d\n", myCircularQueueRear(obj)); printf("%d\n", myCircularQueueFront(obj)); myCircularQueueDeQueue(obj); printf("%d\n", myCircularQueueFront(obj)); myCircularQueueFree(obj); return 0; }
OK，本节内容到此结束，各位友友留下三连和评论吧，有更好的方法希望各位佬私信交流！！！
