免费领取：测试资料+性能测试+接口测试+自动化测试+测试开发+测试用例+简历模板+测试文档 - 公众号 - 测试人社区

本文为霍格沃兹测试开发学社学员学习笔记分享
原文链接：数据结构与算法——渔舟唱晚 - 学习笔记 - 测试人社区

堆栈

数组和列表暴露了太多的接口，虽然操作灵活，但不可控，容易出错。如果在插入位置写错数据将会改变整个数组的内容
栈是**操作受限的列表

栈只能在一端进行删除和插入操作，遵循先进后出后进先出的原则

• 数组栈

class ArrayStack:    def __init__(self, volume):        self.vol = volume        self.count = 0        self.data = [-1] * volume    def in_stack(self, value):        """入栈"""        if self.count == self.vol:            return False        self.data[self.count] = value        self.count += 1        return True    def de_stack(self):        """出栈"""        if self.count == 0:            return None        self.count -= 1        return self.data[self.count]def test_stack():    array_stack = ArrayStack(5)    data = ["a", "b", "c", "d", "e"]    for i in data:        array_stack.in_stack(i)    result = array_stack.in_stack("a")    assert not result    data.reverse()    for i in data:        assert i == array_stack.de_stack()    assert not array_stack.de_stack()

入栈时间复杂度：O(1)
出栈时间复杂度：O(1)

• 链式栈

class LinkStack:    class Node:        def __init__(self, data):            self.data = data            self.next = None    def __init__(self):        self.top = None    def en_stack(self, value):        """入栈"""        new_node = self.Node(value)        if self.top is None:            self.top = new_node        else:            new_node.next = self.top            self.top = new_node    def de_stack(self):        """出栈"""        if self.top is None:            return -1        result = self.top.data        self.top = self.top.next        return resultdef test_link_stack():    link_stack = LinkStack()    data = [1, 2, 3, 4, 5]    for i in data:        link_stack.en_stack(i)    data.reverse()    for j in data:        assert j == link_stack.de_stack()    assert link_stack.de_stack() == -1

入栈时间复杂度：O(1)
出栈时间复杂度：O(1)