认识数据结构之列表、栈_栈和列表

我们之前介绍到一些查找，排序的算法，但是也没和数据结构进行联系，接下来咱们一起看看吧！

 

算法用来解决实际问题，数据结构用来解决各个数据结构的存储问题，抛砖引玉，有没有觉得python和java、c的数组结构有点类似，通过下标来访问数据...

但其实他们还是有一定的差异。

数组/列表：
列表（其他语言称为数组）是一种基本的数据结构。

关于列表的问题：

• 列表中的数据如何存储？
• 列表的基本操作：按下标查找、插入元素、删除元素...
• 这些操作的时间复杂的是怎么的呢？

拓展：Python的列表是如何实现的呢？

先来看看c语言的数据存储方式：

c语言采用地址顺序存储数据，每个数据会有一个对应地址，数据与数据间的地址是等距离连续的，例如：在32位上的平台，一个整数占4个字节，一个地址占四个字节，地址距离为4个字节。

注意：c语言的数组的是相同类型的数据，而Python是没有对应要求的。

Python列表的数据存储方式是根据地址指向其对应的数据来实现的 例如（地址为：293 对应数据："hello world" 地址为：28 对应数据：1...）

数组与列表的两点不同：

1. 数组元素需要相同，列表数据都行
2. 创建数组时，数组的长度就限定了，但是列表可以增添，删除，修改...

接下来看看什么叫做"栈"：
栈（Stack）是是一个数据集合，可以理解为只能在一端进行插入(append())或者删除(pop)操作的列表。

栈的特点：先进后出。

栈的概念：栈顶、栈底、

进栈：push   出栈：pop

 只能对堆顶进行操作，其他地方不行，添加（append）删除（pop） 取栈顶list-1[]

栈的实现：

使用一般的列表结构即可是实现.

实现代码：

接下来看看常见的问题：
括号匹配问题：
括号匹配问题 给你一个字符串 包含有（）[] {} 求该字符串是否匹配？

例如：

（）匹配

[]{} 匹配

{[()]} 匹配

{(}) 不匹配 各种括号间不能交叉

 .....

代码演示：

 

 思路：
建立栈：包括进栈，使用append()函数 记得传入参数；出栈，利用pop()可以查到每一次出栈的内容（栈是先进后出，与后面的队列不一样 队列是先进先出） 判断栈是否为空；取堆顶（栈不为空才可以取堆顶，不然返回None）

括号匹配函数：先建好一个栈，传入一个字符串 利用栈的性质判断括号匹配问题。利用字典方便对堆顶的判断，是否匹配，如果配上了 就删除堆顶  例如：现在堆顶是'{' 现在匹配好了 '}' 两者就相消了！ 还有一种情况 栈不空 (( } 突然来了一个不匹配的反大括号 直接不能匹配 return 终止函数。

栈这种数据结构的特点：

先进后去，，每次处理只能对堆顶操作 其他地方是不能处理的！！！

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

接下来我们看看和栈对立的一种数据结构  队列

队列（Queue）是一个数据集合，仅允许在列表的后面插入 前面出来     f  r  

进行插入的一段叫队尾（rear），插入动作称为入队；

进行删除的一段叫做队头（front）,删除动作称为出队；

队列的性质：先进（r）先出(f)   r控制进 f控制出  从后面进往前面出。

队列如何实现？

可以使用指针的思想 两个指针(r、f)   r控制进 f控制出

每次进一个r就往上走 每次删一个f也往上走 栈为空时：r f两个指针指向一起 栈满时：r追上f。

那列表的长度设置呢？

这里我们可以变换成一个环形队列 过程：从队列为空 到 队列全满（队列全满是结束这个过程）。

粗俗地可以理解为：当r（负责进数）追上f（负责出数）时，队列满了 队列结束了。

注意：
队列满了不是全部满 而是f指向空的 r在后面隔了一块内存  区别于队列为空（r==f）和队列满了。 

那这个队列应该长成什么样式呢？

可以想象为一个环形列表。

 

 

那假设r已经走了一圈，但是还没有追上f，r如何回到0这个下标呢？

设计十分巧妙，假设一个数为n 他与任何数%  是不是等于（0~n-1） 没问题吧！

我们就可以让r=(r+1)%列表长度

队首指针前进1：rear=(rear+1)%list_length

队尾指针前进1：front=(font+1)%list_length

队空条件：rear=front

队满条件：front=(rear+1)%list_length

代码及测试结果如下：

 

 队列的总结：

利用(r+1)%list_length重新回到起点  队列的最终目标：r追上f 使得队列满了；

队列空是当r==f的时候 ，队列满不是吧所有内存都占满了 牺牲了一小块内存来区别于队空。

队列这种数据结构的特点：

先进先出，从后面进到从前面出。rear追上font时 队满 游戏结束 r追f的故事。

其实Python这门脚本语言已经帮我们写好了队列的代码：

直接第三方库调用就好了！！！

Python中的内置模块：
队列分为单项队列和双向队列

增加知识：queue这个库保证进程安全

内置模块是双向队列：

左边进（appendleft）出(popleft)      右边出(pop)进(append)

双向队列的两端都支持进队和出队操作

• 队首进队
• 对首出队
• 队尾进队
• 队尾出队

使用方法：from collections import deque  导入Python中队列的内置模块

测试代码如下：

 

 

 我们可以利用这种特性，获取一个文件后n行的数据 类似于linux里的tail命令：

谢谢大家的阅读，下一期我将会发布利用栈和队列这两种数据结构解决迷宫问题。