力扣栈的简单题，你真会做吗？
A
前言
很多高级算法，其实都需要借助栈这种基础的数据结构来实现，本文通过力扣的一道简单题来介绍栈的基础使用。
栈
堆栈（stack）又称为栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（栈顶 top）进行插入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。如下图示：
刚开始，栈顶和栈底元素分别是 1 和 2，将数字 8 压入栈中，此时栈顶元素变成 8，继续将数字 2 压入栈中，栈顶元素变为 2，再将栈顶元素 2 弹出栈，此时栈顶元素又变成 8，继续将栈顶元素 8 以及将元素 8 弹出栈后栈顶元素 1 弹出栈，栈顶元素变成了7。
题目
leetcode 20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
解题思路
题目要求判断字符串是否有效，即左括号 ( '('、'{' 和 '[' ) 必须用相同类型的右括号 ( ')'、'}' 和 ']' ) 闭合，并且要以正确的顺序。这是一道典型的可以通过栈来解决的题目，遍历字符串遇到左括号时，入栈，遇到能与左括号正确顺序的右括号时，出栈，最后再判断栈是否为空，如果最后栈为空，则代表其为有效字符串，否则不是有效字符串。
Show me the Code
// c 语言 数组模拟栈
bool isValid(char * s){
/* 栈顶 */
int top = 0;
/* 动态分配一个数组，用于模拟栈 */
char *stack = (char *) malloc(sizeof(char) * (strlen(s) + 1));
/* 校验是否分配成功 */
if (stack == NULL) {
return false;
}
/* 遍历整个字符串 */
for(int i = 0; s[i] != '\0'; i++) {
/* 遇到左括号，则入栈 */
if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
stack[++top] = s[i];
/* 遇到与左括号刚好顺序匹配的右括号，则出栈 */
} else if( (s[i] == ')' && stack[top] == '(') || (s[i] == ']' && stack[top] == '[') ||
(s[i] =='}' && stack[top] =='{') ) {
top--;
} else {
if(stack != NULL) {
free(stack);
stack = NULL;
}
return false;
}
}
/* 释放申请的空间 */
if(stack != NULL) {
free(stack);
stack = NULL;
}
/* 最后栈为空，代表刚好全部匹配 */
return top == 0 ? true : false;
}// c++ 直接用栈
bool isValid(string s) {
stack<char> stack;
for (int i = 0; i < s.size(); ++i) {
/* 左括号( '('、'{' 和 '[' ) 入栈*/
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
stack.push(s[i]);
} else {
/* 栈为空，不是有效的括号 */
if (stack.size() == 0) {
return false;
}
/* 记录栈顶元素 */
char top = stack.top();
/* 弹出栈顶元素 */
stack.pop();
/* 记录用于匹配右括号 */
char match;
if (s[i] == ')') {
match = '(';
} else if (s[i] == '}') {
match = '{';
} else if (s[i] == ']') {
match = '[';
}
/* 栈顶存储的括号跟需要匹配的括号不同，不是有效的括号 */
if (top != match) {
return false;
}
}
}
/* 栈中的元素全部弹出，代表全部匹配，否则不匹配 */
return stack.size() == 0;
}通过switch case 解决
上面的代码中有很多的 if else，可以通过 switch case 去改写上面的代码。还是遍历整个字符串，当遇到左括号（'('、'{' 和 '['）时，则将能与左括号匹配的右括号进栈，然后判断栈顶元素是否与字符串的下一个元素相同，若相同则将栈顶出栈，最后判断栈是否为空，如果为空，则代表该字符串是有效字符串。
Show me the Code
// c++
bool isValid(string s) {
stack<char> stack;
for (char c : s) {
switch (c) {
case '(':
stack.push(')');
break;
case '[':
stack.push(']');
break;
case '{':
stack.push('}');
break;
default:
if (stack.empty() || stack.top() != c) {
return false;
}
stack.pop();
}
}
return stack.empty();
}// java
boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
switch (c) {
case '(':
stack.push(')');
break;
case '[':
stack.push(']');
break;
case '{':
stack.push('}');
break;
default:
if (stack.empty() || stack.pop() != c) {
return false;
}
}
}
return stack.empty();
}往期精彩回顾
四种方法解决leetcode203. 移除链表元素 Dine，公众号：TanLiuYi00四种方法解决leetcode203. 移除链表元素
更多精彩
腾讯云开发者
