09 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
class CQueue:
def __init__(self):
self.a = []
self.b = []
def appendTail(self, value: int) -> None:
self.a.append(value)
def deleteHead(self) -> int:
if self.b:
return self.b.pop()
if not self.a:
return -1
while self.a:
self.b.append(self.a.pop())
return self.b.pop()
思路：维护两个栈，一个输入栈，一个删除栈。
心得：list.pop()是最后输入的一个元素，empty判断可以直接用list。
30 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.a = []
self.b = []
def push(self, x: int) -> None:
self.a.append(x)
if not self.b or self.b[-1] >= x:
self.b.append(x)
def pop(self) -> None:
if self.a.pop() == self.b[-1]:
self.b.pop()
def top(self) -> int:
return self.a[-1]
def min(self) -> int:
return self.b[-1]
思想：主要在于最小值的计算，维护两个栈，一个存储所有的元素，一个存储最小的。
注:>=，因为当=时，就被移除，因此push的时候也要考虑等号的情况。
32 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from queue import Queue
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
record = Queue()
result = []
if not root:
return result
record.put(root)
while not record.empty():
tmp = record.get()
result.append(tmp.val)
if tmp.left:
record.put(tmp.left)
if tmp.right:
record.put(tmp.right)
return result
思想：创建一个队列，将新节点的子节点不断放入队列中，直到队列为空。
32 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from queue import Queue
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
record = Queue()
if not root:
return result
record.put(root)
while not record.empty():
tmp1 = []
for i in range(record.qsize()):
tmp = record.get()
tmp1.append(tmp.val)
if tmp.left:
record.put(tmp.left)
if tmp.right:
record.put(tmp.right)
result.append(tmp1)
return result
思想：维护新的一层的载入节点，size只在开始的时候计算。
32 从上到下打印二叉树 III
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
record = collections.deque()
if not root:
return result
record.append(root)
while record:
tmp = collections.deque()
for i in range(len(record)):
tmp1 = record.popleft()
if len(result)%2:
tmp.appendleft(tmp1.val)
else:
tmp.append(tmp1.val)
if tmp1.left:
record.append(tmp1.left)
if tmp1.right:
record.append(tmp1.right)
result.append(list(tmp))
return result
思想：保持原有的顺序读数据，但是将存数据的方式设置为一个双向队列，以保存数据的results作为层数的隐式指标，用于确定从左往右还是从右往左。
tips：
-
collection.deque()// 双端队列； -
appendleft()：从右边往左插入；append()：从左边往右插入； -
list(collections.deque())//将queue转化为list。
