func (d *Deque) PopFront() (interface{}, bool) {
	if d.len == 0 {
		return nil, false
	}
	vp := &d.head.v[d.hp]
	v := *vp
	*vp = nil  
	d.len--
	switch {
	case d.hp < d.hlp:
		d.hp++
	case d.head == d.tail:
		d.tp = d.hp
	case d.spareLinks >= maxSpareLinks:
		d.hp = 0
		d.head.p.n = d.head.n
		d.head.n.p = d.head.p
		d.head = d.head.n
		d.hlp = len(d.head.v) - 1
	default:
		d.hp = 0
		d.head = d.head.n
		d.spareLinks++
		d.hlp = len(d.head.v) - 1
	}
	return v, true
}
PopFront retrieves and removes the current element from the front of the deque.
The second, bool result indicates whether a valid value was returned;
if the deque is empty, false will be returned.
The complexity is O(1).
package deque
const (
	firstSliceSize = 4
	sliceGrowthFactor = 4
	maxFirstSliceSize = 64
	maxInternalSliceSize = 256
	maxSpareLinks = 5
)
type Deque struct {
	head *node
	tail *node
	hp int
	hlp int
	tp int
	len int
	spareLinks int
}
type node struct {
	v []interface{}
	n *node
	p *node
}
func New() *Deque {
	return new(Deque)
}
func (d *Deque) Init() *Deque {
	*d = Deque{}
	return d
}
func (d *Deque) Len() int { return d.len }
func (d *Deque) Front() (interface{}, bool) {
	if d.len == 0 {
		return nil, false
	}
	return d.head.v[d.hp], true
}
func (d *Deque) Back() (interface{}, bool) {
	if d.len == 0 {
		return nil, false
	}
	return d.tail.v[d.tp-1], true
}
func (d *Deque) PushFront(v interface{}) {
	switch {
	case d.head == nil:
		h := &node{v: make([]interface{}, firstSliceSize)}
		h.n = h
		h.p = h
		d.head = h
		d.tail = h
		d.tp = firstSliceSize
		d.hp = firstSliceSize - 1
		d.hlp = d.hp
	case d.hp > 0:
		d.hp--
	case d.head.p != d.tail:
		d.head = d.head.p
		d.hp = len(d.head.v) - 1
		d.hlp = d.hp
		d.spareLinks--
		if d.len == 0 {
			d.tail = d.head
			d.tp = len(d.head.v)
		}
	case len(d.head.v) < maxFirstSliceSize:
		l := len(d.head.v)
		nl := l * sliceGrowthFactor
		n := make([]interface{}, nl)
		diff := nl - l
		d.tp += diff
		d.hp += diff
		d.hlp = nl - 1
		copy(n[d.hp:], d.head.v)
		d.head.v = n
		d.hp--
	case d.len == 0:
		d.tail = d.head
		d.tp = len(d.head.v)
		d.hp = d.tp - 1
		d.hlp = d.hp
	default:
		n := &node{v: make([]interface{}, maxInternalSliceSize)}
		n.n = d.head
		n.p = d.tail
		d.head.p = n
		d.tail.n = n
		d.head = n
		d.hp = maxInternalSliceSize - 1
		d.hlp = d.hp
	}
	d.len++
	d.head.v[d.hp] = v
}
func (d *Deque) PushBack(v interface{}) {
	switch {
	case d.head == nil:
		h := &node{v: make([]interface{}, firstSliceSize)}
		h.n = h
		h.p = h
		d.head = h
		d.tail = h
		d.tail.v[0] = v
		d.hlp = firstSliceSize - 1
		d.tp = 1
	case d.tp < len(d.tail.v):
		d.tail.v[d.tp] = v
		d.tp++
	case d.tp < maxFirstSliceSize:
		nv := make([]interface{}, len(d.tail.v)*sliceGrowthFactor)
		copy(nv, d.tail.v)
		d.tail.v = nv
		d.tail.v[d.tp] = v
		d.tp++
		d.hlp = len(nv) - 1
	case d.tail.n != d.head:
		d.spareLinks--
		n := d.tail.n
		d.tail = n
		d.tail.v[0] = v
		d.tp = 1
	default:
		n := &node{v: make([]interface{}, maxInternalSliceSize)}
		n.n = d.head
		n.p = d.tail
		d.tail.n = n
		d.head.p = n
		d.tail = n
		d.tail.v[0] = v
		d.tp = 1
	}
	d.len++
}