实现一
最直观的实现,用一个slice。
type Queue struct {
s []*valueType
}
func (q *Queue) pushBack(v *valueType) {
s = append(s, v)
}
func (q *Queue) popFront() *valueType {
if len(s) == 0 {
return nil
}
v := s[0]
s[0] = nil
s = s[1:]
return v
}
这有个问题,Queue中的slice所占的内存并不会随着popFront操作而释放,已经出队的元素所占的内存仍在slice底层的数组中保留,内存占用会越来越多。
实现二
用两个slice构造一个queue,在go net.http.transport包中有个wantConnQueue的实现,看注释是参考了Okasaki's purely functional queue.
// A wantConnQueue is a queue of wantConns.
type wantConnQueue struct {
// This is a queue, not a deque.
// It is split into two stages - head[headPos:] and tail.
// popFront is trivial (headPos++) on the first stage, and
// pushBack is trivial (append) on the second stage.
// If the first stage is empty, popFront can swap the
// first and second stages to remedy the situation.
//
// This two-stage split is analogous to the use of two lists
// in Okasaki's purely functional queue but without the
// overhead of reversing the list when swapping stages.
head []*wantConn
headPos int
tail []*wantConn
}
// len returns the number of items in the queue.
func (q *wantConnQueue) len() int {
return len(q.head) - q.headPos + len(q.tail)
}
// pushBack adds w to the back of the queue.
func (q *wantConnQueue) pushBack(w *wantConn) {
q.tail = append(q.tail, w)
}
// popFront removes and returns the wantConn at the front of the queue.
func (q *wantConnQueue) popFront() *wantConn {
if q.headPos >= len(q.head) {
if len(q.tail) == 0 {
return nil
}
// Pick up tail as new head, clear tail.
q.head, q.headPos, q.tail = q.tail, 0, q.head[:0]
}
w := q.head[q.headPos]
q.head[q.headPos] = nil
q.headPos++
return w
}
// peekFront returns the wantConn at the front of the queue without removing it.
func (q *wantConnQueue) peekFront() *wantConn {
if q.headPos < len(q.head) {
return q.head[q.headPos]
}
if len(q.tail) > 0 {
return q.tail[0]
}
return nil
}
// cleanFront pops any wantConns that are no longer waiting from the head of the
// queue, reporting whether any were popped.
func (q *wantConnQueue) cleanFront() (cleaned bool) {
for {
w := q.peekFront()
if w == nil || w.waiting() {
return cleaned
}
q.popFront()
cleaned = true
}
}
入队的时候,append到tail中。出队的时候,从head[headPos]中取第一个元素,如果head空了,就交换head和tail。这样head slice为空的时候,与tail slice交换,底层的数组空间可以重用,从而节省内存空间。
reference
有疑问加站长微信联系(非本文作者)