作者：一个喜欢猫咪的的程序员
专栏：《Leetcode》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
20. 有效的括号
20. 有效的括号
https://leetcode.cn/problems/valid-parentheses/
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例：
思路：
本题我们可以利用栈的方式很好的解决。当s为左括号的时候入栈，右括号的时候出栈进行比较。
当s为全右括号的时候，我们出栈会有报错，因此我们在这之前利用StackEmpty进行判空一下。
可以参考一下我实现栈的博客：
代码实现:
typedef char STDatatype; typedef struct Stack { STDatatype* a; int capacity; int top; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDatatype x); void StackPop(ST* ps); STDatatype StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST*ps); void StackInit(ST* ps) { assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); if (ps->a == NULL) { perror("Init fail"); exit(-1); } ps->capacity = 4; ps->top = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); if (ps->capacity == ps->top) { STDatatype* tmp = (STDatatype*)realloc(ps->a,ps->capacity * 2 * sizeof(ps->a)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool isValid(char * s){ ST st; StackInit(&st); while(*s) { if(*s=='{'||*s=='['||*s=='(') { StackPush(&st,*s); ++s; } else { if(StackEmpty(&st)) { StackDestory(&st); return false; } char top=StackTop(&st); StackPop(&st); if((*s=='}'&&top!='{')|| (*s==']'&&top!='[')|| (*s==')'&&top!='(')) { return false; } else { ++s; } } } bool ret=StackEmpty(&st); StackDestory(&st); return ret; }
622. 设计循环队列
622. 设计循环队列
https://leetcode.cn/problems/design-circular-queue/
题目描述：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
思路：
我们假设开k个空间，我们可以多开一个开k+1个空间。
当我们需要判空或者判满的时候，判空size==0，判满size==k。
当我们需要添加数据时，先判满，然后不为满时分为两种情况，以k=3为例。
一种是rear位置直接添加然后右移就好，还有一种情况当rear从下标为3的位置到下标为0的位置，
obj->rear = (obj->rear+1)%(obj->k)这样可以实现循环。
出数据时，先判空，但front的操作跟rear的操作差不多。
myCircularQueueRear函数是要出队尾的数据，当rear在下标为0的位置时，较为特殊;
int rear=(obj->rear==0?obj->k-1:obj->rear-1); return obj->a[rear];
这个写法较为简单
也有另外一种写法，较为巧妙
return obj->a[(obj->rear + obj->k-1) % (obj->k)];
代码实现：
typedef struct { int* a; int rear; int front; int k; int size; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->rear = obj->front = 0; obj->k = k+1; obj->size=0; obj->a = (int*)malloc(sizeof(int) * obj->k); return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return (obj->size==0); } bool myCircularQueueIsFull(MyCircularQueue* obj) { if(obj->size==obj->k-1) return true; return false; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { assert(obj); if (myCircularQueueIsFull(obj)) return false; else { obj->a[obj->rear] = value; obj->rear = (obj->rear+1)%(obj->k); obj->size++; return true; } } bool myCircularQueueDeQueue(MyCircularQueue* obj) { assert(obj); if (myCircularQueueIsEmpty(obj)) return false; else { obj->front++; obj->front %= (obj->k); obj->size--; return true; } } int myCircularQueueFront(MyCircularQueue* obj) { assert(obj); if (myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { assert(obj); if (myCircularQueueIsEmpty(obj)) return -1; int rear=(obj->rear==0?obj->k-1:obj->rear-1); return obj->a[rear]; //return obj->a[(obj->rear + obj->k-1) % (obj->k)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
