今天接着栈&队列OJ题目。
【1】括号匹配问题
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路分析
- 左括号入栈
- 右括号与栈顶元素匹配（记得Pop)（顺序匹配）
- 考虑左/右括号多了（数量匹配）
易错总结
- 同一个域不能存在同名变量
- 类型的匹配度100%
- 字符串的比较用strcmp 字符比较==即可（字符的比较都是ASCII码）
- 出栈的性质：必须出了栈顶元素才能访问下一个元素
- 括号的匹配不是==
*s == ')'&& top != '(' || *s == '}'&& top != '{'|| *s == ']'&& top != '['
- return 之前都必须free ，不然会造成内存泄露的问题！！非常严重 先销毁再返回！！
Stack.h&Stack.c手撕栈
//stack.h #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef char STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; void STInit(ST* pst); void STDestroy(ST* pst); void STPush(ST* pst, STDatatype x); void STPop(ST* pst); STDatatype STTop(ST* pst); bool STempty(ST* pst); int STSize(ST* pst); //stack.c void STInit(ST* pst) { assert(pst); pst->a = 0; pst->top = 0; pst->capacity = 0; } void Createcapacity(ST* pst) { if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity; STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(ST) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } } void STPush(ST* pst, STDatatype x) { assert(pst); Createcapacity(pst); pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } STDatatype 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; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; }
isValid括号匹配
bool isValid(char* s) { ST stack; STInit(&stack); //遍历字符串 while(*s) { //左括号入栈 if(*s == '(' || *s == '{' || *s == '[' ) { STPush(&stack,*s); } else//右括号 { //数量匹配 左括号<右括号 if(STempty(&stack)) { STDestroy(&stack); return false; } //右括号取栈顶的元素比较 //记住要Pop char top=STTop(&stack); STPop(&stack); //因为true 不是一次匹配成功 flase是依次成功 if( *s == ')'&& top != '(' || *s == '}'&& top != '{'|| *s == ']'&& top != '[' ) { STDestroy(&stack); return false; } } s++; } //数量匹配，左括号>右括号 STDestroy(&stack); return STempty(&stack); }
【2】设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满
//用数组实现+多开辟一个空间不放元素 typedef struct { int*a; int front; int back;//数组下标 int k;//循环队列的最多放置数据 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); int*tmp=(int*)malloc(sizeof(int)*(k+1));//多开辟一个空间 obj->a=tmp; obj->front=0; obj->back=0;//指向最后一个元素的下一个 obj->k=k; return obj; } //判断循环队列是否为空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->back;//==0 } //判断是否为满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1) % (obj->k+1) == obj->front;//back+1=front //操作符优先级问题 } //插入元素 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj))//true 满了 { return false; } obj->a[obj->back] = value; obj->back++; obj->back %= obj->k+1;//处理 //obj->front+1%=obj->k+1;//处理左边不能为计算表达式 return true; } //删除元素 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } else { 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 //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]; return obj->a[(obj->back+obj->k)%(obj->k+1)]; } //释放空间 void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); obj=NULL; } /** * 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月分才会频繁继续更新博文了，要去准备英语和西语的考试，大家要乖乖敲代码哦！
