这周把顺序表和单链表、双向链表、栈和队列能熟练的用C语言写出底层代码，下面是我自己的知识梳理：

1.顺序表

顺序表就是对数组的修饰，用结构体封装 基本框架为  :

struct SeqList{

Sqdatatype*(你要存储的数据类型)arr;

int size(有效元素个数)；

int capacity (数组总容量)；

}

相关代码https://gitee.com/O-tao/data-structure-1.git

它的优点 按下标查找复杂度为O（1），插入和删除元素为O（1）.

缺点：头插与头删为O（n），随机删除和插入也为O（n）.

2. 单链表与双向链表

链表的底层实现对指针的理解与操作要深，它们是在动态内存中一个个节点由指针连接，基本框架为：

单链表：

struct  SList {

Sdatatype(同上) data;

struct SList* next（指向下一个节点的指针）

}

双向链表：

struct  DList {

Ddatatype(同上) data;

struct DList* next（指向下一个节点的指针）

struct DList* prev(指向前一个节点)

}

它头节点里prev指向尾节点

它们相较于顺序表 它们头插的复杂度为o（1）,但尾插为o（n）,

最重要的是: 单链表是没有头节点 所以一开始为空的情况下要传二级指针改变指针的指向，如果传一级指针虽然形参改变了，但你返回到实参它还是指为空。    双向链表有头节点相当于“哨兵位”，只需要传一级指针因为它一定不为空。

在写力扣的时候也学到了一些算法思想（小白真的一点想不到）1：找链表的中间节点（数组也能用）

这个思想真的很巧妙，在fast(快指针)遍历完链表后，slow(慢指针)就是中间节点。在后续算法题的判断链表是否有环也能用，当slow会fast相遇时，则证明有环，反之亦然。还有如果有环返回入环节点，也是很巧妙，头节点和快慢指针相遇点到入环节点的距离相等。故当头节点和快慢指针相遇时就为入环节点。

相关代码实现https://gitee.com/O-tao/data-structure-1.git

3.栈和队列

栈的底层是用数组也就是跟顺序表类似，它有栈顶和栈底，它保存的数据从栈顶进（栈底是封闭的）只能先进后出，也就是只能从栈顶出。

队列的框架：

//创造节点
typedef int Qdata;
typedef struct QueueNode {
    Qdata data;
    struct QueueNode* next;
}QueueNode;

//创建队列
typedef struct Queue {
QueueNode*    phead;
QueueNode*    ptail;
}Queue;

这个数据结构我目前只知道对有效括号匹配的算法题能用（做题太少了哈哈哈哈！）

队列的话是双向的从队尾插入数据，从队头拿出数据

实现的算法题现在有栈实现队列，算法思想为：定义两个栈封装在结构体中，一个叫pushST,用来装数据，一个叫popST，用来出数据，刚好实现的就是队的思想先进先出

还有队列实现栈，算法思想为：定义两个队列封装在结构体，分别叫p1,p2。先入队，只要不为空就往p1入（往p2也行），然后出栈，往为p2(空的队列)中移入size-1个元素，最后返回p1的尾元素，然后一直循环。

代码实现https://gitee.com/O-tao/data-structure-1.git

以上就是我刚学数据机结构的一些笔记