什么是栈？
栈是大家很熟悉的一种数据结构了，人们之所以使用栈，就是为了使用其后进先出的特性。入栈和出栈是栈的两个灵魂操作。
如图所示，以Python中的list模拟栈结构，原始list是[1,2]，通过两次push()操作，我们先后将3,4这两个元素加入到list中，这个操作被称作压栈，之后我们再对list施加两次pop()操作来模拟出栈，值得注意的是，元素4虽然是最后被压栈的元素，但却是第一个出栈的元素，这就是我们所说栈结构的后进先出的特性。
栈的操作.png
leetcode #1544之整理字符串
原题如下：
给你一个由大小写英文字母组成的字符串
s。
一个整理好的字符串中，两个相邻字符s[i]和s[i+1]，其中0<= i <= s.length-2，要满足如下条件:
若s[i]是小写字符，则s[i+1]不可以是相同的大写字符。
若s[i]是大写字符，则s[i+1]不可以是相同的小写字符。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的两个相邻字符并删除，直到字符串整理好为止。
效果如下：
输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。
思路
我们可以维护一个listr来作为处理后的字符串的缓存，并且从头至尾遍历原始字符串s，考虑如下两种情况：
- 如果当前遍历到的字符
c和r中的最后一个元素互为大小写，那么按照题意，我们将同时舍弃这个元素c，以及r中的最后一个元素。删除r中的最后一个元素，就对应着上述的出栈动作，可以用pop()方法来实现。 - 如果当前遍历到的字符
c和r中的最后一个元素没有大小写关系，或者r尚为空，那么直接把当前字符c插入到r中，作为r的最后一个元素就可以了，对应着上述压栈的操作。
经过上述的循环操作，就可以得到一个按题意处理过的字符串了。
其他小的知识点
在编写最终程序前，考虑本例中用到的几个小的实现方式。
- Python如何新建一个list？
可以用r = []和r = list()两种方式表示 - 如何判断两个字符互为大小写？
两个字符互为大小写，意味着如果我们把两个字符都转成小写（或大写）来比较的话，二者是相等的；并且把这两个原始字符直接进行比较的话，二者是不相等的：c1.lower() == c2.lower() and c1 != c2 - Python如何访问list的最后一个元素？
用-1作为索引，可以访问list中的最后一个元素：r[-1] - Python如何向list末尾插入一个元素，以及从末尾删除一个元素？
用append(c)向list尾部插入一个元素，用pop()从list尾部删除一个元素。 - Python如何将字符数组组合成字符串？
使用join()函数，形式为str.join()。这里的str意指连接分隔符。例如'-'.join(['a','b','c'])的结果是a-b-c，''.join(['a','b','c'])的结果是abc。
Python实现的源码
class Solution:
def makeGood(self, s: str) -> str:
# 新建一个list作为返回值的栈
r = list()
# 遍历原始字符串
for ch in s:
# 如果当前字符ch和r中的最后一个字符互为大小写，那么需要删除r中的最后一个元素
if r and r[-1].lower() == ch.lower() and r[-1] != ch:
r.pop()
# 否则将当前字符ch入栈
else:
r.append(ch)
# 将r中的元素组合成字符串返回
return ''.join(r)
时间复杂度
很明显，时间复杂度与原始字符串s的长度相关，对于s中每个字符的操作时间都是常量级的，因此时间复杂度为。
如果您觉得这篇文章对您有用，请不吝点赞和打赏哦。
