栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或者删除的列表,栈的特点是先进后出LIFO(last-in, first-out),本文用Python的列表,来实现一个栈结构。

栈的概念:栈顶、栈底

基本操作:进栈(压栈):push、出栈:pop、取栈顶:gettop

栈结构

当然,不定义类,只使用列表的push和pop方法也可以。

class Stack():
    def __init__(self):
        self.data = []

    def push(self, elem):
        self.data.append(elem)

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

    def gettop(self):
        if len(self.data) > 0:
            return self.data[-1]
        else:
            return None


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) #3
print(stack.gettop()) #2

栈的运用:括号匹配问题

给定一个字符串,其中包括小括号、中括号、大括号,判断该字符串中的括号是否匹配。

例如:

()[]{}、([{}])  匹配

[](、([)]  不匹配

def is_match(string):
    map = {'}':'{', ']':'[', ')':'('}
    stack = Stack()
    for s in string:
        # 栈顶有值且匹配
        top = stack.gettop()
        if top and map.get(s) == top:
            stack.pop()
        else:
            stack.push(s)
    # 最后栈内没有元素
    if not stack.gettop():
        return True

string = '[]('
print(is_match(string))

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/283