栈和队列的实现【转】https://www.cnblogs.com/yiduobaozhiblog1/p/9272556.html
栈和队列是两种基本的数据结构，同为容器类型。两者根本的区别在于：
stack:后进先出

image

queue:先进先出

image

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]

我们定义如下的链表来实现队列数据结构：

image

定义一个头结点，左边指向队列的开头，右边指向队列的末尾，这样就可以保证我们插入一个元素和取出一个元素都是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 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

image

示例:
输入: [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)

栈之逆波兰表达式
使用栈的逆波兰表达式计算值是最简单的题目了 就是遇到数字就入栈，遇到符号就取出栈顶的两个元素做计算，且得到的结果入栈，遍历一遍表达式即可。