用C++栈和队列的基本操作设计用两种以上的算法来实现判断输入的字符串序列是否为回文
时间: 2024-01-22 10:18:11 浏览: 13
算法一:使用栈
步骤:
1. 从前往后扫描字符串,将每个字符压入栈中。
2. 从前往后扫描字符串,将每个字符与栈顶元素进行比较,如果不相同则说明不是回文,返回false。
3. 如果一直比较到字符串末尾,栈为空,则说明是回文,返回true。
C++代码实现:
```cpp
#include <iostream>
#include <stack>
using namespace std;
bool isPalindrome(string str) {
stack<char> s;
int n = str.size();
for (int i = 0; i < n ; i++) {
s.push(str[i]);
}
for (int i = 0; i < n ; i++) {
if (str[i] != s.top()) {
return false;
}
s.pop();
}
return true;
}
int main() {
string str;
cout << "Enter a string: ";
cin >> str;
if (isPalindrome(str)) {
cout << str << " is a palindrome." << endl;
} else {
cout << str << " is not a palindrome." << endl;
}
return 0;
}
```
算法二:使用队列
步骤:
1. 从前往后扫描字符串,将每个字符加入队列中。
2. 从前往后扫描字符串,将每个字符与队首元素进行比较,如果不相同则说明不是回文,返回false。
3. 如果一直比较到字符串末尾,队列为空,则说明是回文,返回true。
C++代码实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
bool isPalindrome(string str) {
queue<char> q;
int n = str.size();
for (int i = 0; i < n ; i++) {
q.push(str[i]);
}
for (int i = 0; i < n ; i++) {
if (str[i] != q.front()) {
return false;
}
q.pop();
}
return true;
}
int main() {
string str;
cout << "Enter a string: ";
cin >> str;
if (isPalindrome(str)) {
cout << str << " is a palindrome." << endl;
} else {
cout << str << " is not a palindrome." << endl;
}
return 0;
}
```
注:以上两种算法都是空间复杂度为O(n),时间复杂度为O(n)的算法。
阅读全文