golang中用slice实现queue

劫客轮蹲 · · 1857 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

实现一

最直观的实现，用一个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交换，底层的数组空间可以重用，从而节省内存空间。