栈——Python数据结构

线性结构 (Linear Structure) 是一种有序数据项的集合，其中每个数据项都有唯一的前驱与后驱。不同的线性结构关键的区别在于数据项增删的方式

栈 Stack 的基础性质

栈的增删示意图

• 有向数据项集合，数据项的增删都在同一端（栈顶 Top ）

• 后入先出 LIFO Last in First out

• python 实现栈

  
  栈的抽象数据类型

用 list 的尾端list[-1]做栈顶，push pop 的复杂度均为 O(1)

class Stack:

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def size(self):
        return len(self.items)

用 list 的首端list[0]做栈顶，push pop 的复杂度均为 O(n)

class Stack:

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        self.items.insert(0,item)

    def pop(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

    def size(self):
        return len(self.items)

栈的应用

1. 简易括号匹配
   从左向右扫描括号，最新打开的左括号 ( 应该匹配到最先遇到的右括号 ) .
   实现思路：从左往右入栈，遇到 ( 直接入，遇到 ) 不用入栈并且pop() 一次。读完所有如果栈空就是完全匹配

class Stack:

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def size(self):
        return len(self.items)

def parChecker(symbs):
    
    s = Stack()
    for i in symbs:
        if i == ')':
            if s.isEmpty():
                return False
            else:
                s.pop()
        elif i == '(':
            s.push(i)
    return s.isEmpty()

print('():', parChecker('()'))
print('(())):', parChecker('(()))'))
print('):', parChecker(')'))

2. 通用括号匹配

通用版的括号匹配需要考虑的除了 () 之外还有[] {} <>

待更