跳到主要内容

Deque

Deque 是双端队列，可以在队头和队尾进行插入、删除操作。Go 标准库没有直接提供 deque 类型，常见做法是基于切片封装一个轻量结构。

基础实现​

package deque

type Deque[T any] struct {
 items []T
}

func New[T any]() *Deque[T] {
 return &Deque[T]{}
}

func (d *Deque[T]) Len() int {
 return len(d.items)
}

func (d *Deque[T]) Empty() bool {
 return len(d.items) == 0
}

func (d *Deque[T]) PushFront(v T) {
 d.items = append([]T{v}, d.items...)
}

func (d *Deque[T]) PushBack(v T) {
 d.items = append(d.items, v)
}

func (d *Deque[T]) PopFront() (T, bool) {
 var zero T
 if d.Empty() {
  return zero, false
 }

 v := d.items[0]
 d.items[0] = zero
 d.items = d.items[1:]
 return v, true
}

func (d *Deque[T]) PopBack() (T, bool) {
 var zero T
 if d.Empty() {
  return zero, false
 }

 last := len(d.items) - 1
 v := d.items[last]
 d.items[last] = zero
 d.items = d.items[:last]
 return v, true
}

使用示例​

q := deque.New[int]()
q.PushBack(1)
q.PushFront(0)
q.PushBack(2)

front, _ := q.PopFront() // 0
back, _ := q.PopBack()   // 2

注意点​

  • PushFront 使用 append([]T{v}, d.items...) 会移动已有元素，数据量大时成本较高。
  • 高频队头插入删除可以使用环形数组实现，减少元素搬移。
  • PopFront 和 PopBack 中把移除位置置零，可以帮助 GC 回收引用类型元素。