栈和队列的实现【转】https://www.cnblogs.com/yiduobaozhiblog1/p/9272556.html
栈和队列是两种基本的数据结构，同为容器类型。两者根本的区别在于：
stack:后进先出
queue:先进先出
PS:stack和queue是不能通过查询具体某一个位置的元素而进行操作的。但是他们的排列是按顺序的
对于stack我们可以使用python内置的list实现，因为list是属于线性数组，在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求。当然，我们也可以使用链表来实现。
stack的实现代码（使用python内置的list），实现起来是非常的简单，就是list的一些常用操作
class Stack(object):
def __init__(self):
self.stack = []
def push(self, value): # 进栈
self.stack.append(value)
def pop(self): #出栈
if self.stack:
self.stack.pop()
else:
raise LookupError('stack is empty!')
def is_empty(self): # 如果栈为空
return bool(self.stack)
def top(self):
#取出目前stack中最新的元素
return self.stack[-1]
我们定义如下的链表来实现队列数据结构：
定义一个头结点，左边指向队列的开头，右边指向队列的末尾，这样就可以保证我们插入一个元素和取出一个元素都是O(1)的操作，使用这种链表实现stack也是非常的方便。实现代码如下：
class Head(object):
def __init__(self):
self.left = None
self.right = None
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
class Queue(object):
def __init__(self):
#初始化节点
self.head = Head()
def enqueue(self, value):
#插入一个元素
newnode = Node(value)
p = self.head
if p.right:
#如果head节点的右边不为None
#说明队列中已经有元素了
#就执行下列的操作
temp = p.right
p.right = newnode
temp.next = newnode
else:
#这说明队列为空，插入第一个元素
p.right = newnode
p.left = newnode
def dequeue(self):
#取出一个元素
p = self.head
if p.left and (p.left == p.right):
#说明队列中已经有元素
#但是这是最后一个元素
temp = p.left
p.left = p.right = None
return temp.value
elif p.left and (p.left != p.right):
#说明队列中有元素，而且不止一个
temp = p.left
p.left = temp.next
return temp.value
else:
#说明队列为空
#抛出查询错误
raise LookupError('queue is empty!')
def is_empty(self):
if self.head.left:
return False
else:
return True
def top(self):
#查询目前队列中最早入队的元素
if self.head.left:
return self.head.left.value
else:
raise LookupError('queue is empty!')
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
1 找出最高点
2 分别从两边往最高点遍历：如果下一个数比当前数小，说明可以接到水
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height) <= 1:
return 0
max_height = 0
max_height_index = 0
# 找到最高点
for i in range(len(height)):
h = height[i]
if h > max_height:
max_height = h
max_height_index = i
area = 0
# 从左边往最高点遍历
tmp = height[0]
for i in range(max_height_index):
if height[i] > tmp:
tmp = height[i]
else:
area = area + (tmp - height[i])
# 从右边往最高点遍历
tmp = height[-1]
for i in reversed(range(max_height_ind
ex + 1, len(height))):
if height[i] > tmp:
tmp = height[i]
else:
area = area + (tmp - height[i])
return area
python2的坑
在python2中，2/3 的结果是0，因为除法中是两个整数相除，所以取了整数，改为float(2)/3，就可以了。
而python3中不存在这个问题。
关于yield的解释 https://blog.csdn.net/qq_33472765/article/details/8083941
栈之计算器
224
This solution uses stack to store previous result and sign when encounter a "("
For this problem storing sign is enough, and will be faster.
def calculate(self, s):
res, num, sign, stack = 0, 0, 1, [1]
for i in s+"+":
if i.isdigit():
num = 10*num + int(i)
elif i in "+-":
res += num * sign * stack[-1]
sign = 1 if i=="+" else -1
num = 0
elif i == "(":
stack.append(sign * stack[-1])
sign = 1
elif i == ")":
res += num * sign * stack[-1]
num = 0
stack.pop()
return res
栈之基本计算器
224. 基本计算器
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例 1:
输入: "1 + 1"
输出: 2
示例 2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
用res存放累加值，遇到括号就把res入栈，然后置0计算括号内的和，根据前一个符号的sign来计算暂存值。
class Solution:
def calculate(self, s: str) -> int:
stack , num, sign, res = [], 0, 1, 0
for ss in s:
if ss.isdigit():
num = num*10+int(ss)
elif ss in ['+', '-']:
res += sign*num
sign = [-1,1][ss=='+']
num = 0
elif ss == '(':
stack.append(res)
stack.append(sign)
res, sign = 0,1
elif ss == ')':
res += num*sign
res *= stack.pop()
res += stack.pop()
num = 0
# sign = 1
return res+num*sign
227. 基本计算器 II
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
sum是中间向量，每次用前一个符号判断此时的操作，stack放'+''-'之间的结果，在字符串的首和尾加上'+'标记
class Solution:
def calculate(self, s):
num, sign, stack = 0, "+", []
for i,c in enumerate(s):
if c.isdigit():
num = 10*num + int(c)
if c in ["+", "-", "*", "/"] or i==len(s)-1 :
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack.append(stack.pop()*num)
elif sign == '/':
stack.append(int(stack.pop()/num))
num = 0
sign = c
return sum(stack)
栈之逆波兰表达式
使用栈的逆波兰表达式计算值是最简单的题目了 就是遇到数字就入栈，遇到符号就取出栈顶的两个元素做计算，且得到的结果入栈，遍历一遍表达式即可。
