数据结构（一）

栈：First In Last Out，只能在一端操作的线性结构

PHP每执行函数都会开辟栈，执行完毕释放。
应用：栈实现无限级分类

// 模拟数据
$list = array(
  array('id'=>1,'name'=>"衣服",'parent_id'=>0),
  array('id'=>2,'name'=>"书籍",'parent_id'=>0),
  array('id'=>3,'name'=>"T恤",'parent_id'=>1),
  array('id'=>4,'name'=>"裤子",'parent_id'=>1),
  array('id'=>5,'name'=>"鞋子",'parent_id'=>1),
  array('id'=>6,'name'=>"皮鞋",'parent_id'=>5),
  array('id'=>7,'name'=>"运动鞋",'parent_id'=>5),
  array('id'=>8,'name'=>"耐克",'parent_id'=>7),
  array('id'=>9,'name'=>"耐克",'parent_id'=>3),
  array('id'=>10,'name'=>"鸿星尔克",'parent_id'=>7),
  array('id'=>11,'name'=>"小说",'parent_id'=>2),
  array('id'=>12,'name'=>"科幻小说",'parent_id'=>11),
  array('id'=>13,'name'=>"古典名著",'parent_id'=>11),
  array('id'=>14,'name'=>"文学",'parent_id'=>2),
  array('id'=>15,'name'=>"四书五经",'parent_id'=>14)
);


foreach(tree($list) as $row) {
    echo str_repeat(' ', $row['deep']*4), $row['name'],'<br>';
}

function tree($list)
{
    $stack = [];// 栈
    $tree = [];
    // 入栈所有的顶级分类
    foreach($list as $row) {
        if (0 == $row['parent_id']) {
            $row['deep'] = 0;// 顶级分类的深度为0
            array_push($stack, $row);
        }
    }
    //stack: 衣服 书籍
    do {
        // 出栈 一个元素,查找其子元素 
        $top = array_pop($stack);
        // stack: 衣服
        // var_dump($top); echo '<br>';
        $tree[] = $top;
        // $top 某个分类, 查找给分类的所有子类
        foreach($list as $row) {
            if ($row['parent_id'] == $top['id']) {
                // 是当前分类的子类,将其入栈
                $row['deep'] = $top['deep']+1;
                array_push($stack, $row);
            }
            // stack: 衣服 小说 文学
        }
    } while(!empty($stack));
    return $tree;

}

堆是树状结构的一种。有人常说堆栈指的是栈。

队列 First In First Out

右进左出：array_push()和array_shift()
反过来：
左进右出：array_pop()和array_unshift()

散列表，哈希表

哈希是一种算法，将某个内容经过计算得到的相同长度字符串（即摘要字符串）的算法，比如md5(),sha1()

哈希表是一种数据结构，通过某个原始字符串，经过哈希运算，得到对应值的地址，利用该地址获取数据（数据相当于在线性表）