python数据结构与算法——栈,,# 栈# 其实pyt
python数据结构与算法——栈,,# 栈# 其实pyt
# 栈
# 其实python里面的list就可以当栈使用啦,用collections.deque也可以
# 1. 入栈 list.append(item)
# 2. 出栈 item = list.pop()
# 3. 对于首元素出栈,还可以 item = list.pop(0) 和队列概念一样
# 4. 其实还可以任意元素出栈 item = list.pop(i) 相当于删除第i个元素
# 注意3,4是很耗时间的
栈可以方便用来判断一个字符串是否回文,但是要在一个长字符串中找到最大的回文一般用的数据结构是后缀树。
下面是基于栈的回文判断算法
1 # 判断一个字符串是否回文(plalindrome 不是 Moslems =_=||) 2 # 如果一个字符串是回文的话,它必须是中间对称的 3 # 将前半部分入栈,再依次出栈,看看能否与mid之后的字符一一匹配 4 5 def is_Plalindrome_demo1(A): 6 mid = len(A)/2 # 5/2=2, 4/2=2 7 stack = [] 8 for i in range(mid): 9 stack.append(A[i])10 11 if len(A)%2 == 0: # 判断字符串的长度是奇数还是偶数12 next = mid # 确定后半截字符串的起始下标13 else:14 next = mid + 115 16 top = mid-117 for i in range(next,len(A)):18 if stack[top] != A[i]:19 return False20 top -= 121 22 return True
测试:
if __name__=="__main__": q = list("hahahahahahahahaha") print is_Plalindrome_demo1(q)
手动实现栈
1 # 简单的FILO栈类别 2 class Stack: 3 def __init__(self): 4 self.top = None # 指向栈顶 5 self.end = None # 指向栈底 6 self.count = 0 7 8 def push(self,data): 9 if self.end == None:10 self.end = Node(data)11 self.top = self.end12 else:13 temp = self.top # 保存当前栈顶14 self.top = Node(data)15 self.top.next = temp16 self.count += 117 18 def pop(self):19 if self.top == None:20 raise "Error: top==None"21 data = self.top.data22 self.top = self.top.next23 self.count -= 124 return data
python数据结构与算法——栈
相关内容
- 暂无相关文章
评论关闭