什么是数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系的组成。
数据结构就是设计数据以何种方式存储在计算机中，列表、字典等都算是数据结构。
程序=数据结构+算法，数据结构属于静态的部分，算法的调用为动态部分
数据结构的分类根据逻辑结构划分：
线性结构：数据结构中的元素一对一的关系，一前驱，一后继。
树结构：数据结构中元素一对多的关系，一前驱，多后继。
图结构：数据结构中元素存在多对多的关系，多前驱，多后继，我也不会。
判断一个图形能不能一笔画完，就判断它的奇数度节点数目是否为0或2.这种能一笔画完的就是欧拉图，奇数度节点为四个，就是两笔画完。
线性结构 列表 列表和数组python中的列表和其他语言中的数组很相似，区别为：
数组是定长的。
数组的数据类型也必须一致。
对列表或数组来说，它们的下标操作是最快的。
列表解决的变长问题的方式假设一开始在内存中分配了四个元素存储的空间，那么前四个元素的append操作不会出现问题。
当第五次append操作时，会先在内存中分配一个能够存储八个元素的空间，也就是翻倍。
然后进行复制，把以前的四个元素依次放到相应的位置上。
若再次超出长度，则继续执行上述操作。
也就是使用了动态表的原理
append操作会不会使速度变慢？
根据摊还分析，没有变长时的append和变长时的append均摊，最后的复杂度时O(3).
append越往后，变长时的出现频率就会越小
浪费了一部分空间，最坏情况应该是浪费了长度除二减一的空间。
列表解决多数据类型问题的方式对于纯整数的数组，它的每一个元素占4个字节，那么就事先计算好内存分配的大小，计算方法为：- 第一个元素的地址+元素个数 乘 4
python的列表里存的不是值，而是指向这个值的内存地址。
地址的大小是一样的，32位里地址是4个字节，64位里地址是8个字节。
这种方法的缺点是内存开销翻倍，这也是python被人诟病的地方。
栈 相关知识点总是能听到一个词 堆栈 ，堆(heap)和栈(stack)是两个东西，传统的编程语言中把内存分为两个地方，堆空间和栈空间，堆存储的是一些动态生成的对象，与数据结构中的堆是不同的，栈空间由系统调用，存放函数的参数值，局部变量的值。
应该是早年间翻译的问题，一般听到堆栈指的就是栈。
栈是一个数据集合，可以理解为只能在一端进行插入和删除操作的列表。
栈的特点：后进先出(last-in,first-out)
栈顶：操作永远在栈顶。
栈底：最后一个元素。
栈的基本操作：
进栈(压栈)：push
出栈：pop
取栈顶： gettop
关于出栈顺序的问题：
对于某个元素，如果进展顺序在它前面的元素出栈时在它后面，那么前面的元素顺序是相反的。
不知道说的明不明白
卡特兰数，n个数的出栈顺序，就是卡特兰数的第n项。
#栈的python实现 class Stack: def __init__(self,size): self.size=size self.top = 0 self.lst=[] def push(self,a): if self.top = self.size: raise StackFullError("stackoverflow") self.lst.insert(self.top,a) self.top+=1 def pop(self): if self.top = 0: raise StackEmptyError() b = self.list[self.top] self.lst.pop(self.top) returm b 栈的应用--括号匹配问题给定一个字符串，问其中字符串是否匹配。
括号本身满足栈的性质
匹配失败的情况：
括号不匹配
匹配完毕栈没空
栈空了又进元素
def brace_match(s): stack = [] d ={\'(\':\')\',\'[\':\']\',\'{\':\'}\'} for ch in s: if ch in {\'(\',\'[\',\'{\'}: stack.append(ch) elif len(stack)==0: print(\'多了%s\' %ch) return False elif d[stack[-1]] == ch: stack.pop() else: print(\'%s不匹配\'%ch) if len(stack)==0: return True else: print("未匹配") return False 队列 相关知识点：队列是一个数据集合，仅允许在列表的一端插入，另一端删除。
进行插入的时队尾，进行删除操作的是队首，插入和删除操作也被称为进队(push)和出队(pop)。
队列的性质：先进先出(first-in,first-out)
双向队列：两边都能进行插入删除操作的队列。
队列的数组实现：
简单的pop(0)操作复杂度过高，不采用。
由于数组定长，不能继续添加数据，如果是列表，出队的操作就会出现空位，所以想办法让数组变成一个圆环。
设置两个指针，队首指针front，队尾指针rear。
由于，队列满的时候和队列空的时候rear和front都在一个位置，那么就无法判断了。于是设置成队列满的时候减去一做为队满的标志。
这种队列就叫做环形队列。
当队尾指针front=最大长度+1时，再前进一个位置就自动到0.
实现方式：求余数运算
队首指针前进1：front=(front+1)%maxsize
队尾指针前进1：rear=(rear+1)%maxsize
队空条件：rear=front