数据结构

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

二叉树

平衡二叉树(AVL树)

红黑树