栈、队列——练习题

1. ✌有效的括号

代码实现：

方法一：括号匹配

在任意一个位置上，左括号数量 >= 右括号数量
在最后一个位置上，左括号数量 == 右括号数量

方法二：栈

bool isValid(char* s) {char stack[10000];int top = -1;while (*s) {if (*s == '(' || *s == '{' || *s == '[') {stack[++top] = *s;} else {if (top == -1) { // 栈空return false;}int top_val = stack[top]; // 获取栈顶元素if (top_val == '(' && *s != ')' || top_val == '[' && *s != ']' || top_val == '{' && *s != '}') {return false;} else {top--;}}s++;}if (top != -1) {return false;}return true;
}

2. 海贼OJ #595. 程序调用关系

代码实现：

#include <stdio.h>
#include <string.h>int main(int argc, char *argv[]) {int n;scanf("%d", &n);char S[n][110];for (int i = 0; i < n; i++) {scanf("%s", S[i]);}char s[110];scanf("%s", s);char stack[n][110]; // 模拟栈int top = -1;int flag = 1; // 标记位for (int i = 0; i < n; i++) {if (strcmp(S[i], "return") != 0) {strcpy(stack[++top], S[i]);} else if (top != -1) {top--;}if (top != -1 && strcmp(stack[top], s) == 0) {flag = 0;break;}}if (flag) {printf("NOT REFERENCED\n");} else {for (int i = 0; i <= top; i++) {printf("%s", stack[i]);int j = i + 1;if (j <= top) {printf("->");}}putchar('\n');}return 0;
}

3. 海贼OJ #838. 2020年数据结构41题

代码实现：

4. 比较含退格的字符串

代码实现：

5. 海贼OJ #263. 火车进栈

代码实现：

#include <stdio.h>
#include <stdbool.h>int a[20], vis[21] = {0};int stack[20];// 判断是否符合栈先进后出的要求
bool judge_one_result(int n) {int top = -1;int x = 1;for (int i = 0; i < n; i++) {if (top == -1 || stack[top] < a[i]) {while (x <= a[i]) {stack[++top] = x;x++;}}if (top == -1 || stack[top] != a[i]) {return false;}top--;}return true;
}int len = 0;
void f(int i, int n) { // i:当前枚举的是第i位的值   n:最大可以选取的数字   if (i == n) { // 边界if (judge_one_result(i)) {if (len >= 20) {exit(0); // 结束所有程序 exit(0):表示程序正常退出，exit(1)或exit(-1)表示程序异常退出} else {len++;for (int j = 0; j < n; j++) {printf("%d", a[j]);}putchar('\n');}}return ;}for (int k = 1; k <= n; k++) {if (vis[k]) { // 标记位思想continue;}a[i] = k;vis[k] = 1;f(i + 1, n);// 回溯vis[k] = 0;}
}int main(int argc, char *argv[]) {int n;scanf("%d", &n);f(0, n);return 0;
}

6. 验证栈序列

代码实现：

bool validateStackSequences(int *pushed, int pushedSize, int *popped, int poppedSize) {int *stack = (int*)malloc(sizeof(int) * pushedSize);int top = -1;for (int i = 0, j = 0; i < pushedSize; i++) {stack[++top] = pushed[i];while (top > -1 && stack[top] == popped[j]) {top--;j++;}}free(stack);return top == -1;
}

7. 海贼OJ #265. 括号画家

代码实现：

记录匹配的下标

#include <stdio.h>int main(int argc, char *argv[]) {char str1[10000];gets(str1);char *str = str1 - 1; // 让数组下标从1开始int match[10001] = {0};int stack[10000]; // 定义一个栈，存储数组下标int top = -1; // 栈顶指针for (int i = 1; str[i]; i++) {switch (str[i]) {case '(': case '[': case '{': stack[++top] = i; break;case ')': {if (top != -1 && str[stack[top]] == '(') {match[stack[top]] = i;match[i] = stack[top]; //delete 可以没有top--;} else {stack[++top] = i;}} break;case ']': {if (top != -1 && str[stack[top]] == '[')  {match[stack[top]] = i;match[i] = stack[top]; //delete 可以没有top--;} else {stack[++top] = i;}} break;case '}': {if (top != -1 && str[stack[top]] == '{') {match[stack[top]] = i;match[i] = stack[top]; // delete 可以没有 top--;} else { stack[++top] = i;}} break;}}int temp_ans = 0, ans = 0, i = 1;while (str[i]) {if (match[i]) {temp_ans += (match[i] - i + 1);i = match[i] + 1;} else {i += 1;temp_ans = 0;}if (temp_ans > ans) {ans = temp_ans;}}printf("%d\n", ans);return 0;
}