栈
- 知识点
- 先出后进
- 代码实现
class Stack(object):
'''定义stack'''
def __init__(self):
self.items = []
'''是否为空'''
def is_empty(self):
if self.items:
print('false')
else:
print('true')
'''push'''
def push(self,item):
self.items.append(item)
'''pop(只能删除栈顶元素,故不用传入元素）'''
def pop(self):
self.items.pop()
'''peek(返回栈顶元素）'''
def peek(self):
return self.items[len(self.items)-1]
'''栈元素个数'''
def size(self):
return len(self.items)
- leetcode
- 括号匹配
s = input()
dic = {')':'(',']':'[','}':'{'}
stack = []
for i in s:
if stack and i in dic:
if stack[-1] == dic[i]:
stack.pop()
else:
print('False')
break
else:
stack.append(i)
print(not stack)
- 最小栈
运用辅助栈在push操作同时比较存储最小元素
class MinStack:
'''辅助栈'''
def __init__(self):
"""
initialize your data structure here.
"""
self.items = []
self.min_items = [math.inf]
def push(self, x: int) -> None:
self.items.append(x)
self.min_items.append(min(x,self.min_items[-1]))
def pop(self) -> None:
self.items.pop()
self.min_items.pop()
def top(self) -> int:
return self.items[-1]
def getMin(self) -> int:
return self.min_items[-1]
- 用栈实现队列
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.items = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.items.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
x = self.items[0]
self.items.pop(0)
return x
def peek(self) -> int:
"""
Get the front element.
"""
return self.items[0]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return self.items == []
