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)