学习资料:https://programmercarl.com/栈与队列理论基础.html
栈与队列
学习记录:
232.用栈实现队列(两个栈(stack_in, stack_out)实现一个队列的行为)
点击查看代码
class MyQueue(object):
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack_in.append(x)
def pop(self):
"""
:rtype: int
"""
if self.empty():
return None
if self.stack_out:
return self.stack_out.pop()
else:
for i in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self):
"""
:rtype: int
"""
ans = self.pop()
self.stack_out.append(ans)
return ans
def empty(self):
"""
:rtype: bool
"""
return not (self.stack_in or self.stack_out)
# 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()
225.用队列实现栈(一个两端队列deque实现栈的行为)
点击查看代码
class MyStack(object):
def __init__(self):
self.que = deque()
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.que.append(x)
def pop(self):
"""
:rtype: int
"""
if self.empty():
return None
for i in range(len(self.que)-1):
self.que.append(self.que.popleft())
return self.que.popleft()
def top(self):
"""
:rtype: int
"""
if self.empty():
return None
return self.que[-1]
def empty(self):
"""
:rtype: bool
"""
return not self.que
# 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()
20.有效的括号(栈行为的应用:消消乐;左括号取反存入栈;右括号与栈中右括号消除;有三种错误括号形式(左括号多了;右括号多了;左右括号不匹配,如'{(})'))
点击查看代码
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for item in s:
# 当出现左括号时,变成对应的右括号放到栈里
if item == '(':
stack.append(')')
elif item == '[':
stack.append(']')
elif item == '{':
stack.append('}')
# 当还未遍历完栈就为空,或者当前括号与栈顶元素不同时,都是错的
elif not stack or stack[-1] != item: # 要先判断栈为空的情况
return False
# 排除2、3种错误情况后,当前括号与栈顶元素一致,消除此栈顶元素
else:
stack.pop()
# 排除第1种错误,遍历完后如果栈中还有元素则错
if not stack:
return True
else:
return False
1047.删除字符串中的所有相邻重复项(消消乐,两两消除;逻辑:如果栈不为空且遍历值等于栈顶元素,则消除,其余情况都把遍历值添加到栈中)
点击查看代码
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
stack = [] # 用list模拟栈的行为
for item in s:
# 如果栈有元素且栈顶元素等于该遍历值,则消除
if stack and stack[-1]==item:
stack.pop()
# 如果栈之前没有元素或者元素不等于该遍历值,则添加
else:
stack.append(item)
return ''.join(stack)
PS:前两道题栈与队列相互实现操作的类,还有点迷糊,多刷
今天吃了酸汤云吞全家福美味,特别是香菇马蹄和紫菜馅儿的~
面试不顺啊,国企又礼貌又犀利