线性数据结构---栈

写在前面

线性数据结构指的是元素之间的顺序是由插入和删除所决定的，一个元素被添加，那么它相对于前后项的位置就不变了。在线性数据结构这部分，我们主要了解四种类型，栈，队列，deque，列表，均用python实现，教材Problem Solving with Algorithms and Data Structures using Python http://interactivepython.org/courselib/static/pythonds/index.html

1、什么是栈

栈是项的有序集合， 它的特点是后进先出（LIFO），添加和移除总发生在一端，我们称之为'顶部'，相对应的另一端称之为'底部'。

figure1.png
这种反转的属性可以用到很多地方。 比如当你在浏览网页时，你浏览的网址会被存入栈中，最先浏览的网址在底部，现在浏览的网址在顶部。当你点击网页上的返回键的时候，这些网页按相反的顺序被返回回来。

2、栈的抽象数据类型

在栈中我们定义了以下操作：
stack(): 创建了一个新的空栈
isEmpty(): 判断栈是否为空，为空返回“True”, 不为空返回“False”
push(item): 将item添加到栈顶，它没有返回项，参数为item
pop(): 删除栈顶项，返回item,没有参数
peek(): 返回栈顶项，但并不删除，没有参数
size(): 返回栈中item的数量，不需要参数，返回一个整数

我们使用了列表作为底层实现，列表中的pop()、append()可以实现添加和删除操作。

class stack:
    def __init__(self):
        self.items=[]
    def isEmpty(self): ## 简洁一点的写法return self.items ==[]
        if len(self.items)==0:
            return True
        else:
            return False
    def push(self,item): #将一个新的项添加到栈的顶部，它需要item做参数并不返回任何内容
        self.items.append(item)
    def pop(self): #删除栈顶项，返回item,不需要参数
        item = self.items.pop()
        return item
    def peek(self):#返回栈顶的item,但并不会删除它，不需要参数
        item = self.items[len(self.items)-1]
        return item
    def size(self):
        return len(self.items)

stack-test.png

3、适用问题

在这部分，我们用几个例子说明栈的应用场景。

（1）括号匹配

在使用括号的时候，左括号和右括号成对出现，我们要做的就是对于一连串的括号，判断它们是否匹配。

括号示例.png
为什么括号匹配适合用栈处理呢？
在输入的时候，我们先输入左括号，当出现第一个右括号时，最后出现的左括号与之匹配，而与最后一个右括号相匹配的是最早出现的左括号。右括号以相反的顺序匹配左括号，这是一个可以用栈解决的问题。
figure2.png
算法流程
假设输入为一个只包含括号的字符串，遇到左括号，添加到栈，遇到右括号，则删除栈顶的左括号，这样操作之后，如果括号时匹配的，当右括号使用完，那么栈应该为空。若右括号有剩余，栈为空 或者 栈不为空，右括号无剩余，那么则不匹配。

def parChecker(symbolString):
    s = stack()
    for item in symbolString:
        if item =="(":
            s.push(item)
        elif item == ")":
            if not s.isEmpty():
                s.pop()
            else:  return False # 如果栈为空，但是还有右括号剩余，证明不匹配
    if not s.isEmpty():
        return  False # 如果右括号都没有剩余，但是栈中还有左括号，证明不匹配
    return True

example1 test.png

延伸 ：符号匹配

如果我们匹配的不仅仅是括号，还有 [ ],{ }，这就是我们接下来要说的符号匹配了，两者的思想都差不多。唯一一点区别在于，我们遇到的不仅仅是“）”，还有"]", "}"，遇到这些符号，我们要删除栈中相应的"(" "]" "}"

def parChecker(symbolString):
    s = stack()
    symbollist =[ "(","[","{"]
    symboldict ={")":0,"]":1,"}":2}
    for item in symbolString:
        if item in symbollist:
            s.push(item)
        else:
            if s.isEmpty():
                return False# 如果栈为空，但是还有右括号剩余，证明不匹配
            else:
                if symboldict[item] == symbollist.index(s.peek()): # 使用索引值和字典值匹配
                    s.pop()
                else: return False # 字符与栈中字符不匹配
    if not s.isEmpty():
       return  False # 如果右括号都没有剩余，但是栈中还有左括号，证明不匹配
    return True

example2 test.png

( 2 ) 十进制转化为二进制

为什么进制转换适合用栈处理呢？
进制转换过程中，我们不断除以进制数，得到余数，最后将余数倒序，就得到了转换后的数。这里再一次出现了反转属性，表明栈可能是解决这个问题的数据结构。

二进制.png
算法流程
假设我们要处理的数字为num, num不断除以2得到余数，添加到栈中，最后将栈中的余数弹出，得到结果。

def divideby2 (num):
    s=stack()
    binstring=""
    while num:
        res=num%2
        s.push(res)
        num = num//2
    while not s.isEmpty():
        binstring+=str(s.pop())
    return binstring

延伸： 任意进制

def dividebybase(num,base):
    s=stack()
    binstring=""
    digits="0123456789ABCDEF"
    while num:
        res=num%base
        s.push(res)
        num = num//base
    while not s.isEmpty():
        binstring+=str(digits[s.pop()])
    return binstring

(3) 中缀表达式转后缀表达式

我们平时所写的表达式称为中缀表达式，表示运算符号在两个操作数的中间。同时我们也可以将其写为后缀表达式和前缀表达式，前缀表达式 将所有的运算符都放置在操作数之前，后缀表达式将所有的运算符放在操作数之后。

后缀表达式.png
前缀表达式和后缀表达式.png

为什么中缀表达式转为后缀表达式适合用栈处理？
在书中的解释为，因为运算符号存在优先级，所以转换成后缀表达式会出现反转，考虑可以使用栈来处理这样的情况。若只考虑一般的情况，后缀表达式的运算符号顺序是与中缀表达式相反的，从某种程度上说可以用栈来处理。
算法流程
1、新建一个栈s用来保存运算符号和括号，新建一个空列表postfixlist用来保存转换后的中缀表达式
2、将要转换的中缀字符串用字符串拆分方法转换为标记列表
3、遍历标记列表中的每个元素：
          若为操作数，则直接添加到postfixlist
          若为"("左括号，则直接添加到栈s中
          若为操作符，添加到栈s，但要先比较操作符与栈中操作符的优先级，弹出栈中具有更高优先级的操作符到postfixlist，再添加到栈s
          若为"）"，则弹出栈中的操作符直至删除左括号
4、当输入表达式被完全处理时，检查栈中是否还有操作符，若有的话则全部弹出添加到postfixlist

def infixtopostfix(infixexpr):
    infixlist = infixexpr.split()
    s = stack()
    prec={"*":2,"/":2,"+":1,"-":1,"(":0}
    postfixlist=[]
    for item in infixlist:
        if item =="(":
            s.push(item)
        elif item == ")":
            flag=True
            while not s.isEmpty() and flag:
                if s.peek()!="(":
                    postfixlist.append(s.pop())
                else:
                    flag = False
                    s.pop() #当时写程序的时候忘记弹出左括号了
        elif item in ["+", "-" ,"*","/"]:
            sign = True
            while not s.isEmpty() and sign:
                if prec[s.peek()]>prec[item]:
                    postfixlist.append(s.pop())
                else: sign = False
            s.push(item)
        else:
            postfixlist.append(item) #若是操作符则加入到列表中
    while not s.isEmpty():
        postfixlist.append(s.pop())
    return " ".join(postfixlist)

test infixtopostfix.png
str.join(sequence) 指的是用字符str 链接序列sequence中的元素新生成的字符串，sequence是一个对象，如果有多个元素，那么就是元组或者列表，字符串也是可以的。 join.png

延伸：后缀表达式求值

因为运算符需要两个操作数，它只与最近的两个操作数有关，而与之前进入的数无关，有点反转的感觉，用栈处理时合适的。
给出一个后缀表达式如何求值呢？ 我们可以将操作数添加到栈中，待遇到了操作符，就从栈中弹出两个操作数，在进行运算，运算后的结果再添加到栈中，以便后续运算。最后栈中剩余的数字，就是所求的结果。

def postfixeval(postfixexpr):
    postfixlist = postfixexpr.split()
    s = stack()
    for item in postfixlist:
        if item in ["+","-","*","/"]:
            op2=s.pop()
            op1=s.pop()
            res=calculation(op1,op2,item)
            s.push(res)
        else:
            s.push(int(item))
    return s.pop()
def calculation(op1,op2,item):
    if item=="+":
        return op1+op2
    elif item=="-":
        return op1-op2
    elif item=="*":
        return op1*op2
    else: return op1/op2