算法导论-单数组实现双端队列

栈插入和删除元素只能在同一端进行，队列的插入操作和删除操作分别在两端进行，与它们不同的，有一种双端队列(deque)，其插入和删除操作都可以在两端进行。写出4个时间均为O(1)的过程，分别实现在双端队列插入和删除元素的操作，该队列使用一个数组实现的。

package main

// 一个数组实现双端队列
const maxSize = 10

type Deque struct {
    leftHead  int
    rightHead int
    size      int // 记录现有元素数量
    arr       [maxSize]int
}

func (d *Deque) isEmpty() bool {
    return d.size == 0
}

func (d *Deque) isFull() bool {
    if d.size == len(d.arr) {
        return true
    }
    return false
}

func (d *Deque) pre(position int) int {
    if position == 0 {
        return len(d.arr) - 1
    }
    return position - 1
}

func (d *Deque) next(position int) int {
    if position == len(d.arr)-1 {
        return 0
    }
    return position + 1
}

func (d *Deque) LeftInsert(val int) bool {
    if d.isFull() {
        return false
    }
    if d.isEmpty() {
        d.rightHead = d.next(d.rightHead)
    }
    d.arr[d.leftHead] = val
    d.size++
    d.leftHead = d.pre(d.leftHead)
    return true
}

func (d *Deque) RightInsert(val int) bool {
    if d.isFull() {
        return false
    }
    if d.isEmpty() {
        d.leftHead = d.pre(d.leftHead)
    }
    d.arr[d.rightHead] = val
    d.size++
    d.rightHead = d.next(d.rightHead)
    return true
}

func (d *Deque) LeftDelete() (int, bool) {
    if d.isEmpty() {
        return 0, false
    }
    d.leftHead = d.next(d.leftHead)
    if d.isEmpty() {
        d.rightHead = d.pre(d.rightHead)
    }
    val := d.arr[d.leftHead]
    d.size--
    return val, true
}

func (d *Deque) RightDelete() (int, bool) {
    if d.isEmpty() {
        return 0, false
    }
    d.rightHead = d.pre(d.rightHead)
    if d.isEmpty() {
        d.leftHead = d.next(d.leftHead)
    }
    val := d.arr[d.rightHead]
    d.size--
    return val, true
}

var deque = Deque{
    leftHead:  0,
    rightHead: 0,
    arr:       [maxSize]int{},
}