当前位置：首页 > news >正文

【Leedcode】栈和队列必备的面试题（第一期）

news 2025/7/19 0:43:02

栈和队列必备的面试题（第一期）

文章目录

栈和队列必备的面试题（第一期）
一、题目
二、思路（图解）
三、存在的问题与隐患（报错提示）
- （1）s中只有右括号，无左括号
- （2）返回值处理
- （3）销毁栈
四、整体源代码
总结

一、题目

在这里插入图片描述

Leedcode链接：https://leetcode.cn/problems/valid-parentheses/

在这里插入图片描述

二、思路（图解）

我们用栈来实现这道题，具体如下图！

在这里插入图片描述

这里我们用到栈接口实现中的 Stackpush 接口！然后 s++

在这里插入图片描述

这里我们会用到栈接口实现中的 Stacktop 和 Stackpop 接口！下面是 比较方法！

正确的就 s++，知道*s为NULL为止！
在这里插入图片描述

如果不匹配，直接返回 false！
在这里插入图片描述

出栈 + 入栈 + 取栈顶数据 + 比较方法 : 代码如下（示例）：

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 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 = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}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];
}
int 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{STDataType top = StackTop(&st);StackPop(&st);if(*s == ')' && top != '('|| *s == ']' && top != '['|| *s == '}' && top != '{'){StackDestroy(&st);return false;}else{s++;}}}
}

三、存在的问题与隐患（报错提示）

如果现在提交代码，会出现以下的报错 + 问题！

（1）s中只有右括号，无左括号

在这里插入图片描述

这里我们应该注意：如果没有左括号直接返回 false 即可！
在这里插入图片描述

代码如下（示例）：

while(*s){if(*s == '('|| *s == '['|| *s == '{'){StackPush(&st , *s);s++;}else{//如果没有左括号，栈为空，返回falseif(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++;}}}

（2）返回值处理

在这里插入图片描述

如果栈不是空，则说明栈中还有左括号未出。即没有匹配，返回是 false

代码如下（示例）：

bool ret = StackEmpty(&st);StackDestroy(&st);return ret;

（3）销毁栈

最后不要忘了用栈的 StackDestroy 对栈进行销毁否则会导致内存泄漏等问题！

StackDestroy(&st);

四、整体源代码

代码如下（示例）：

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 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 = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}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];
}
int 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{//如果没有左括号，栈为空，返回falseif(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;}