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

---

---

一、题目

---

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;}

---

总结

以上就是今天要讲的内容，本文介绍了【Leedcode】中栈和队列必备的面试题（第一期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！