双端队列

基础与数据结构

说明

两端都能插入和取出；下面用固定容量的环形缓冲区实现。

分析

环形缓冲区把逻辑位置映射到固定长度数组，front 左移即可在头部插入。尾部下标由 front 与 size 计算，两个方向都不必搬动已有元素。

容量4、front初始为0时，头插7会回绕至槽3；size=1，尾删下标为(3+1-1)%4，仍是槽3。逻辑顺序由front和size共同决定，满时继续头插会覆盖有效数据。

查看图表代码

适用前提与边界

这个示例要求容量大于零且未满；实际容器还需处理扩容和空队列。 容量必须为正；PushFront要求size小于容量，PopBack要求size大于0，示例没有实现这些检查。

示例输入与调用

deque := NewDeque(4)
	deque.PushFront(7)
	fmt.Println(deque.PopBack())

运行输出

7

完整 Go 示例

package main

import "fmt"

type Deque struct {
	a           []int
	front, size int
}

func NewDeque(capacity int) *Deque {
	return &Deque{a: make([]int, capacity)}
}
func (d *Deque) PushFront(x int) {
	d.front = (d.front - 1 + len(d.a)) % len(d.a)
	d.a[d.front] = x
	d.size++
}
func (d *Deque) PopBack() int {
	i := (d.front + d.size - 1) % len(d.a)
	d.size--
	return d.a[i]
}

func main() {
	deque := NewDeque(4)
	deque.PushFront(7)
	fmt.Println(deque.PopBack())
}