栈的存储结构
顺序存储
顺序栈：利用一组地址连续的的存储单元依次存放自栈底到栈顶的所有数据元素，利用了数组实现，我们将数组索引为0的一端作为栈底，另一端作为栈顶。
代码实现
class SequenceStack: """顺序栈""" def __init__(self): """初始化""" self.stack_arr = [] self.top = -1 self.maxsize = 10 # 设置栈的最大长度 def push(self, arg): """入栈""" if self.top + 1 >= self.maxsize: print("栈已满，请重新选择操作") return self.stack_arr.append(arg) self.top += 1 def pop(self): """出栈""" if self.top < 0: print("栈以空无法出栈") return self.top -= 1 return self.stack_arr.pop() def gethead(self): """得到栈顶的元素""" if self.top < 0: print("栈以空") return return self.stack_arr[self.top] def isempty(self): """判断栈是否为空""" if len(self.stack_arr) == 0: return True else: return False def size(self): """栈中的元素""" return len(self.stack_arr) def next(self): """从栈顶遍历到栈底""" for i in self.stack_arr: print(i) def clear(self): """清空栈""" self.stack_arr.clear() self.top = -1
链式存储
栈的链式存储结构称为链栈，利用的链表实现，链表中的每个元素由两个部分组成，一部分是存储本身的数据信息，一部分存储其直接后继的内存地址，分别叫做为数据域，地址域
链表和顺序表的功能都一样，我就不分开介绍了。因为存储结构的不同，导致代码内部的实现方法不同，大家仔细看一下代码实现的区别就行了。
链栈的基本结构
入栈出栈
代码实现
class LinkStack: def __init__(self): self.length = 0 self.top = None def push(self, arg): """入栈""" self.top = Node(data=arg, next=self.top) self.length += 1 def pop(self): """出栈""" if self.top == None: print("栈已空，无法删除元素") return x = self.top.data self.top = self.top.next self.length -= 1 return x def gethead(self): """获取栈顶的元素""" if self.top == None: print("栈已空，无法删除元素") return return self.top.data def size(self): """求出栈中数据元素的个数""" return self.length def isEmpty(self): """判断栈是否为空""" return self.top == None def next(self): """遍历""" p = self.top while p != None: print(p.data) p = p.next def clear(self): """清空栈""" self.top = None self.length = 0
顺序栈和链栈的区别
顺序存储：存储空间预先分配，可能会出现空间闲置或溢出的现象，元素个数不能自由扩充。
链式存储：动态分配，不会出现闲置或者栈溢出的现象，数据元素可以自由扩充
栈的实战题目
实战的题目这里选择的就是牛客网中系列题 👉传送门
由于篇章的限制，这里我就写一个比较经典的算法有效括号匹配，其余的题目我会出新的文章
有效括号序列
class SequenceStack: # 这个类可以选择上面的任意一个类，这里就不再进行重复了，主要说算法的实现方式 pass def brace_match(s): """验证括号是否合法""" if len(s) == 0: """当长度为0的时候直接返回""" return False match = {'}': '{', ']': '[', ')': '('} # 右括号和左括号的键值队，用于后面的判断 stack = SequenceStack() # 创建栈 for ch in s: if ch in {'{', '[', '('}: # 只让左括号进栈 stack.push(ch) else: if stack.isEmpty(): return False elif stack.gethead() == match[ch]: # 当元素为右括号的时候，如果和栈顶的元素是一对括号的时候，栈顶的元素出栈 stack.pop() # stack_top() != match(ch) else: return False # 最后判断栈是否为空，如果栈为空则代表该序列是有效的括号序列 # 如果栈非空则代表栈不为空 if stack.isEmpty(): return True else: return False
