队列

定义

// 线性表的一种，构造上两端都是凋谢的
// 容许删除的一端，称为队首
// 容许插入的一端，称为队尾

// 依据定义写出队列的结构构造体(假设队列中都是整型元素)
type Queue struct {
    // 寄存队列元素的容器
    container []int
    // 队首标记
    front int
    // 队尾标记
    tail int
    // 容量限度
    size int
}

// 依据构造体写出队列的构造方法
func NewQueue(size int) *Queue{
    return &Queue{container: make([]int, size)
        front: 0,
        tail: 0,
        // size 不为 font-tail
        // 是为了不便循环队列判空、满操作
        size: 0,
    }
}

循环队列的个性

因为队首、尾永远在 [0, size-1] 之间打转，所以切片的长度在超过默认 size 后就不会再动静增长啦

基本操作

队列判空：队列 size 为 0
队列判满：队列 size 等于 len(container)
入队：队尾插入 data 后，队尾标记加一并对 len(container)取余
出队：取出队首元素后，队首标记加一并对 len(container)取余

// 队列判空
func (q *Queue) IsEmpty() bool {
    if q.size == 0{return true}else{return false}
}

// 队列判满
func (q *Queue) IsFull() bool {if q.size == len(q.container){return true}else{return false}
}

// 入队
func (q *Queue) EnQueue(data int) bool {if q.IsFull(){return false}else{q.container[q.tail] = data
        q.tail = (q.tail + 1)%len(q.container)
        q.size++
        return true
    }
}

// 出队
func (q *Queue) DeQueue() (flag bool, ret int) {if q.IsEmpty(){return false,ret}else{ret = q.container[q.front]
        q.front = (q.front + 1)%len(q.container)
        q.size--
        return true,ret
    }
}

测试

func main(){c := CircleQueue(6)
    c.EnQueue(1)
    c.EnQueue(2)
    c.EnQueue(3)
    c.EnQueue(4)
    c.EnQueue(5)
    c.EnQueue(6)
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
    c.EnQueue(1)
    c.EnQueue(2)
    fmt.Println(c.DeQueue())
    fmt.Println(c.DeQueue())
}

// 运行后果
true 1
true 2
true 3
true 4
true 5
true 6
false 0
false 0
true 1
true 2