Python数据结构01 线性结构

栈

实现

后进先出的结构，主要有如下操作
*Stack()
*push(item)
*pop()
*peek()
*isEmpty()
*size()

class Stack():
    def __init__(self):
        self.items=[]
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items)-1]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

append和pop()复杂度都是O(1),而如果push函数用self.items.insert(-1,item),pop()函数用pop(0),则复杂度会变成O(n)

应用

括号匹配

判断一个公式，例如{[（3+2）-5]*3}的括号是否匹配，可以采用栈。思路是遍历这个公式，每次读取到左括号([{时将其入栈，读到右括号时将其与栈顶左括号进行配对，如果是一对括号，那么该左括号出栈，配对成功。否则，配对失败，结束遍历输出信息。为了在配对失败的情况下立即停止，定义一个开关变量flag。配对的过程单独定义一个函数match

def match(lef,rig):
   a='([{'.find(lef)
   b=')]}'.find(rig)
   return a == b

def symCheck(symString):
    s=Stack()
    flag=True
    index=0
    while index < len(symString) and flag:
        if symString[index] in '([{':
            s.push(symString[index])
        elif symString[index] in ')]}':
            if s.isEmpty():
                flag = False
            else:
                top = s.pop()
                if not match(top,symString[index]):
                    flag=False
        index=index+1
    return flag

队列

实现

先进先出的结构

class Queue:
    def __init__(self):
        self.items=[]
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def isEmpty(self):
        return len(self.items) == []
    def size(self):
        return len(self.items)