数据结构
栈 Stack
栈是一种线性结构，相比数组，栈对应的操作是数组的子集。只能从一端添加元素，也只能从一端去除元素，这一端成为栈顶。
栈是一种后进先出的数据结构（Last In First Out）
栈的应用
- 无所不在的Undo（撤销）操作
- 程序调用的系统栈
- 函数之间的子调用，使用栈记录每次调用过程中中断的点
实例
有效的括号
/** * 有效的括号 * @param string $s * @return boolean */ function isValid(string $s){ $left = [ '(', '[', '{' ]; $stack = []; for ($i=0; $i < strlen($s); $i++) { if(in_array($s[$i],$left)){ array_push($stack,$s[$i]); }else{ if(!$stack){ return false; } $top = array_pop($stack); if($s[$i] == '}' && $top != '{' ){ return false; }else if($s[$i] == ')' && $top != '('){ return false; }elseif ($s[$i] == ']' && $top != '[') { return false; } } } if(!$stack){ return true; } return false; }
队列 Queue
队列也是一种线性结构，相比数组，队列对应的操作是数组的子集，队列只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。
队列是一种先进先出的数据结构（First In First Out）
链表
链表和数组的对比
- 数组最好用于索引有语义的情况
- 最大优点：支持快速查询
- 链表不适合用于索引有语义的情况
- 最大优点是：动态
PHP实现链表
https://juejin.im/post/5af0f46c6fb9a07ace58ce98
B树
B+树
B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有底层的叶子节点（文件）保存数据，非叶子节点只保存索引）。
B+树的性质
- 非叶子结点的子树指针与关键字个数相同
- 非叶子结点的子树指针p[i]指向关键字值属于[k[i],k[i+1]]的子树。（B树是开区间，也就是说B树不允许关键字重复，B+树运行重复）
- 为所有叶子节点增加一个链指针。
- 所有关键字都在叶子节点出现构成链表（且链表是有序的）