建立能够存放字符的顺序栈空栈,利用栈的特性对输入的字符串完成是否为回文的判断。
时间: 2024-11-20 11:43:08 浏览: 5
JS使用栈判断给定字符串是否是回文算法示例
5星 · 资源好评率100%
建立一个能存放字符的顺序栈(也称作线性栈),可以分为以下几个步骤:
1. 创建栈的数据结构:通常使用一个数组来实现,初始化时栈为空,可以设置一个变量`top`表示栈顶位置,初始值设为-1表示栈为空。
```python
class Stack:
def __init__(self):
self.stack = []
self.top = -1
```
2. 插入字符(入栈):当有新的字符要插入,检查栈顶是否已满,如果没有,就将字符添加到`stack[top+1]`位置,然后`top`加一。
```python
def push(self, char):
self.top += 1
self.stack.append(char)
```
3. 删除字符(出栈):对于回文判断,我们需要将字符逐个出栈与原串对应字符比较,所以需要一个辅助函数`pop()`,如果栈不为空,将`stack[top]`取出并移动`top`。
```python
def pop(self):
if not self.isEmpty():
self.top -= 1
return self.stack.pop()
else:
raise Exception("Stack is empty")
def isEmpty(self):
return self.top == -1
```
4. 判断回文:输入一个字符串`str`,我们先将字符串反转得到`reversed_str`,然后依次将`str`中的字符压入栈,接着对比栈顶元素与`reversed_str`的字符,若不相等则返回False,直到两者都遍历完。
```python
def isPalindrome(self, str):
reversed_stack = Stack() # 另外新建一个栈,用于存放字符
for char in str:
reversed_stack.push(char)
while not reversed_stack.isEmpty(): # 比较栈顶元素与原串字符
if self.pop() != reversed_stack.pop():
return False
return True
```
阅读全文