1. 数据结构之线性表结构学习笔记

数据结构：

        数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

    数据存储结构：按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。

            线性结构就是表中各个结点具有线性关系。数组、链表、栈和队列是最基本的数据结构。

                非线性结构就是表中各个结点之间具有多个对应关系。包括树、堆、图等。

        数据结构的基本操作：

            基本操作无非遍历 + 访问（增删查改），线性就是 for/while 迭代为代表，非线性就是递归为代表。

数组

用一组连续的内存空间，来存储一组具有相同类型的数据。

复杂度（优劣势比较）：

1）随机访问 ：复杂度为 O(1)；

2）插入：最好情况复杂度为 O(1)，最坏的情况复杂度为 O(n)；

3）删除：最好情况复杂度为 O(1)，最坏的情况复杂度为 O(n)。

基本操作:

队列

    队列也是一种特殊的线性表，和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。数据存储原则： 先进先出。

    复杂度（优劣势比较）：

        1）插入：最好情况复杂度为 O(1)；

        2）删除：最好情况复杂度为 O(1)。

基本操作:

from collections import deque


### 创建队列
queue = deque([1, 2, 3, 4])


### deque 入队（append） 在队列的末尾添加一个对象 object; (appendleft） 在队列的头部添加一个对象 object
queue.append(7)
>> deque([1, 2, 3, 4, 7])


queue.appendleft(0)
deque([0, 1, 2, 3, 4, 7])


### deque 出队（pop）获取最左边一个元素,并删除队列中最后一个元素；（popleft）获取最左边一个元素，并在队列中删除
queue.pop()
>> 7
queue.popleft()
>> 0


>> queue        
deque([1, 2, 3, 4])


### insert（在指定位置插入元素）
>> queue.insert(2,6)
deque([1, 2, 6, 3, 4])


队列 ：queue.append()  queue.popleft()

栈

    栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。数据存储原则： 后进先出。

    复杂度（优劣势比较）：

        1）插入：最好情况复杂度为 O(1)

        2）删除：最好情况复杂度为 O(1)

from collections import deque
 stack = deque()
栈：stack.append()  stack.pop()

链表

    链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。

    复杂度（优劣势比较）：

        1）随机访问 ：平均复杂度为 O(n)；

        2）插入：最好情况复杂度为 O(1)；

        3）删除：最好情况复杂度为 O(1)。

基本操作: 遍历 + 增删查改

实现：

    栈、队列  ：  python 内置模块  from collections import deque

    链 ：( SingleLink ) (GitHub ：https://github.com/JinYang-Law/-algorismS.git

参考：

python3 deque（双向队列） https://www.cnblogs.com/volcao/p/8728102.html

https://cloud.tencent.com/developer/article/1102593

https://blog.csdn.net/Eric_qiushui/article/details/82767934

链

https://segmentfault.com/a/1190000010819283

https://zhuanlan.zhihu.com/p/60057180