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

7-1回文判断（栈和队列PTA）

news 2025/6/30 2:00:18

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。

若用C++，可借助STL的容器实现。

输入格式:

输入待判断的字符序列，按回车键结束，字符序列长度<20。

输出格式:

若字符序列是回文，输出“YES”；否则，输出“NO”。

输入样例:

abdba

输出样例:

YES

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

解题代码

两种实现方式：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAXSIZE 20typedef struct Stack {char data[MAXSIZE];int top;
} Stack;void InitStack(Stack *s) {s->top = -1;
}void Push(Stack *s, char x) {if (s->top == MAXSIZE - 1) {printf("Stack is full\n");exit(1);}s->data[++s->top] = x;
}char Pop(Stack *s) {if (s->top == -1) {printf("Stack is empty\n");exit(1);}return s->data[s->top--];
}int main() {char input[MAXSIZE];fgets(input, MAXSIZE, stdin);input[strcspn(input, "\n")] = '\0'; // 去掉换行符Stack s;InitStack(&s);int len = strlen(input);// 将前半部分字符压入栈中for (int i = 0; i < len / 2; ++i) {Push(&s, input[i]);}// 如果字符序列长度为奇数，跳过中间的字符int start = (len % 2 == 0) ? len / 2 : len / 2 + 1;// 检查后半部分字符是否与栈中的字符匹配for (int i = start; i < len; ++i) {if (Pop(&s) != input[i]) {printf("NO\n");return 0;}}printf("YES\n");return 0;
}

C++

#include <iostream>
#include <stack>
#include <string>using namespace std;int main() {string input;getline(cin, input); // 读取输入的字符序列stack<char> s;int len = input.length();// 将前半部分字符压入栈中for (int i = 0; i < len / 2; ++i) {s.push(input[i]);}//如果字符序列长度为偶数 (len % 2 == 0)，则从 len / 2 开始比较。//如果字符序列长度为奇数 (len % 2 != 0)，则从 len / 2 + 1 开始比较，跳过中间的字符int start = (len % 2 == 0) ? len / 2 : len / 2 + 1;// 检查后半部分字符是否与栈中的字符匹配for (int i = start; i < len; ++i) {if (s.top() != input[i]) {cout << "NO" << endl;return 0;}s.pop();}cout << "YES" << endl;return 0;
}

可以看出C++的实现方式要大大简便

具体简便之处

内存管理：
- C++：stack<char> s; 自动管理内存。
- C：需要手动初始化栈，并管理内存分配和释放。
数据结构实现：
- C++：直接使用 stack 容器。
- C：需要定义 Stack 结构体，并实现 Push 和 Pop 函数。
接口和操作：
- C++：s.push(input[i]); 和 s.top() 等操作非常简洁。
- C：需要自己实现 Push 和 Pop 函数，并处理栈满和栈空的情况。
异常处理：
- C++：STL 容器在操作失败时会抛出异常。
- C：需要手动检查每个操作的返回值，并处理错误。
泛型编程：
- C++：STL 容器是模板类，可以存储任意类型的数据。
- C：需要使用 void* 指针和类型转换来实现类似的功能。