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) 複雜度內回傳鍊錶的節點數量(長度);