代码随想录算法训练营第十天｜栈和队列理论基础、232. 用栈实现队列、225. 用队列实现栈、20. 有效的括号、1047. 删除字符串中的所有相邻重复项

栈和队列理论基础

（1）栈：先进后出

（2）栈操作时间复杂度

（3）python中栈的操作

• 创建栈：使用列表（list）创建栈

stack = []

• 入栈操作：将元素添加到栈顶

stack.append(1)

• 出栈操作：从栈顶删除元素

top_element = stack.pop()

• 查看栈顶元素：查看但不删除

top_element = stack[-1] 

• 判断栈是否为空：判断栈长度是否为0

is_empty = len(stack) == 0  

• 遍历栈

while len(stack) != 0:temp = stack.pop()# 对temp进行操作

（4）队列：先进先出

（5）队列操作时间复杂度 = 链表

（6）python中队列的操作

collections.deque

from collections import deque

• 获取出队元素：deque[0]
• 获取入队元素：deque[-1]

232. 用栈实现队列

题目链接：232

1、题目描述

使用栈实现队列的下列操作：

• push(x) – 将一个元素放入队列的尾部
• pop() – 从队列首部移除元素。
• peek() – 返回队列首部的元素。
• empty() – 返回队列是否为空。

2、思路

# 用两个栈模拟队列：一个栈当作队列入口，一个栈当作出口
# 入队就直接把元素推入入栈
# 出队：判断出栈有没有元素：没有：把入栈的所有元素全部已到出栈，之后pop栈首；有：直接出栈
# peek就是出队之后，又把元素放入到出栈里面
# empty就是查看两个栈的元素是否为空

3、code

class MyQueue(object):# 用两个栈模拟队列：一个栈当作队列入口，一个栈当作出口# 入队就直接把元素推入入栈# 出队：判断出栈有没有元素：没有：把入栈的所有元素全部已到出栈，之后pop栈首；有：直接出栈# peek就是出队之后，又把元素放入到出栈里面# 查看两个栈的元素是否为空def __init__(self):self.instack = []self.outstack = []def push(self, x):""":type x: int:rtype: None"""self.instack.append(x)def pop(self):""":rtype: int"""if len(self.outstack) != 0:return self.outstack.pop()else:for i in range(0,len(self.instack)):self.outstack.append(self.instack.pop())return self.outstack.pop()def peek(self):""":rtype: int"""t = self.pop()self.outstack.append(t)return tdef empty(self):""":rtype: bool"""if len(self.instack) == 0 and len(self.outstack) == 0:return Trueelse:return False# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

4、复杂度分析

1️⃣ 时间复杂度：

• push：O(1)
• pop:O(N)
• peek : O(N)
• empty : O(1)

2️⃣ 空间复杂度：
O(N)

225. 用队列实现栈

题目链接：225

1、题目描述

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

2、思路

用一个队列实现😄
push : 就直接入队
pop：需要把最后一个元素之前的全部元素全部取出，并依次重新入队，最后弹出队首元素就是栈顶元素
top：先pop，之后把取出的元素入队
empty：判断队列就好🆗

3、code

from collections import deque
class MyStack(object):def __init__(self):self.q = deque()def push(self, x):""":type x: int:rtype: None"""self.q.append(x)def pop(self):""":rtype: int"""for i in range(0,len(self.q)-1):self.q.append(self.q.popleft())return self.q.popleft()def top(self):""":rtype: int"""t = self.pop()self.q.append(t)return tdef empty(self):""":rtype: bool"""if len(self.q) == 0:return Trueelse:return False# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty() 

4、复杂度分析

1️⃣ 时间复杂度：

• push:O(1)
• pop : O(N)
• top: O(N)
• empty:O(1)

2️⃣ 空间复杂度：
O(N)

20. 有效的括号

题目链接：
20

1、题目描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

2、思路

使用一个栈，保存左边的括号，当遇到左边的括号就入栈，当遇到右边的括号，就pop栈顶元素，判断是否是一对儿（要注意，先判断栈是否还有元素，如果没有，说明第一个就是右边的括号->False），最后判断栈里面是否还有元素。
🔥 优化的点：
使用哈希表，keys代表左边的括号，values代表右边的括号

3、code

"""
普通版本
"""
class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""stack = []for x in s:if x == '(' or x == '[' or x == '{':stack.append(x)else:if len(stack) == 0:return Falseelse:t = stack.pop()if x == ')' and t != '(':return Falseelif x == ']' and t != '[':return Falseelif x == '}' and t != '{':return Falseif len(stack) == 0:return Trueelse:return False
"""
优化版本
"""# 方法二，使用字典
class Solution:def isValid(self, s: str) -> bool:stack = []mapping = {'(': ')','[': ']','{': '}'}for item in s:if item in mapping.keys():stack.append(mapping[item])elif not stack or stack[-1] != item: return Falseelse: stack.pop()return True if not stack else False       

4、复杂度分析

1️⃣ 时间复杂度：for遍历分析O(N)
2️⃣ 空间复杂度：受用栈O(N)

1047. 删除字符串中的所有相邻重复项

题目链接：1047

1、题目描述

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

2、思路

1️⃣ 栈：使用栈记录从左边开始的字符，当遇到一个元素，就把栈顶元素和当前元素进行比较，如果一样就需要把栈顶元素丢了
2️⃣双指针：快指针遍历，慢指针记录最后的保留元素
当慢指针发现前一个字符和当前字符一样就该把慢指针回退，并把快指针的值赋值给慢指针，如果不相等才移动快指针

3、code

"""
栈
"""
class Solution(object):def removeDuplicates(self, s):""":type s: str:rtype: str"""stack = []s_list = list(s)for x in s_list:if len(stack) >= 1 and x == stack[-1]:stack.pop()else:stack.append(x)return "".join(stack[:])
"""
双指针
"""
class Solution(object):def removeDuplicates(self, s):""":type s: str:rtype: str"""fast = 0 # 用来遍历字符串slow = 0 # 用来记录最终保留的字符串list_s = list(s)for fast in range(len(s)):list_s[slow] = list_s[fast]if slow > 0 and list_s[slow-1] == list_s[slow]:slow -= 1else:slow += 1return "".join(list_s[0:slow])          

4、复杂度分析

1️⃣ 时间复杂度：O(N)
2️⃣ 空间复杂度：栈O(N)双指针O(N)