python数据结构之栈


概念

栈是线性数据结构的一种,是数据项的有序集合。添加项和移除项都发生在同一端,称为“顶端”,另一端称为“底端”。

因为添加项和移除项都在栈的顶端进行,因此最新添加的项在移除时也会被第一个移除,这种排序原则称为后进先出(LIFO),这意味着越靠近栈顶的项是越新的,越靠近栈底的项是越老的。

栈最常用的有两种操作,入栈(push)操作表示将数据压入栈顶,出栈(pop)操作表示将数据从栈顶弹出。

对于栈这种数据结构,日常生活中感觉最接近的是羽毛球筒,打开一端后,只能从这一端进行取出或者放入,而不能从中间或者底部抽取,这是栈与列表最大的不同之处。

图片源于网络

实现

栈与列表同属于线性数据结构,因此可以选择列表实现栈,问题在与选择列表的哪一端作为栈顶,栈的push(存入数据)操作对应着列表的append或者insert,pop(移除数据)对应着列表的pop,因为在列表尾部的append和pop时间复杂度都是O(1)的,而在列表头部的insert(0)和pop(0)时间复杂度是O(n)的,因此,选用列表的尾部作为栈顶。

具体代码如下:

class Stack:
    """利用基本数据结构list实现数据结构栈"""
    def __init__(self):
        #将栈初始化为空列表
        self.items = []

    def isEmpty(self):
        #判断栈是否为空,空栈则返回True
        return self.items == []

    def push(self, item):
        #将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 test_stack():
    """对栈进行测试"""
    s = Stack()

    print(s.isEmpty())
    s.push(1)
    s.push("stack")
    print(s.peek())
    print(s.size())
    s.push(True)
    s.push(1.0)
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.isEmpty())

if __name__ == '__main__':
    test_stack()

运行结果是:

True
stack
2
1.0
True
stack
1
True

经过测试,结果是正确的

栈的应用

简单括号匹配

LeetCode 20.有效的括号,题目链接

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true

示例 2:

输入: “()[]{}”
输出: true

示例 3:

输入: “(]”
输出: false

示例 4:

输入: “([)]”
输出: false

示例 5:

输入: “{[]}”
输出: true

第一种解法,完全用栈来解决:

def sym_matching(symbol_str):
    """symbol_str:待检测的括号字符串"""
    #如果待检测字符串长度是奇数,必定不匹配,直接返回false
    if len(symbol_str) % 2 == 1: return False
    #使用Stack之前注意是否需要导入
    s = Stack()
    index = 0
    while index < len(symbol_str):
        if symbol_str[index] in "([{":
            s.push(symbol_str[index])
        else:
            if s.isEmpty():
                return False
            else:
                top = s.pop()
                if not match(top, symbol_str[index]):
                    return False
        index += 1
    return True if s.isEmpty() else False

def match(begin, end):
    begins = "([{"
    ends = ")]}"
    return begins.index(begin) == ends.index(end)

还有更简洁的解法,利用字典+栈:

def sym_matching(s):
    if len(s) % 2 == 1: return False
    dict_symbol = {"(":")", "[":"]", "{":"}", "?":"?"}
    stack = Stack()
    stack.push("?")
    for i in s:
        if i in dict_symbol:
            stack.push(i)
        elif dict[stack.pop()] != i:
            return False
    return stack.size() == 1

进制转换

将十进制转换为二、八、十六进制

代码如下:

def base_convert(number, base):
    """
    number:待转换的十进制数
    base:将要转换的进制
    """
    digits = "0123456789ABCDEF"
    rem_stack = Stack()

    while number > 0:
        number, rem = divmod(number, base)
        rem_stack.append(rem)

    res_string = ""
    while not rem_stack.isEmpty():
        res_string += str(rem_stack.pop())

    return res_string

文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
  目录