【Leetcode】2道题彻底理解栈和队列

平凡的人1

发布于 2022-11-15 15:05:03

1720

发布于 2022-11-15 15:05:03

文章被收录于专栏：从小白开始修炼

前言🎬

好的，前面具体的学习了栈和队列的知识，然后本篇博客的主要内容是做3道OJ题，学完之后，一定要及时地去刷题，对其加深理解和巩固，不然很难有所进步，有利于我们更好的学习数据结构的栈和队列。然后，对栈和队列还不够熟悉的，可以看看我之前写的博客

✨栈：👉 点我 ✨队列：👉点我

ok，下面我们开始把

1.有效的括号

leetcode传送门⏩：20. 有效的括号

📄题目内容：

吐槽一下😝：哈哈，这道题第一次打开leetcode的时候就看到了，那时候就想把这道题解决掉，觉得会很简单，可奈何那时的知识储备实在太少，自然无功而返，今天，重新把这道题拿出来，这也算是一种回忆把。感觉很不一样。

🔑 思路分析：

首先一上来，我们就要告诉自己，这是一道非常简单的题。

不知道你是否会有这样的想法：只需要看左括号有多少个，右括号有多少个，比较一下就行了？恭喜你，搞错了，请看示例4。

这道题其实很容易想到我们前面学的栈来解决非常合适。怎么去解决？我概括成以下几点：

Step1：.左括号，入栈，算法结束 Step2：右括号，出栈顶的左括号与右括号是否匹配如果匹配，继续。不匹配，终结，算法结束

不过很可惜的是，在c语言版本中并没有可以提供栈的函数，我们需要自己手动创建一个栈，包括操作，我们可以拷贝之前博客的代码实现栈的操作。所以，实际上，对于后面一些数据结构用c去实现是非常麻烦的。别人一个类就能几行代码能够解决的事情，你需要很多行，多说了几句。好啦，下面直接上手代码

🔎代码运行：

主要部分

完整代码：

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;
}ST;
 
 
 
void StackInit(ST* ps);
void StackDestory(ST* ps);
 
//栈顶插入删除数据
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
 
int StackSize(ST* ps);
bool StackEmpty(ST* ps);


void StackInit(ST* ps)
{
	assert(ps);
	ps->a = malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
 
//栈顶插入删除数据
//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//满了--增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
 
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//栈空了，调用Pop，直接终止程序报错
	assert(ps->top);
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	//栈空了，调用Top，直接终止程序报错
	assert(ps->top > 0);
	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 != '\0')
   {
       switch(*s)
       {
           case '{':
           case '[':
           case '(':
           {
           StackPush(&st,*s);
           ++s;
           break;
           }
           case '}':
           case ']':
           case ')':
           {
            if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
            char top = StackTop(&st);
            StackPop(&st);

            //不匹配
            if((*s == '}' && top !='{')
            ||(*s == ']' && top !='[')
            ||(*s == ')' && top !='('))
            {
                StackDestory(&st);
                return false;
            }
            else{//匹配
                ++s;
            }
            break;
           }
           default:
           break;
       }
   }
   bool ret = StackEmpty(&st);
   StackDestory(&st);
   return ret;


}

注：不要觉得代码很长哦，前面一大部分只是为了构造堆及其操作👇