数据结构——栈
1
概念
大家先想象一下这个场景：当我们去打羽毛球时，通常会带一桶羽毛球，不管我们是要拿出还是放入一个羽毛球，都要从最上面拿，如果想拿到下方的羽毛球，必须先把上面的拿出来。这种只能在一端进行拿去和放入的方式，就是栈。
栈是只能在一端进行插入和删除操作的线性表，可以进行操作的这端叫做栈顶，另一端叫做栈底，向栈顶插入元素叫入栈，从栈顶删除元素叫出栈。
2
python实例展示
题目：比较含退格的字符串
给定两个字符串，其中“#”代表退格，判断两个字符串是否相等。
思路：用栈重构字符串
遍历两个字符串，当是普通字符时，压入栈底，当是退格符时，弹出顶端字符。
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
s_result = []
t_result = []
for i in range(0,len(S)):
if S[i]!= '#' :
s_result.append(S[i])
elif len(s_result)>0 :
s_result.pop()
for i in range(0,len(T)):
if T[i]!= '#':
t_result.append(T[i])
elif len(t_result)>0:
t_result.pop()
return(s_result == t_result)本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读