您的位置:

python数据结构之栈结构(Python基本数据结构)

本文目录一览:

python中的堆栈什么意思

堆栈是一种执行“后进先出”算法的数据结构。

设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球,小球的直径比竹筒的直径略小。现在把不同编号的小球放到

竹筒里面,可以发现一种规律:先放进去的小球只能后拿出来,反之,后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的

特点。

堆栈是计算机中最常用的一种数据结构,比如函数的调用在计算机中是用堆栈实现的。 堆栈可以用数组存储,也可以用以后会介绍的链

表存储。

堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域,数据一个一个顺序地存入(也就是“压入——push”)这个区域之中。

有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元,存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫

做“栈底”。数据一个一个地存入,这个过程叫做“压栈”。在压栈的过程中,每有一个数据压入堆栈,就放在和前一个单元相连的后面

一个单元中,堆栈指示器中的地址自动加1。读取这些数据时,按照堆栈指示器中的地址读取数据,堆栈指示器中的地址数自动减 1。这

个过程叫做“弹出pop”。如此就实现了后进先出的原则。

推荐学习《python教程》。

Python数据结构与算法-利用列表实现栈

概念:

栈:

名称的由来:这个名字来源于自动售货机中用弹簧顶住的一堆盘子的隐喻。

概念:这里提到的栈是一种抽象的数据结构

,而非空间内存分配处涉及的空间存储的概念。但是大同小异,原理还是来自于对栈空间的理解。这里的栈是有一系列对象组成的一个集合,这些对象的插入和删除操作遵循后进先出(LIFO)原则。用户可以在任意时刻向栈中插入一个对象,但只能取得或者删除最后一个插入的对象(即所谓的栈顶)。

目的:通过列表实现栈

有些同学可能认为,是不是还有其他操作没有完成,为什么不能在中间插入或者其他操作,因为栈不具备这些功能,所以实现的都是栈的常规功能。

利用栈实现数据的逆置

由于LIFO协议的限制,栈可以用作一种通用的工具,用于实现一个数据序列的逆置,这一思想可以用于很多方面,例如以降序

的方式显示一个数据集,我们可以通过先逐行读取数据,然后压如一个栈中,在按照从栈中弹出的顺序来写入。这个方法的实现过程如下:

python中的数据结构分析?

1.Python数据结构篇

数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录,当然,也结合了部分[算法导论](Introduction to Algorithms)

中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例

如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文

章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。

**这一部分是下

面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,我个人认为直接读算法设计篇比

较好,因为大家时间也都比较宝贵,如果你会来读这些文章说明你肯定有一定基础了,后面的算法设计篇中更多的是思想,这里更多的是代码而已,嘿嘿。**

(1)[搜索](Python Data Structures)

简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突)

(2)[排序](Python Data Structures)

简述各种排序算法的思想以及它的图示和实现

(3)[数据结构](Python Data Structures)

简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆

(4)[树总结](Python Data Structures)

简述二叉树,详述二叉搜索树和AVL树的思想和实现

2.Python算法设计篇

算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**点击链接可进入Springer免费下载原书电子版**]之后写下的读书总结,原书大部分内容结合了经典书籍[算法导论](Introduction to Algorithms),

内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排

序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并

没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但

是我想我的介绍应该还算简单明了,因为我用的都是比较朴实的语言,并没有像算法导论一样列出一堆性质和定理,主要是对着某个问题一步步思考然后算法就出来

了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩真的不容错过!

这里每篇文章都有实现代码,但是代码我一般都不会分

析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算

法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟

们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。

本篇的顺序按照原书[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。

**1.

你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这

个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等,采用问答式的方式让读者和我一起来想出某个问题的解,每篇

文章之后都还有一两道小题练手哟**

**2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂

不更好些,当然,你如果想读算法导论的话我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科

普的啦,没有多少人能够坚持读完的。但是码农与蛇的故事内容不多哟,呵呵呵**

**3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,前面三节内容都是介绍基础知识,所以精彩内容从第4节开始哟,么么哒 O(∩_∩)O~**

(1)[Python Algorithms - C1 Introduction](Python Algorithms)

本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。

(2)[Python Algorithms - C2 The basics](Python Algorithms)

**本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。**

(3)[Python Algorithms - C3 Counting 101](Python Algorithms)

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

(4)[Python Algorithms - C4 Induction and Recursion and Reduction](Python Algorithms)

**本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分**

(5)[Python Algorithms - C5 Traversal](Python Algorithms)

**本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法**

(6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms)

**本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法**

(7)[Python Algorithms - C7 Greedy](Python Algorithms)

**本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树等等**

(8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms)

**本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比**

(9)[Python Algorithms - C9 Graphs](Python Algorithms)

**本节主要介绍图算法中的各种最短路径算法,从不同的角度揭示它们的内核以及它们的异同**