leetcode 有效括号和循环队列
1. 有效的括号
本题目来源于leetcode有效的括号
1.1 题目描述
提示
1.1.1 接口函数
bool isValid(char * s){
}
1.2 大致框架
虽然数组也可以解决问题但是不太好，后面有些题目就会出现问题 我们尝试用栈来解决问题
直接用c肯定是栈要自己写的，因为没有库，所以如果我们这里要用c语言实现这道题，需要自己写一个栈
1.2.1 想法思路
题目的说输入的情况只有左括号或者右括号,所以我们不用管其他的输入可能性
利用栈的先进后出特性，所以我们可以把是左括号类型（有（{【）的都放入栈中，然后右括号则开始匹配，如果匹配失败，则直接false，如果成功则通过StackPop把栈最上面一个拿掉，然后判断下一个是否匹配，直到最后一个返回true或者中途不匹配返回false
1.2.2 具体步骤
先得c语言自己实现一下栈
声明
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType ;
struct Stack
{
STDataType* a;
int capacity; //容量，方便增容
int top; //栈顶
};
typedef struct Stack Stack;
void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//性质决定了在栈顶数据出入
STDataType StackTop(Stack* pst);
void StackPop(Stack* pst);
bool StackEmpty(Stack* pst);
int StzckSize(Stack* pst);
函数
void StackInit(Stack* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//容量翻倍
STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
pst->a = tmp;
pst->capacity =newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];//从高下标往低下标
}
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;//布尔来判断
}
int StzckSize(Stack* pst)
{
assert(pst);
return pst->top;//恰好是size
}
然后构建isValid(char * s)
注意事项：
-
循环里面要由一个分支判断是左括号还是右括号，左括号进栈，右括号判断
-
不能忘记走完一个分支后s指针要往前继续走
-
最后如果是空则说明匹配，不空说明不匹配，因为加入最后剩下一个就不判断了会直接返回true，其实应该要false，所以最后应该还是要有一个判断，可以用
StackEmpty判断
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
//左括号入栈
//右括号找最近的做括号匹配
if(*s =='['
||*s=='{'
||*s=='(')
{
StackPush(&st,*s);
++s;
}
else
{
if(StackEmpty(&st))//说明没有前括号
{
StackDestroy(&st);
return false;
}
char top=StackTop(&st);
if((top=='['&&*s!=']')
||(top=='('&&*s!=')')
||(top=='{'&&*s!='}'))
{
StackDestroy(&st);
return false;
}
else
{
//匹配的
StackPop(&st);
++s;
}
}
}
bool ret=StackEmpty(&st);
StackDestroy(&st);
return ret;
}
1.3 整体实现
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType;
struct Stack
{
STDataType* a;
int capacity; //容量，方便增容
int top; //栈顶
};
typedef struct Stack Stack;
void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//性质决定了在栈顶数据出入
STDataType StackTop(Stack* pst);
void StackPop(Stack* pst);
bool StackEmpty(Stack* pst);
void StackInit(Stack* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//容量翻倍
STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
pst->a = tmp;
pst->capacity =newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];//从高下标往低下标
}
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;//布尔来判断
}
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
//左括号入栈
//右括号找最近的做括号匹配
if(*s =='['
||*s=='{'
||*s=='(')
{
StackPush(&st,*s);
++s;
}
else
{
if(StackEmpty(&st))//说明没有前括号
{
StackDestroy(&st);
return false;
}
char top=StackTop(&st);
if((top=='['&&*s!=']')
||(top=='('&&*s!=')')
||(top=='{'&&*s!='}'))
{
StackDestroy(&st);
return false;
}
else
{
//匹配的
StackPop(&st);
++s;
}
}
}
bool ret=StackEmpty(&st);
StackDestroy(&st);
return ret;
}
小结：
这道题目用c++的话会简单很多，因为可以直接调接口，但是c语言就得自己实现一个栈，会比较麻烦
2. 设计循环队列
本题目来源于leetcode 622. 设计循环队列
这道题目涉及到的可能会深一点，难度会高一点
2.1 题目描述
提示
2.1.1 接口函数
typedef struct {
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
}
int myCircularQueueFront(MyCircularQueue* obj) {
}
int myCircularQueueRear(MyCircularQueue* obj) {
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
}
void myCircularQueueFree(MyCircularQueue* obj) {
}
/**
* 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);
*/
2.2 大致框架
2.2.1 想法思路
用数组或链表实现
要实现循环队列肯定是得用到循环链表了，不能光单链表不是吗,当然数组也可以，链表的话更像是一个环
按照题目的意思我们要实现的功能是能使用之前用过的空间，要求队列满了不能再插入，但是没满或者满了再删了之后，我们可以用之前的位置存放数据
解决空和满
要想完成这样一个题目的要求是不是我们要有两个指针
但是这个想法的话是无法判断这个循环队列里面是空还是满的
所以要区分两种情况，什么时候判定算满，什么时候判定算空
这里采取空出一个位置不存数据来解决，比如说这个队列4个数据就满，则我只存3个那么这时可以判断了
- 以下的图例上方的是链表，下方演示的是数组
- 满就``tail->next
为front` - 空就
tail==front
那么此时我们也能实现pop和push操作
小结：
我们一般什么时候会用到这个循环队列呢？
比如说操作系统中的生产者和消费者问题
2.2.2 具体步骤
我们用数组实现一下,因为数组比链表可能实现的简单一点
注意以下步骤实现的函数仍有问题，后面会在找报错问题时解决，整体实现里是正确的代码
myCircularQueueCreate
typedef struct {
int * a;
int k;//队列最多能存多少个数据
int front; //头
int tail; //尾（队尾数据的下一个）
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));//留一个
obj->front=0;
obj->tail=0;
obj->k=k;
return obj;
}
myCircularQueueIsEmpty
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
myCircularQueueIsFull
bool myCircularQueueIsFull(MyCircularQueue* obj) {
int tailNext = obj->tail + 1;
if (tailNext == obj->k + 1)//防止next走出去
{
tailNext = 0;
}
return tailNext == obj->front;
}
myCircularQueueEnQueue
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
++obj->tail;
if (obj->tail == obj->k + 1)
{
obj->tail = 0;
}
return true;
}
}
myCircularQueueDeQueue
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
++obj->front;
if (obj->front == obj->k + 1)
{
obj->front = 0;
}
return true;
}
}
myCircularQueueFront
int myCircularQueueFront(MyCircularQueue* obj) {
return obj->a[obj->front];
}
myCircularQueueRear
int myCircularQueueRear(MyCircularQueue* obj) {
int tailPrev = obj->tail - 1;
if (tailPrev == -1)//防止prev走出去
{
tailPrev = obj->k;
}
return obj->a[tailPrev];
}
myCircularQueueFree
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
2.2.3 寻找报错问题
说明问题出在Front上，按照值钱的输入的话，在执行这个Front之前这个循环队列里面是没有数据的，所以返回的Front应该是空的，所以说明这个点没有考虑到，如果为空返回-1即可
myCircularQueueFront
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front] ;
}
}
那么myCircularQueueRear应该也是一样，虽然没有提示但是可以想到
int myCircularQueueRear(MyCircularQueue* obj) {
int tailPrev = obj->tail - 1;
if (tailPrev == -1)//防止prev走出去
{
tailPrev = obj->k;
}
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[tailPrev];
}
}
2.3 整体实现
#include<stdbool.h>
typedef struct {
int* a;
int k;//队列最多能存多少个数据
int front; //头
int tail; //尾（队尾数据的下一个）
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k + 1));//留一个
obj->front = 0;
obj->tail = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
int tailNext = obj->tail + 1;
if (tailNext == obj->k + 1)//防止next走出去
{
tailNext = 0;
}
return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
++obj->tail;
if (obj->tail == obj->k + 1)
{
obj->tail = 0;
}
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
++obj->front;
if (obj->front == obj->k + 1)
{
obj->front = 0;
}
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
int tailPrev = obj->tail - 1;
if (tailPrev == -1)//防止prev走出去
{
tailPrev = obj->k;
}
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[tailPrev];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
小结：
栈和队列的难点主要在于结构复杂，不在于单个逻辑，写多了就会感觉好多了
后面更难的栈和队列的题目之后会使用c++的stl库再实现
如果老铁们有收获的话，希望给个一键三连哦，谢谢