20. 有效的括号
题目
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
题目链接：有效的括号
解法一：建立栈解决
代码如下：
typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void StackDestroy(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->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); ps->top--; } STDataType StackTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } bool isValid(char * s){ ST st; StackInit(&st); while(*s) { if(*s == '(' || *s == '{' || *s == '[') { StackPush(&st,*s); ++s; } else { if(StackEmpty(&st)) { StackDestroy(&st); return false; } STDataType top = StackTop(&st); StackPop(&st); if((*s == '}') && top != '{' || (*s == ']') && top != '[' || (*s == ')') && top != '(') { StackDestroy(&st); return false; } else { ++s; } } } bool ret=StackEmpty(&st); StackDestroy(&st); return ret; }
在C语言中，因为没有现成的栈可以调用，所以这里首先我们建立一个栈结构及各种操作函数建立，以便于这里的函数实现进行调用，这里我们首先建立一个栈st，初始化栈st，第一层while循环判定数组中有没有元素，进入循环后如果首元素为左括号入栈，并将指针位置后移一位，再看else语句，如果栈为空，说明上一段条件语句没执行，直接返回false，不执行这句，说明栈中有元素，则先将栈顶值记录，再删除栈顶元素，再进行括号匹配，如果s此时指向的是右括号并且top不等于左括号，说明不匹配，等于就将指针位置后移再进行匹配，最后遍历完，如果栈为空，则都匹配，否则就不匹配。这种写法代码虽然长，但是相对来说很好理解。
如下图：
解法二：数组模拟栈解决
代码如下：
char pairs(char a) { if(a==')') return '('; if(a=='}') return '{'; if(a==']') return '['; return 0; } bool isValid(char * s){ int n=strlen(s); if(n%2==1) return false; int stk[n],i=0,top=0; for(i=0;i<n;i++) { char ch=pairs(s[i]); if(ch) { if(top==0||stk[top-1]!=ch) return false; top--; } else stk[top++]=s[i]; } return top==0; }
这里我们创建一个pairs函数进行返回匹配，如果a是右括号则返回左括号，否则返回0，再看我们的主调函数，我们首先记录字符串长度，如果长度为奇数，直接返回false，如果没进入条件语句，则执行下面语句，首先我们建立字符串长度的数组stk，然后就是一个for循环，循环次数为字符串长度（防止最坏情况，全为左括号），首先记录第一个字符调用pairs函数进行匹配，如果是左括号，返回0；进入else语句，stk首元素记录第一个字符，top+1，再进行第二次循环，如果为右括号，则ch记录为左括号，进行匹配，如果相同，top-1，不相同则直接返回false，循环结束，如果top等于0，则返回ture，否则为false，其实这种写法原理和上面是一样的，只不过编写形式不一样。
如下图：
225. 用队列实现栈
题目
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
题目链接：用队列实现栈
解法：两个队列实现栈
代码如下：
typedef struct { int queue1[100]; int queue2[100]; int front1; int front2; int rear1; int rear2; } MyStack; MyStack* myStackCreate() { MyStack* stack=malloc(sizeof(MyStack)); stack->front1=0; stack->front2=0; stack->rear1=0; stack->rear2=0; return stack; } void myStackPush(MyStack* obj, int x) { obj->queue1[(obj->rear1)++]=x; } int myStackPop(MyStack* obj) { int front1=obj->front1; int front2=obj->front2; int rear1=obj->rear1; int rear2=obj->rear2; while(rear1-front1>1) { obj->queue2[rear2++]=obj->queue1[front1++]; } int top=obj->queue1[front1++]; while(front2!=rear2) { obj->queue1[rear1++]=obj->queue2[front2++]; } obj->front1=front1; obj->front2=front2; obj->rear1=rear1; obj->rear2=rear2; return top; } int myStackTop(MyStack* obj) { return obj->queue1[obj->rear1-1]; } bool myStackEmpty(MyStack* obj) { return obj->queue1[obj->front1]==obj->queue2[obj->front2]; } void myStackFree(MyStack* obj) { obj->front1=obj->front2=obj->rear1=obj->rear2=0; }
具体思路如下图：
入栈
入栈
出栈
232. 用栈实现队列
题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
解法：两个栈实现队列
代码如下：
typedef struct { int* stk; int stksize; int stkcapacity; }Stack; Stack* createStack(int capacity) { Stack* ret=malloc(sizeof(Stack)); ret->stk=malloc(sizeof(int)*capacity); ret->stksize=0; ret->stkcapacity=capacity; return ret; } void stackpush(Stack* obj,int x) { obj->stk[obj->stksize++]=x; } void stackpop(Stack* obj) { obj->stksize--; } int stacktop(Stack* obj) { return obj->stk[obj->stksize-1]; } bool stackempty(Stack* obj) { return obj->stksize==0; } void stackfree(Stack* obj) { free(obj->stk); } typedef struct { Stack* inqueue; Stack* outqueue; } MyQueue; MyQueue* myQueueCreate() { MyQueue* ret=malloc(sizeof(MyQueue)); ret->inqueue=createStack(100); ret->outqueue=createStack(100); return ret; } void inout(MyQueue* obj) { while(!stackempty(obj->inqueue)) { stackpush(obj->outqueue,stacktop(obj->inqueue)); stackpop(obj->inqueue); } } void myQueuePush(MyQueue* obj, int x) { //stackpush(obj->inqueue,x); obj->inqueue->stk[obj->inqueue->stksize++]=x; } int myQueuePop(MyQueue* obj) { if(stackempty(obj->outqueue)) { inout(obj); } int x=stacktop(obj->outqueue); stackpop(obj->outqueue); return x; } int myQueuePeek(MyQueue* obj) { if(stackempty(obj->outqueue)) { inout(obj); } return stacktop(obj->outqueue); } bool myQueueEmpty(MyQueue* obj) { return (stackempty(obj->inqueue)&&stackempty(obj->outqueue)); } void myQueueFree(MyQueue* obj) { stackfree(obj->inqueue); stackfree(obj->outqueue); }
具体思路如下图：
622. 设计循环队列
题目
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
题目链接：设计循环队列
解法一：数组
代码如下：
typedef struct { int front;//队首 int rear;//队尾 int capacity;//容量 int* elem;//元素 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* ret=malloc(sizeof(MyCircularQueue)); ret->capacity=k+1; ret->elem=malloc(sizeof(int)*ret->capacity); ret->front=ret->rear=0; return ret; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if((obj->rear+1)%obj->capacity==obj->front) return false; obj->elem[obj->rear]=value; obj->rear=(obj->rear+1)%obj->capacity; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(obj->front==obj->rear) return false; obj->front=(obj->front+1)%obj->capacity; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(obj->front==obj->rear) return -1; return obj->elem[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(obj->front==obj->rear) return -1; return obj->elem[(obj->rear-1+obj->capacity)%obj->capacity]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%obj->capacity==obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->elem); free(obj); }
首先是队列结构体的建立，然后是队列初始化创建，和普通队列不同的是这里的capacity是给定值k+1，这里的用处在后面的函数会体现。
入队列：首先判定队尾下标+1模上容量等于队首下标，说明队列已经满了，返回false。入队为队尾值为下标，更新队尾值为+1模上容量，而不是直接++。
出队列：题目要求是直接删除，返回逻辑值，所以这里直接删除队首值对应下标元素，同样是队首值+1模上容量，实际此时并没删除，但是等到队尾值对应下标访问该位置入队列时会直接覆盖，而且此时这个位置也不是合法位置，所以不需要直接将其删除。
返回队首值：题目要求队列为空返回-1，只有队首等于队尾时，队列才为空，否则直接返回队首值对应下标元素即为队首。
返回队尾值：为空和上面一样，否则返回队尾值-1加上容量值再%上容量，很多人看不懂这句，举个例子，假设这时队列是满的，那么如果队尾值为0，减去1的话为负值，再去取余数就出现了越界，而且返回值是错的。
返回队列是否为空：返回队首队尾是否相等即可
返回队列是否已满：队尾值+1模上容量如果等于front，那就满了
讲到这你会发现容量的初始值设定非常的奇妙，它是循环队列思路的关键。
解法二：链表
代码如下：
typedef struct { struct ListNode *head;//队首指针 struct ListNode *tail;//队尾指针 int capacity;//容量 int size;//长度 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue)); obj->capacity = k; obj->size = 0; obj->head = obj->tail = NULL; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (obj->size >= obj->capacity) { return false; } struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode)); node->val = value; node->next = NULL; if (!obj->head) { obj->head = obj->tail = node; } else { obj->tail->next = node; obj->tail = node; } obj->size++; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj->size == 0) { return false; } struct ListNode *node = obj->head; obj->head = obj->head->next; obj->size--; free(node); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if (obj->size == 0) { return -1; } return obj->head->val; } int myCircularQueueRear(MyCircularQueue* obj) { if (obj->size == 0) { return -1; } return obj->tail->val; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->size == 0; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->size == obj->capacity; } void myCircularQueueFree(MyCircularQueue* obj) { for (struct ListNode *curr = obj->head; curr;) { struct ListNode *node = curr; curr = curr->next; free(node); } free(obj); }
这种写法是使用双向循环链表的写法，个人觉得这种写法比上面的要更好理解
首先是队列结构体的建立和初始化队列
入队列：如果长度等于容量队列已满，返回false，这里插入分两种情况，第一种是第一次插入时，首位指针都指向该元素结点，之后每次插入为第二种情况，一直挪动尾指针即可，插入成功，size+1，返回true
出队列：如果size为0，返回false，头指针指向下一结点，size-1，返回true
返回队首值：直接返回队首指针指向元素即为队首。
返回队尾值：直接返回队尾指针指向元素即为队尾。
返回队列是否为空：返回队首size是否为0。
返回队列是否已满：size等于capacity就满了。
结语
这里的解法代码部分来自力扣官方和作者自己的解法，作者只是进行了详细的剖析和部分改动方便大家理解和提升自己，学会多角度观察问题，解决问题。
有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！
制作不易，如有不正之处敬请指出
感谢大家的来访，UU们的观看是我坚持下去的动力
在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
