class deque{ public $queue = array(); public $length = 0; public function rpop(){ $node = array_pop($this->queue); $this->countque(); return $node; } public function rpush($node){ array_push($this->queue, $node); $this->countque(); return $this->queue; } public function lpop(){ $node = array_shift($this->queue); $this->countque(); return $node; } public function lpush($node){ array_unshift($this->queue, $node); $this->countque(); return $this->queue; } private function countque(){ $this->length = count($this->queue); } }
Redis 实现了自己的双端链表结构。
•双端链表主要有两个作用: ◦作为 Redis 列表类型的底层实现之一;
◦作为通用数据结构,被其他功能模块所使用;
•双端链表及其节点的性能特性如下: ◦节点带有前驱和后继指针,访问前驱节点和后继节点的复杂度为 O(1) ,并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行;
◦链表带有指向表头和表尾的指针,因此对表头和表尾进行处理的复杂度为 O(1) ;
◦链表带有记录节点数量的属性,所以可以在 O(1) 复杂度内返回链表的节点数量(长度);