用栈和队列的基本操作设计用两种以上的算法来实现判断输入的字符串序列是否为回文
时间: 2024-01-22 08:17:36 浏览: 33
算法1:利用栈实现回文判断
1. 创建一个空栈S
2. 将字符串s的每个字符依次压入栈S中
3. 弹出栈S中的每个字符,将它们组成一个新的字符串s1
4. 判断s是否等于s1,如果相等则为回文,否则不是回文
Python代码实现:
```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代码实现:
```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++栈和队列的基本操作设计用两种以上的算法来实现判断输入的字符串序列是否为回文
算法一:利用栈的特性,将输入的字符串序列按顺序入栈,再按顺序出栈并与原字符串序列比较,若相同则为回文。
C++代码实现:
```cpp
#include <iostream>
#include <stack>
using namespace std;
bool isPalindrome(string str) {
stack<char> s;
int len = str.length();
for (int i = 0; i < len; i++) {
s.push(str[i]);
}
for (int i = 0; i < len; i++) {
if (s.top() != str[i]) {
return false;
}
s.pop();
}
return true;
}
int main() {
string str;
cout << "请输入字符串:";
cin >> str;
if (isPalindrome(str)) {
cout << "是回文字符串" << endl;
} else {
cout << "不是回文字符串" << endl;
}
return 0;
}
```
算法二:利用队列的特性,将输入的字符串序列按顺序入队列,再按顺序出队列并与原字符串序列比较,若相同则为回文。
C++代码实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
bool isPalindrome(string str) {
queue<char> q;
int len = str.length();
for (int i = 0; i < len; i++) {
q.push(str[i]);
}
for (int i = 0; i < len; i++) {
if (q.front() != str[i]) {
return false;
}
q.pop();
}
return true;
}
int main() {
string str;
cout << "请输入字符串:";
cin >> str;
if (isPalindrome(str)) {
cout << "是回文字符串" << endl;
} else {
cout << "不是回文字符串" << endl;
}
return 0;
}
```
用C++中栈和队列的基本操作设计用两种以上的算法来实现判断输入的字符串序列是否为回文
算法一:使用栈
1. 将字符串依次压入栈中,即从字符串的第一个字符开始,依次将字符压入栈中,直到字符串结束。
2. 从字符串的第一个字符开始,依次将字符与栈顶元素进行比较,如果相等,则弹出栈顶元素,继续比较下一个字符;如果不相等,说明该字符串不是回文,直接返回false。
3. 如果比较完了所有字符,且栈已经为空,说明该字符串是回文,返回true;否则,说明该字符串不是回文,返回false。
代码如下:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isPalindrome(string str) {
stack<char> s;
int len = str.length();
for (int i = 0; i < len; i++) {
s.push(str[i]);
}
for (int i = 0; i < len; i++) {
if (s.top() == str[i]) {
s.pop();
} else {
return false;
}
}
return true;
}
int main() {
string str;
cin >> str;
if (isPalindrome(str)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
```
算法二:使用队列
1. 将字符串依次加入队列中,即从字符串的第一个字符开始,依次将字符加入队列中,直到字符串结束。
2. 从字符串的第一个字符开始,依次将字符与队列的队首元素进行比较,如果相等,则弹出队首元素,继续比较下一个字符;如果不相等,说明该字符串不是回文,直接返回false。
3. 如果比较完了所有字符,且队列已经为空,说明该字符串是回文,返回true;否则,说明该字符串不是回文,返回false。
代码如下:
```c++
#include <iostream>
#include <queue>
#include <string>
using namespace std;
bool isPalindrome(string str) {
queue<char> q;
int len = str.length();
for (int i = 0; i < len; i++) {
q.push(str[i]);
}
for (int i = 0; i < len; i++) {
if (q.front() == str[i]) {
q.pop();
} else {
return false;
}
}
return true;
}
int main() {
string str;
cin >> str;
if (isPalindrome(str)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
```
以上两种算法都可以实现判断输入的字符串序列是否为回文,使用栈或队列都可以。但是,使用栈的空间复杂度更小,因为只需要一个栈就可以了,而使用队列则需要一个队列。