聊一聊Python数据结构--栈
聊一聊Python数据结构--栈
刚开始学写代码的时候，我们都是想到什么就写什么，反正一个代码文件总归也不会太长。但等进一步深入编程之后，就不能没有章法地随便写了，也要讲究一些“套路”。“数据结构和算法”就是编程的重要套路之一。有了这些套路，我们可以更容易实现功能、让bug更少、代码运行效率更高、程序更容易维护和扩展。
既然有这么些好处，我们肯定要来说道说道。今天码哥就给你们来讲讲一个很基本的数据结构：栈。
栈是什么
栈是一种数据结构，而且是一种线性的数据结构。但跟我们接触最多的列表不同，栈有它特殊的操作规则：
- 只能从一端添加和移除元素（称作栈顶）
- 另一段是限制操作的（称作栈底）
直观点，你可以想象一个手枪的弹夹
永远只能从一端压入子弹，且从同一端弹出子弹。这样的结果就是，最先压进去的子弹会最后才被弹出，而最后压进去的子弹会最先弹出。
这个模式被称为 LIFO 后进先出（Last In First Out）。
栈数据管理模式就是 LIFO。
栈最常用的就是两个操作：
1. 存储数据，称为“入栈”或“压栈”（push）
2. 提取提取，称为“出栈”或“弹栈”（pop）
（这个叫法的创意大概就来源于弹夹吧）
栈有什么用
那么问题来了，为什么我们放着好好的可以随处插入和访问的列表不用，要折腾啥栈？
其实我认为，并不是用栈可以有什么神奇功效，而是有很多场景和需求的特点就是符合 LIFO。当我们解决这类场景的问题是，你自然而然就会创建出一个具有“栈”功能的数据结构。
现实中来说，比如我们去记录浏览器的回退记录、软件的操作撤销功能、IDE中的括号匹配检测，都是很典型的栈。而在程序内部和算法层面，使用到栈的地方就更多了，比如代码中函数的调用和返回，就是一个入栈出栈的过程。理解到这一点，对你理解函数的执行过程以及递归函数都很有帮助。还有如深度优先搜索，也是基于栈的结构实现的。
栈的实现
栈结构通常可用数组或链表实现。为了便于大家更好地理解栈这种数据结构，下面我们就用 python 里的 list 列表，来实现一个自己的栈。
功能需求：
创建一个 Stack 类，具备以下功能：
- Stack() - 创建新栈，不需要参数，返回空栈。
- push(item) - 将元素添加到栈顶，需要参数，无返回值。
- pop() - 删除栈顶元素，不需要参数，返回栈顶元素，并修改栈的内容。
- peek() - 返回栈顶元素，不需要参数，不修改栈的内容。
- isEmpty() - 检查栈是否为空，不需要参数，返回布尔值
- size() - 返回栈中元素个数，不需要参数，返回整数
开发思路：
我们画几张示意图，来理一下上述几个功能：
第一步 初始化栈：准备原料，一个栈与少量元素（元素是后面添加的不是初始化时创建）
第二步 push(item)：将原料放入栈中
第三步 peek(): 看看栈顶是个啥,哇看到了元素B
第四步 pop()：突然不想要 B了，赶紧取出来
栈与列表的对应操作：
栈的方法 | 对应的 Python 中列表的方法时 | 时间复杂度 |
|---|---|---|
stack.push(item) | list.append(item) | O(1) |
stack.pop() | list.pop() | O(1) |
stack.peek() | list[-1] | O(1) |
stack.isEmpty() | list == [] | O(1) |
stack.size() | len(list) | O(1) |
代码实现：
class Stack:
def __init__(self):
self.stack = []
self.size = 0
def push(self, item):
self.stack.append(item) # 添加元素
self.size += 1 # 栈元素数量加 1
def pop(self):
pop = self.stack.pop() # 删除栈顶元素
self.size -= 1 # 栈元素数量减 1
return pop
def isEmpty(self):
return self.stack == []
def sizes(self):
return self.size
def peek(self):
return self.stack[-1]
if __name__ = '__main__':
# 这里假定 A 是 4，B 是 'dog',建议每一步的结果用 print() 输出看一下
s = Stack()
s.isEmpty()
s.push(4)
s.push('dog')
s.peek()
s.pop()
s.isEmpty()以上便是一个栈的 Python 实现。
码哥之后还会跟大家讲解更多的数据结构，有什么想听的，可以在后台留言告诉我。感谢大家的阅读！
作者：码不理
来源：编程学习者社区