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

算法1：利用栈实现回文判断

1. 创建一个空栈S

2. 将字符串s的每个字符依次压入栈S中

3. 弹出栈S中的每个字符，将它们组成一个新的字符串s1

4. 判断s是否等于s1，如果相等则为回文，否则不是回文

Python代码实现：

def is_palindrome(s: str) -> bool:
    stack = []
    for c in s:
        stack.append(c)
    s1 = ""
    while len(stack) > 0:
        s1 += stack.pop()
    return s == s1

算法2：利用队列实现回文判断

1. 创建一个空队列Q

2. 将字符串s的每个字符依次加入队列Q中

3. 弹出队列Q中的每个字符，将它们组成一个新的字符串s1

4. 判断s是否等于s1，如果相等则为回文，否则不是回文

Python代码实现：

from collections import deque

def is_palindrome(s: str) -> bool:
    queue = deque()
    for c in s:
        queue.append(c)
    s1 = ""
    while len(queue) > 0:
        s1 += queue.popleft()
    return s == s1

以上两种算法的时间复杂度都为O(n)，其中n为字符串s的长度。

相关问题

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

算法一：使用栈

1. 遍历输入的字符串，将每个字符依次压入栈中；
2. 再次遍历输入的字符串，每次将栈顶元素弹出并与当前字符比较，如果相同则继续比较，否则返回false；
3. 如果遍历完整个字符串后栈为空，则说明输入的字符串是回文，返回true，否则返回false。

时间复杂度为O(n)，空间复杂度为O(n)。

以下是C++代码实现：

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

bool isPalindrome(string s) {
    stack<char> st;
    int len = s.size();
    for (int i = 0; i < len; i++) {
        st.push(s[i]);
    }
    for (int i = 0; i < len; i++) {
        if (st.top() != s[i]) {
            return false;
        }
        st.pop();
    }
    return true;
}

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

算法二：使用队列

1. 遍历输入的字符串，将每个字符依次加入队列中；
2. 再次遍历输入的字符串，每次从队列头部取出一个字符并与当前字符比较，如果相同则继续比较，否则返回false；
3. 如果遍历完整个字符串后队列为空，则说明输入的字符串是回文，返回true，否则返回false。

时间复杂度为O(n)，空间复杂度为O(n)。

以下是C++代码实现：

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

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

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

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

算法一：使用栈

1. 将字符串中的每个字符依次入栈
2. 依次弹出栈顶字符并与原字符串中的字符比较，如果不相等则不是回文
3. 如果所有字符都比较完了，则是回文

C++代码实现：

#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]);
    }
    for (int i = 0; i < str.length(); i++) {
        if (s.top() != str[i]) {
            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. 依次出队队头字符并与原字符串中的字符比较，如果不相等则不是回文
3. 如果所有字符都比较完了，则是回文

C++代码实现：

#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]);
    }
    for (int i = 0; i < str.length(); i++) {
        if (q.front() != str[i]) {
            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;
}

注意：以上两种算法都是基于字符串中的每个字符相等才判断为回文，如果需要忽略大小写或忽略空格等要求，则需要先处理字符串再进行判断。