python中使用栈的简单介绍

python-033-实现栈-使用链表实现-提高时间复杂度

栈在我们之前的文章中就说明过了，想了解的去看一下030即可。

之前我们实现的栈，算法时间复杂度在摊销的情况下，是O(1)，其底层是python的列表，是一种动态数组，在内存中是一个固定长度的数组，是无法改变大小的，只有重新换一个更大的数组来装新的数据。虽然实现起来非常简单，但是并不够完美。

在我们最开始的几篇文章中，很详细的介绍了链表的各种使用方式。之前实现链表时，只声明了节点对象，但是我们在程序的使用中应该把链表作为一个整体，作为一个对象来使用，这样封装性更好。

今天就不写这个链表了，我们利用在栈类中定义一个 嵌套类 来做为链表的节点对象，因为创建节点的操作非常多，所以我们用 slots 来声明节点的两个成员变量，来减少内存的使用，提高效率。

链表是一种可以随时改变的数据结构。我们可以随时改变他的结构。

实现如下：

这次实现的栈的每一个方法操作，其时间复杂度都为O(1)，不需要摊销。这与用数组实现的栈形成了对比。

链表实现的更快，明天用链表实现队列。

相关问答

Q1: python多类化和栈有什么区别?

python多类化和栈有管理方式不同，生长方向不同的区别。Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义：

（1）程序内存布局场景下，堆与栈表示的是两种内存管理方式；

（2）数据结构场景下，堆与栈表示两种常用的数据结构。

堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别：

（1）管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏；

（2）空间大小不同。每个进程拥有的栈的大小要远远小于堆的大小。理论上，程序员可申请的堆大小为虚拟内存的大小，进程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB；

Q2: python中为什么要讲堆栈

1、因为堆栈是Python中处理数据不可或缺的一部分。

2、栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

3、由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

关于python中使用栈和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。