数据结构和算法001
资源来源网络，仅用于自己学习
时间复杂度- 大O表示法（Big O）
注意:大O 表示法仅仅是一种粗略的分析模型，是一种估算。
空间复杂度-- 估算所需占用的存储空间。
算法的优化方向：
数组
数组是一种顺序存储线性表，所有元素的内存地址是连续的。
数组的内存分布
很多编程语言中 数组无法动态修改容量
需要自己设计动态数组
1.接口设计
动态数组需要以下接口
链表
数组有个明显的缺点， 可能会造成内存空间的大量浪费。
链表可以做到 用多少就申请多少内存。
链表是一种链式存储的线性表，所有的元素地址不一定是连续的。
接口设计
链表的接口大部分和动态数组一样的
双向链表
数组：增删慢，查询快
链表：增删快，查询慢
栈
栈是一种特殊的线性表，只能在一端进行操作。。
入栈：往栈中添加元素的操作，- -般叫做push
出栈：从栈中移除元素的操作，- -般叫做pop
遵循 后进先出 的原则 Last In First Out (LIFO)
这里的栈 和内存中的栈空间是不同的概念
接口设计：
队列(Queue)
队列是一种特殊的线性表，只能再头尾两端进行操作。
队尾（rear ）：只能从队尾添加元素，一遍叫做enQueue,入队。
对头（front）：只能从对头移除元素，一般叫做deQueue,出队。
·
先进先出的原则 FIFO.
接口设计：
双端队列（Deque）
双端队列是可以在头尾两端添加 删除的队列
英文是deque是 double ended queue 的简称
双端队列两端都可以添加、删除元素。
接口设置：
循环队列（Circle Queue）
在队列的顺序存储表示时，如果还是用之前顺序表的模式来描述，则会显得很浪费空间。
因此采用一种循环的结构去实现队列的顺序存储。一般情况下，我们队满和队空时标志都是
Q->front=Q->rear;因此为了区别两种情况，在这里采用的方法是：牺牲一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”。
循环队列之空队列示意图：
循环队列满队列示意图如下：
入队：
初始化建空队列时，令front=rear=0；每插入新的队列元素时，尾指针增1
出队：
每当删除队列头元素时，“头指针增1”。
循环双端队列
可以进行两端添加、删除操作的循环队列