建立能够存放字符的顺序栈,编写栈的五个基本函数;利用栈的特性对输入的字符串完成是否为回文的判断;
时间: 2024-11-06 11:15:19 浏览: 8
建立一个能存放字符的顺序栈(也称为简单堆栈),通常我们可以选择数组或链表作为底层数据结构。以下是栈的基本操作:
1. **初始化** (push_empty): 创建一个空栈,即栈顶指针top初始值为-1。
2. **入栈** (push): 当有新元素需要加入时,将它放在栈顶,并更新top指针加一。
3. **出栈** (pop): 如果栈非空,取出栈顶元素并返回,然后top减一。
4. **查看栈顶元素** (peek): 返回当前栈顶元素,但不改变栈的状态。
5. **判断栈是否为空** (is_empty): 检查top是否等于-1,如果等于,则栈为空。
对于判断输入字符串是否为回文,我们先将其推入栈中,然后依次从栈顶出栈并与原字符串对应位置的字符比较。如果所有字符都匹配,那么原始字符串就是回文。下面是一个简单的Python实现:
```python
def is_palindrome(s):
stack = []
for char in s:
stack.append(char)
# 双向遍历,同时出栈与原字符串对比
while len(stack) > 0 and len(s) > 0:
if stack.pop() != s[0]:
return False
s = s[1:]
# 如果只剩下一个元素或者两个完全相同的元素,它是回文
return not len(stack) + len(s)
# 示例:
input_str = "madam"
print(is_palindrome(input_str)) # 输出: True
```
阅读全文