leetcode|力扣刷题_栈数据结构|链表

【简单】用两个栈实现队列题目链接
思路：双栈可以实现列表倒序，倒序后，stack_out执行出栈则相当于删除了stack_in的栈底元素，即对应队首元素

class CQueue:def __init__(self): self.stack_in = [] self.stack_out = []#创建两个空栈def appendTail(self, value: int) -> None: self.stack_in.append(value)#stack_in支持插入操作def deleteHead(self) -> int: #若out非空，则弹出倒叙排列后的最后一个元素（即原先的第一个元素） #若out为空，in不为空则倾倒in中的所有元素 #若out,in为空，则返回-1 while self.stack_out: return self.stack_out.pop() if not self.stack_in: return -1 else: self.stack_out = [self.stack_in.pop() for i in range(len(self.stack_in))] #将in中的所有元素倾倒至out中 return self.stack_out.pop()

【简单】包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
难点：在普通的栈中，min的复杂度是O(n)
思路：创建辅助栈 B 用来存储栈 A 中所有非单调减的元素

class MinStack:def __init__(self): """ initialize your data structure here. """ self.a = [] self.b = []def push(self, x: int) -> None: #若新增的元素小于等于a中的最小值，则进入b栈中 self.a.append(x) if not self.b: self.b.append(x) elif x<=self.b[-1]: self.b.append(x)def pop(self) -> None: #若a栈弹出的是其最小值，则b栈也要弹出相应元素 pop_0 = self.a.pop() if self.b[-1] == pop_0: self.b.pop()def top(self) -> int: return self.a[-1]def min(self) -> int: if self.b: return self.b[-1]