想了解一起学习PHP中的DS数据结构扩展的新动态吗？本文将为您提供详细的信息，我们还将为您解答关于二的相关问题，此外，我们还将为您介绍关于ES6+数据结构扩展、js数据结构——链表（二）、js数据结构

想了解一起学习PHP中的DS数据结构扩展的新动态吗？本文将为您提供详细的信息，我们还将为您解答关于二的相关问题，此外，我们还将为您介绍关于ES6+ 数据结构扩展、js数据结构——链表（二）、js数据结构和算法（二）栈和队列、OA信用盘源码控杀-PHP 的数据结构扩展的新知识。

• 一起学习PHP中的DS数据结构扩展（二）（php dsl）
• ES6+ 数据结构扩展
• js数据结构——链表（二）
• js数据结构和算法（二）栈和队列
• OA信用盘源码控杀-PHP 的数据结构扩展

一起学习PHP中的DS数据结构扩展（二）（php dsl）

上文中我们学习了 DS 扩展中一些比较常用的数据结构，也留下了一些伏笔，比如 Map 中返回 keys() 和 values() 分别返回的是两种特殊的数据结构，也就是我们今天要学习的内容。

向量集合 Vector

最初见到 Vector 还是在很早的时候在 Java 中见过。不过即使是在 Java 中，这个类型的数据结构的使用也并不多，因为在 Java 中也是以 List 和 Map 为主。我们先来看看这个集合是怎么用的。

$vector = new \Ds\Vector(["a", "b", "c"]);

$vector->push("d");
$vector->push(5);
$vector->push(6);
$vector->push(7);
$vector->push(8);

$vector->set(3, "ccc");

var_dump($vector->get(3)); // string(3) "ccc"
var_dump($vector->pop()); // int(8)

$vector->unshift(1);
$vector->unshift(-1); 

var_dump($vector->shift()); // int(-1)

$vector->insert(5, 'five');
var_dump($vector->get(5)); // string(4) "five"

var_dump($vector->get(6)); // int(5)
$vector->remove(6);
var_dump($vector->get(6)); // int(6)

var_dump($vector[4]); // string(3) "ccc"

$vector[4] = 'Num 4.';

var_dump($vector[4]); // string(6) "Num 4."

var_dump($vector);
// object(Ds\Vector)#1 (8) {
//   [0]=>
//   int(1)
//   [1]=>
//   string(1) "a"
//   [2]=>
//   string(1) "b"
//   [3]=>
//   string(1) "c"
//   [4]=>
//   string(6) "Num 4."
//   [5]=>
//   string(4) "five"
//   [6]=>
//   int(6)
//   [7]=>
//   int(7)
// }

它的很多方法和 Map 都是类似的，不过它支持 push()、pop()、shift()、unshift() 这四种方法，也就是分别从尾部和头部添加和取出数据。另外在底层，它使用的总内存会少于使用数组，当分配的内存大小降到到足够低的时候会自动释放内存。对于 get()、set()、push()、pop() 这些方法的操作效率都能达到 O(1) 的水平，而对于 shift()、unshift()、insert()、remove() 这些操作则都是 O(n) 的水平。至于在什么场景下使用就很清晰了，很大的数组使用它可以节约内存，并且一些操作的效率还非常高。

在 Map 中使用 values() 和 paris() 返回的就都是 Vector 这个类型的集合。

唯一集合 Set

Set 这个集合结构其实挺常见的，不止是 Java 这些编程语言中，redis 中也有这种存储数据的方式，相信大家不会陌生。和其它结构最显著的区别就是 Set 中的值必须是唯一的。

$set = new \Ds\Set(["a", "b", "c"]);
$set->add("d");

$set->add("b");

var_dump($set);
// object(Ds\Set)#2 (4) {
//   [0]=>
//   string(1) "a"
//   [1]=>
//   string(1) "b"
//   [2]=>
//   string(1) "c"
//   [3]=>
//   string(1) "d"
// }

这个就不多做解释了，相信大家就算没有在代码中用过，也会在 redis 的使用中接触过，业务场景也非常多。在上篇文章中 Map 返回的 keys() 信息就是 Set 结构的，因为 Map 中的键是不能有重复的，包括数字下标的数组其实也都是不能有重复的键值的。

双端队列 Deque

双端队列其实在表现形式上和 Vector 差不多，同样可以在队列的头尾部进行增加取出操作，不过它有两个指针分别指向队列的头尾部，所以它的 shift() 和 unshift() 的速度也是非常快的 O(1) 级别。

$deque = new \Ds\Deque(["a", "b", "c"]);

$deque->push("d");
$deque->unshift("z");

var_dump($deque);
// object(Ds\Deque)#3 (5) {
//     [0]=>
//     string(1) "z"
//     [1]=>
//     string(1) "a"
//     [2]=>
//     string(1) "b"
//     [3]=>
//     string(1) "c"
//     [4]=>
//     string(1) "d"
//   }

var_dump($deque->pop()); // string(1) "d"
var_dump($deque->shift()); // string(1) "z"

总结

今天介绍的内容相比上篇文章简单很多，但上篇文章其实也只是测试的代码结果展示的比较多而已。整体的 DataStruct 扩展框架中的数据结构就是这些，就像最开始我们说过的，如果没有特别的需求，只是需要用到栈或队列的话，直接使用 SPL 中的就可以了。而如果有特殊的需求，比如说 Map 这种对象类型，又或者需要一个节约内存的数组，那么 Ds 中的这些数据结构想必会是你的好帮手。

测试代码：

https://github.com/zhangyue0503/dev-blog/blob/master/php/2021/02/source/3.一起学习PHP中的DS数据结构扩展（二）.php

参考文档：

https://www.php.net/manual/zh/book.ds.php

ES6+ 数据结构扩展

var set = new Set([iterable]);

// 创建一个空的 Set 实例
var set = new Set() // Set(0) {}
// 添加数据
set.add(''es6'') // Set(1) {"es6"}
// 还可以链式添加数据
set.add(''imooc'').add(''7'') // Set(3) {"es6", "imooc", "7"}
// 接受一个可遍历的对象，作为默认值，大部分情况是数组
var  set  =  new Set([, , ])
console.log(set) // Set(3) {1, 2, 3}

var map = Map([iterable]);

// 创建一个空的 Map 对象
var map1 = new Map()
map1.set(''a'', );
map1.set(''b'', );
map1.set(''c'', );
console.log(map1) // Map(3) {"a" => 1, "b" => 2, "c" => 3}

// map也可以进行链式调用
var map2 = new Map()
map2.set(''a'', ).set(''b'', ).set(''c'', )
console.log(map2) // Map(3) {"a" => 1, "b" => 2, "c" => 3}

// 接收一个二维数组，二维数组中包含两个值，key和value
var  map3  =  new Map([["x", ], ["y", ], ["z", ]]);
console.log(map3) // Map(3) {"x" => 10, "y" => 20, "z" => 30}
console.log(map1.get(''a'')) // 1
console.log(map3.get(''z'')) // 30

var set = new Set([, , , ]);
var a = [...set]
console.log(a) // [1,2,3,4]

var set = new Set([, , , ]);
Array.from(set) //输出[1,2,3,4]

var map = new Map([[''name'', ''imooc''], [{name: ''imooc''}, [''JavaScript'', ''ES6 wiki'']]]);

const map = new Map()
map.set(''name'', ''imooc'')
map.set({name: ''imooc''}, [''JavaScript'', ''ES6 wiki'']);
[...myMap]
// [[''name'', ''imooc''], [{name: ''imooc''}, [''JavaScript'', ''ES6 wiki'']]]

function objToMap(obj){
	let map = new Map();
	for (let [key, value] of Object.entries(obj)){
		map.set(key, value);
	}
	return  map;
}
objToMap({name:''imooc'', lesson: ''ES6 Wiki''})
// Map(2) {"name" => "imooc", "lesson" => "ES6 Wiki"}

function mapToObj(map){
	const obj = {}
	for (let [key, value] of map){
		obj[key] = value;
	}
	return obj;
}
const map1 = new Map()
map1.set(''name'', ''imooc'')
map1.set(''lesson'', ''ES6 Wiki'');
mapToObj(map1) // {name: "imooc", lesson: "ES6 Wiki"}

const map2 = new Map()
map2.set(''name'', ''imooc'')
map2.set({name: ''lesson''}, [''JavaScript'', ''ES6 wiki'']);
mapToObj(map2) // {name: "lesson", [object Object]: ["JavaScript", "ES6 wiki"]}

js数据结构——链表（二）

一、双向链表

双向链表和普通链表的区别在于，普通链表的节点只能指向下一个节点，而双向链表可以指向上一个节点。

1.创建双向链表（下面代码和链表（一）中代码写法不一样，只是单纯的想换种写法而已）

function DoublyLinkedList(){
   this.length = 0;
   this.head = null;    //头
   this.tail = null;    //尾
}
function Node(element){
   this.element = element;
   this.next = null;
   this.prev = null;
}

(1)节点类型要有三个属性，元素值element，访问下一个节点的属性next，访问前一节点的属性prev

(2)双向链表类型要有两个属性，头head，尾tail，用于其他操作的开始

2.在任一位置插入一个新元素

DoublyLinkedList.prototype.insert = function(position,element){
        if(position >= 0 && position <= this.length){
            var node = new Node(element),
                    current = this.head,
                    previous,
                    index = 0;
            if(position === 0){
                if(!this.head){          //如果链表为空
                    this.head = node;
                    this.tail = node;
                }else{
                    node.next = current;
                    current.prev = node;
                    this.head = node;
                }
            }else if(position === this.length){
                current = this.tail;
                current.next = node;
                node.prev = current;
                this.tail = node;
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;

                current.prev = node;
                node.prev = previous;
            }
            this.length++;
            return true;
        }else{
            return false;
        }
    };

(1)双向链表，有head和tail，因此不光要判断插入位是否0，还要判断插入位是否是末位。前者是重新赋head值，后者是重新赋tail值

(2)插入位为0时，要判断是否链表中是否有节点，无节点时，head和tail都是node节点，有节点时，node.next = current;current.prev = node;this.head = node;拼接好之后，给head赋值。

3.从任一位置移除一个元素

//从任意位置移除元素
    DoublyLinkedList.prototype.removeAt = function(position){
        //检查越界值
        if(position > -1 && position < this.length){
            var current = this.head,
                    previous,
                    index = 0;
            //移除第一项
            if(position === 0){                     //第一项
                this.head = current.next;
                if(this.length === 1){
                    this.tail = null
                }else{
                    this.head.prev = null;
                }
            }else if(position === this.length-1){    //最后一项
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = null;
            }else{
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                //将previous与current的下一项连接起来——跳过current
                previous.next = current.next;
                current.next.prev = previous;
            }
            this.length--;
            return current.element;
        }else{
            return null;
        }
    };

(1)参数：position

(2)判断移除位置是0还是末位，因为这两个点要重新赋head或tail值

 4.返回链表项

//返回链表项——正序
    DoublyLinkedList.prototype.toString = function(){
        var current = this.head,
                string = '''';
        while(current){
            string += current.element+" ";
            current = current.next;
        }
        return string;
    };
//返回链表项——逆序
    DoublyLinkedList.prototype.toStringRe = function(){
        var current = this.tail,
                string = '''';
        while(current){
            string += current.element+" ";
            current = current.prev;
        }
        return string;
    };

(1)正序，从head开始，向后遍历

(2)逆序，从tail开始，向前遍历

5.使用双向链表

  var doubleList = new DoublyLinkedList();
    doubleList.insert(0,10);
    doubleList.insert(0,15);
    doubleList.insert(0,1);
    doubleList.insert(2,8);
    console.log(doubleList.length);
    console.log(doubleList.toString());     //1 15 8 10
    doubleList.removeAt(1);
    console.log(doubleList.toStringRe());   //10 8 1
    doubleList.removeAt(0);
    doubleList.removeAt(0);
    console.log(doubleList.toString());     //10

6.循环链表

单向循环链表就是tail的next是head

双向循环链表就是head的prev指向tail，tail的next是head

js数据结构和算法（二）栈和队列

基本概念

栈和队列都是动态的集合，在栈中，可以去掉的元素是最近插入的哪一个。栈实现了后进先出。在队列中，可以去掉的元素总是在集合中存在的时间最长的那一个。队列实现了先进先出的策略。

栈的官方定义：栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。入栈使用push()方法。出栈使用pop()方法。

最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

我们把作用于队列上的INSERT操作称为入队（Enqueue），把作用于队列上的DELETE操作称为出队（Dequeue）。我们使用变量top来记录栈顶元素的位置和标记哪里可以加入新的元素，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。

栈和队列的区别

栈的插入和删除操作都是在一端进行的，而队列的操作却是在两端进行的。

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

这里定义了一个顺序存储的栈，它包含了三个元素：base,top,stackSize。

其中base是指向栈底的指针变量，top是指向栈顶的指针变量，stackSize指示栈的当前可使用的最大容量。

创建一个栈

#define STACK_INIT_SIZE 100

initStack(sqStack *s)
{
    s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
    if( !s->base )
        exit(0);

    s->top = s->base;   // 最开始，栈顶就是栈底
    s->stackSize = STACK_INIT_SIZE;
}

入栈操作

入栈操作又叫压栈操作，就是向栈中存放数据。

入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，知道栈满为止。

出栈操作

出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。

每当从栈内弹出一个数据，栈的当前容量就-1。

队列的顺序存储结构

入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。

出队列则不同，因为我们已经架设下标为0的位置是队列的队头，因此每次出队列操作所有元素都要向前移动。

栈的方法和属性

push()：入栈操作
pop()：出栈操作（返回栈顶元素并删除t）
peak()：返回栈顶元素而不删除它
clear()：清除栈内所有元素
length()：记录栈内元素的个数
empty属性：表示栈内是否含有元素

栈的实现

function Stack(){
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

用一个数组dataStore来保存栈内元素，变量top记录栈顶位置

push()方法

先来实现push()方法，当向栈中压入一个新元素时，需要将其保存在数组中变量top对应的位置，然后将top值加1：

 function push(element){
        this.dataStore[this.top++] = element;//top值加1，指向下一个空位置
    }

pop()方法

function pop(){
    return this.dataStore[--this.top];//pop方法与push相反
}

peek()方法

peek方法返回数组的第一个top-1位置的元素，即栈顶元素：

function peek(){
    return this.dataStore[this.top-1];
}

length()方法

length方法通过返回变量top值的方法返回栈内的元素的个数：

function length(){
    return this.top;
}

clear()方法

将变量top的值设为0，就可以清空一个栈了：

function clear(){
    this.top = 0;
}

OA信用盘源码控杀-PHP 的数据结构扩展

在 PHP 中表示集合的数据类型就一种：OA信用盘架设q<319.135.503.1>Array。相信每个初学 PHP 的都会对它感到疑惑。这个东西看起来应该和其他语言中的 Array 或者 List 一样，但在 PHP 中，它是一切，即是 List，也是 Map：

<?PHP
$a = array(1, 2, 3);
$b = array('key1' => 1, 'key2' => 2);
这听起来似乎很好，反正大家都使用同一种数据结构，偶尔情况下才会有些性能问题，况且升级 PHP7 之后 Array 的性能也提高了，实在不济还可以加内存。但如果我们可以通过引入更便利的数据结构优化性能，同时写代码反而更方便了，那何乐而不为呢?

Array 的缺点
有些时候我们需要保存一个集合（Set），但是 Array 并不能保证元素的唯一性，array_unique 有不可避免的性能损耗。一种折衷方案是，将元素当做 key，同时 value 为 true 来曲线实现 Unique Array 的功能：

<?PHP
$users = User::find($ids);
$res = [];
foreach ($users as $user) {
$res[$user->id] = true;
}
PHP 的 Array 访问不存在的 key 可以得到 null，不会产生 Fatal error，但会有一个 E_NOTICE。这个 E_NOTICE 会被 set_error_handler 注册的函数截获。显然，这种代码上的不干净和性能上的无谓开销完全是可以避免的。

<?PHP
$req = [];
$req['user_id']; // PHP Notice: Undefined offset
可以用 array_key_exists 和 if else 来让代码干净一些，但这样就显得啰嗦了。

array 的一些函数式方法很难用，比如 array_map, array_walk 等，写起来也很丑陋。当然这一点原生 PHP 没什么好方法，毕竟 PHP 的面向对象的基因不是很强。

<?PHP
array_map(function($user){
return $user->is_deleted();
}, $users);
// 就是这么难看
users.map { |user| user.is_deleted? }

ruby 的就好看多了

在某些情况下，使用 Array 性能很差1，比如下面这段代码：

<?PHP
$a=[1,2,3,4,5,6,7];
echo $a[5];
// 6
array_unshift($a, 0);
// $a: [0,1,2,3,4,5,6,7];
echo $a[5];
// 5
看起来似乎没什么，但需要注意的是，Array 本质上是一个 Map，unshift 一个元素进来，将会改变每个元素的 key，这是一个 $O(n)$ 操作。另外，PHP 的 Array 将其 value(包扩 key 和 它的 hash) 保存在一个 bucket 中，所以我们需要查看每一个 bucket 并更新 hash。PHP 内部其实是通过创建新的 array 来做 array_unshift 操作的，其性能问题可想可知2。

其他缺点不一而足。

PHP 数据结构插件
Array 饱受诟病，就会出现替代方案。PHP5 有spl，但是有些场景性能很差，且设计的很不好1。laravel 的 Collection 提供了更好用的 Map，但毕竟只是一种单一的数据结构，而且对 orm 操作设计了不少特有的接口，其用途受到限制。

PHP7 新增的 Data Structures 插件（简称 ds）是 PHP 下一个优秀的补充，它充分考虑了便利、安全和整洁的需求。其结构如下图所示：

PHP/PHPds.png
PHP/PHPds.png
它提供了 3 个接口类：Collection, Sequence, Hashable 和 7 个实现类（final class）：Vector, Deque, Map, Set, Stack, Queue, PriorityQueue。

接口
Collection 是基础接口，定义了一个数据集合（这里的集合指的是 Collection，不是 Set） 的基本操作，比如 foreach, json_encode, var_dump 等。

<?PHP
$sequence = new \Ds\Vector([1, 2, 3]);
json_encode($sequence);
Sequence 是类数组数据结构的基础接口，定义了很多重要且方便的方法，比如 contains, map, filter, reduce, find, first, last 等。从图中可知，Vector, Deque, Stack, Queue 都直接或者间接的实现了这个接口。

<?PHP
$sequence = new \Ds\Vector([1, 2, 3]);

print_r($sequence->map(function($value) { return $value * 2; }));
print_r($sequence);
?>
Hashable 在图中看起来比较孤立，但对于 Map 和 Set 很重要。一个 Object 如果实现了 Hashable，就可以作为 Map 的 key，可以作为 Set 的元素。这样 Map 和 Set 就能像 Java 一样方便的使用了。

实现类
Vector 应该是最为常用的数据结构之一了，可以把它当成 Ruby 的 Array 或者 Python 的 List。其元素的值的 index 就是它在 buffer 中的 index，所以效率很高。只要有使用数组的需求且不需要 insert, remove, shift 和 unshift 的都可以用它。

Deque([dek]) 是双端队列，在 Vector 的基础上增加了一个头指针，因此 shift 和 unshift 也是 $O(1)$ 复杂度了。但带来的性能损耗并不多，因此也有讨论是不是只需要一个 Deque 就够了，不需要 Vector（讨论）3。

Stack 栈，嗯没什么好说的，它继承自 Collection，但内部使用 Vector 实现。这样做的好处是实现方便，且同时可以屏蔽不需要的和不应该出现的方法。

Queue 队列，内部使用 Deque 实现。

PriorityQueue，最大堆实现。

Map。以前使用 Array 来实现 map 的地方，改用 Map 更好。二者性能几乎一致，但 Map 对内存的管理更好。而且，Map 的语法要更加友好。

<?PHP
$req = [];
$req['user_id']; // PHP Notice: Undefined offset

$req = new \Ds\Map(["a" => 1, "b" => 2, "c" => 3]);
$req->get('user_id');// OutOfBoundsException
$req->get('user_id', 0); // 0 是默认值
// 即可以方便的指定默认值，也可以选择抛出异常。不用 array，不会产生 E_NOTICE

$req->keys();

$req->map(function($key, $value) { return $value * 2; });
不仅如此，只要 object 继承了 Hashable，Map 还允许使用 object 作为 key。

<?PHP
class Photo implements \Ds\Hashable {

public function __construct($id) {
    $this->id = $id;
}

public function hash() {
    return $this->id;
}

public function equals($obj): bool {
    return $this->id === $obj->id;
}

}

$p1 = new Photo(1);
$p2 = new Photo(2);

$map = new Ds\Map();
$map->put($p1, 1);
$map->put($p2, 2);
Set 集合是一种元素唯一的数据结构。和 array_unique 相比性能有很大提升，而且用法也更加优雅1。

<?PHP
$set = new Ds\Set();
$set->add($p1);
$set->add($p2);
PHP ds 插件性能测试 ↩ ↩2 ↩3

当然，这一点可能稍嫌牵强，毕竟即使是数据量很大的情况下，array_unshift 的耗时也没有那么大 ↩

github 上还在讨论可以增加一个不可变类型 Tuple，以及取消 Vector 直接使用 Deque，讨论地址和 2.0API 计划 ↩

我们今天的关于一起学习PHP中的DS数据结构扩展和二的分享已经告一段落，感谢您的关注，如果您想了解更多关于ES6+ 数据结构扩展、js数据结构——链表（二）、js数据结构和算法（二）栈和队列、OA信用盘源码控杀-PHP 的数据结构扩展的相关信息，请在本站查询。