Py学习  »  Python

聊一聊Python数据结构--栈

Crossin的编程教室 • 4 年前 • 238 次点击  

刚开始学写代码的时候,我们都是想到什么就写什么,反正一个代码文件总归也不会太长。但等进一步深入编程之后,就不能没有章法地随便写了,也要讲究一些“套路”。“数据结构和算法”就是编程的重要套路之一。有了这些套路,我们可以更容易实现功能、让bug更少、代码运行效率更高、程序更容易维护和扩展。


既然有这么些好处,我们肯定要来说道说道。今天码哥就给你们来讲讲一个很基本的数据结构:


栈是什么


栈是一种数据结构,而且是一种线性的数据结构。但跟我们接触最多的列表不同,栈有它特殊的操作规则:

  • 只能从一端添加和移除元素(称作栈顶

  • 另一段是限制操作的(称作栈底


直观点,你可以想象一个手枪的弹夹:



永远只能从一端压入子弹,且从同一端弹出子弹。这样的结果就是,最先压进去的子弹会最后才被弹出,而最后压进去的子弹会最先弹出。


这个模式被称为 LIFO 后进先出(Last In First Out)


栈数据管理模式就是 LIFO。


栈最常用的就是两个操作:

1. 存储数据,称为“入栈”或“压栈”(push

2. 提取提取,称为“出栈”或“弹栈”(pop

(这个叫法的创意大概就来源于弹夹吧)


栈有什么用


那么问题来了,为什么我们放着好好的可以随处插入和访问的列表不用,要折腾啥栈?


其实我认为,并不是用栈可以有什么神奇功效,而是有很多场景和需求的特点就是符合 LIFO。当我们解决这类场景的问题是,你自然而然就会创建出一个具有“栈”功能的数据结构。


现实中来说,比如我们去记录浏览器的回退记软件的操作撤销功能IDE中的括号匹配检测,都是很典型的栈。而在程序内部和算法层面,使用到栈的地方就更多了,比如代码中函数的调用和返回,就是一个入栈出栈的过程。理解到这一点,对你理解函数的执行过程以及递归函数都很有帮助。还有如深度优先搜索,也是基于栈的结构实现的。


栈的实现


栈结构通常可用数组或链表实现。为了便于大家更好地理解栈这种数据结构,下面我们就用 python 里的 list 列表,来实现一个自己的栈。


功能需求:

创建一个 Stack 类,具备以下功能:

  1. Stack() - 创建新栈,不需要参数,返回空栈。

  2. push(item) - 将元素添加到栈顶,需要参数,无返回值。

  3. pop() - 删除栈顶元素,不需要参数,返回栈顶元素,并修改栈的内容。

  4. peek() - 返回栈顶元素,不需要参数,不修改栈的内容。

  5. isEmpty() - 检查栈是否为空,不需要参数,返回布尔值

  6. 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 实现。


码哥之后还会跟大家讲解更多的数据结构,有什么想听的,可以在后台留言告诉我。感谢大家的阅读!


作者:码不理

来源:编程学习者社区

原创不易,点个“在看”是对作者很大的鼓励
↘↘↘
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/48804
 
238 次点击