用C++中栈和队列的基本操作设计用两种以上的算法来实现判断输入的字符串序列是否为回文

算法一：栈实现

1. 先将字符串中的每个字符逐个入栈。
2. 再从栈中依次出栈，将每个出栈元素按照出栈顺序组成新的字符串。
3. 判断新的字符串与原字符串是否相等，相等则是回文，否则不是。

实现代码如下：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isPalindrome(string str) {
    stack<char> s;
    for (int i = 0; i < str.length(); i++) {
        s.push(str[i]);
    }
    string newStr;
    while (!s.empty()) {
        newStr += s.top();
        s.pop();
    }
    return newStr == str;
}

int main() {
    string str;
    cout << "请输入一个字符串：";
    cin >> str;
    if (isPalindrome(str)) {
        cout << str << " 是回文字符串" << endl;
    } else {
        cout << str << " 不是回文字符串" << endl;
    }
    return 0;
}

算法二：队列实现

1. 先将字符串中的每个字符逐个入队。
2. 依次从队首和队尾分别取出元素，判断它们是否相等，若相等则继续，若不相等则不是回文。
3. 直到队列为空或只剩下一个元素，结束判断。

实现代码如下：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

bool isPalindrome(string str) {
    queue<char> q;
    for (int i = 0; i < str.length(); i++) {
        q.push(str[i]);
    }
    while (q.size() > 1) {
        char front = q.front();
        char back = q.back();
        if (front != back) {
            return false;
        }
        q.pop();
        q.pop();
    }
    return true;
}

int main() {
    string str;
    cout << "请输入一个字符串：";
    cin >> str;
    if (isPalindrome(str)) {
        cout << str << " 是回文字符串" << endl;
    } else {
        cout << str << " 不是回文字符串" << endl;
    }
    return 0;
}

两种算法都是基于数据结构的操作，时间复杂度都为 O(n)。其中栈的空间复杂度为 O(n)，队列的空间复杂度为 O(n/2)。