数据结构
栈 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+树运行重复)
- 为所有叶子节点增加一个链指针。
- 所有关键字都在叶子节点出现构成链表(且链表是有序的)