一、什么是数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合，集合中数据元素之间的关系组成。
简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
比如Python中：列表、集合与字典等都是一种数据结构。
N.Wirth: “程序=数据结构+算法”
分类：
数据结构按照其逻辑结构可分为线性结构、树结构、图结构
线性结构：数据结构中的元素存在一对一的相互关系
树结构：数据结构中的元素存在一对多的相互关系
图结构：数据结构中的元素存在多对多的相互关系
二、几种常见的数据结构
栈：
是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表
特点： 后进先出
基本操作
进栈(压栈)：push 出栈：pop 查看栈顶元素 li[-1] 面试题： 进栈序列为 ABCDE 哪一个不是出栈序列 ACBDE AEDCB * ADBCE ABDCE 123 进栈 不可能312出栈
括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。
例如：
()()[]{} 匹配
([{()}]) 匹配
[]( 不匹配
[(]) 不匹配
代码实现：
def brace_match(s): stack = [] dic = {'(': ')', '{': '}','[': ']'} for ch in s: if ch in {'(','{','['}: stack.append(ch) elif ch in {')', '}', ']'}: if len(stack) == 0: return False elif dic[stack[-1]] == ch: stack.pop() # 匹配,出栈 else: return False else: pass if len(stack) > 0: # 栈不空 return False else: return Ture
队列：
队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
队列的性质：先进先出(First-in, First-out)
双向队列：队列的两端都允许进行进队和出队操作。
队列能否简单用列表实现？为什么？ 初步设想：列表+两个下标指针
创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。
进队操作：元素写到li[rear]的位置，rear自增1。 出队操作：返回li[front]的元素，front自减1。
链表：
链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域key和指向下一个节点的指针next。
通过各个节点之间的相互连接，最终串联成一个链表。
节点定义：
class Node(object): def __init__(self, item): self.item = item self.next = None
双链表：双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。
class Node(object): def __init__(self, item=None): self.item = item self.next = None self.prior = None
链表在插入和删除的操作上明显快于顺序表
链表的内存可以更灵活的分配
哈希表：
哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
insert(key, value)：插入键值对(key,value)
get(key)：如果存在键为key的键值对则返回其value，否则返回空值
delete(key)：删除键为key的键值对
直接寻址表：
当关键字的全域U比较小时，直接寻址是一种简单而有效的方法。
直接寻址技术缺点：
当域U很大时，需要消耗大量内存，很不实际
如果域U很大而实际出现的key很少，则大量空间被浪费
无法处理关键字不是数字的情况
直接寻址表：key为k的元素放到k位置上
改进直接寻址表：哈希（Hashing）
构建大小为m的寻址表T
key为k的元素放到h(k)位置上
h(k)是一个函数，其将域U映射到表T[0,1,...,m-1]
哈希表：
哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。
哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
哈希表在Python中的应用---字典与集合都是通过哈希表来实现的。
二叉树
二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
二叉树的遍历：
前序遍历：EACBDGF
中序遍历：ABCDEGF
后序遍历：BDCAFGE
层次遍历：EAGCFBD
二叉搜索树：
二叉搜索树是一颗二叉树且满足性质：设x是二叉树的一个节点。如果y是x左子树的一个节点，
那么y.key ≤ x.key；如果y是x右子树的一个节点，那么y.key ≥ x.key.
