（3）Go实现循环队列

队列的实现方法2，循环队列

循环队列实现思路：
1.循环队列须要几个參数来确定
  front，tail，length，capacity
  front指向队列的第一个元素，tail指向队列最后一个元素的下一个位置
  length表示当前队列的长度，capacity标示队列最多容纳的元素
2.循环队列各个參数的含义
（1）队列初始化时，front和tail值都为零
（2）当队列不为空时，front指向队列的第一个元素，tail指向队列最后一个元素的下一个位置；
（3）当队列为空时，front与tail的值相等，但不一定为零
（4）当（tail+1）% capacity == front ||  （length+1）== capacity 表示队列为满，
    因此循环队列默认浪费1个空间
3.循环队列算法实现
（1）把值存在tail所在的位置；
（2）每插入1个元素，length+1，tail=（tail+1）% capacity
（3）每取出1个元素，length-1，front=（front+1）% capacity
（4）扩容功能，当队列容量满，即length+1==capacity时，capacity扩大为原来的2倍
（5）缩容功能，当队列长度小于容量的1/4，即length<=capacity/4时，capacity缩短为原来的一半

// 循环队列实现方法
type loopQueue struct {
    queues   []interface{}
    front    int //队首
    tail     int //队尾
    length   int //队伍长度
    capacity int //队伍容量
}

func NewLoopQueue() *loopQueue {
    loop := &loopQueue{
        queues:   make([]interface{}, 0, 2),
        front:    0,
        tail:     0,
        length:   0,
        capacity: 2,
    }
    //初始化队列
    for i := 0; i < 2; i++ {
        loop.queues = append(loop.queues, "")
    }
    return loop
}

func (q *loopQueue) Len() int {
    return q.length
}

func (q *loopQueue) Cap() int {
    return q.capacity
}

func (q *loopQueue) IsEmpty() bool {
    return q.length == 0
}

func (q *loopQueue) IsFull() bool {
    return (q.length + 1) == q.capacity
}

func (q *loopQueue) GetFront() (interface{}, error) {
    if q.Len() == 0 {
        return nil, errors.New(
            "failed to getFront,queues is empty.")
    }
    return q.queues[q.front], nil
}

func (q *loopQueue) Enqueue(elem interface{}) {
    // 队列扩容
    if q.IsFull() {
        buffer := new(loopQueue)
        //初始化队列
        for i := 0; i < 2*q.capacity; i++ {
            buffer.queues = append(buffer.queues, "")
        }
        for i := 0; i < q.length; i++ {
            buffer.queues[i] = q.queues[q.front]
            q.front = (q.front + 1) % q.capacity
        }
        q.queues = buffer.queues
        q.front = 0
        q.tail = q.length
        q.capacity = 2 * q.capacity
    }

    q.queues[q.tail] = elem
    q.tail = (q.tail + 1) % q.capacity
    q.length++
}

func (q *loopQueue) Dequeue() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New(
            "failed to dequeue,queues is empty.")
    }

    // 当队列长度小于容量1/4时，队列容量缩短一半
    if q.length <= q.capacity/4 {
        buffer := new(loopQueue)
        //初始化队列
        for i := 0; i < q.capacity/2; i++ {
            buffer.queues = append(buffer.queues, "")
        }
        for i := 0; i < q.length; i++ {
            buffer.queues[i] = q.queues[q.front]
            q.front = (q.front + 1) % q.capacity
        }
        q.queues = buffer.queues
        q.front = 0
        q.tail = q.length
        q.capacity = q.capacity / 2
    }

    queue := q.queues[q.front]
    q.front = (q.front + 1) % q.capacity
    q.length--
    return queue, nil
}

// 测试队列
func main() {
    q := queue4.NewLoopQueue()

    for i := 0; i < 5; i++ {
        q.Enqueue(fmt.Sprintln(strconv.Itoa(i) + "--world "))
    }

    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, getFront=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.GetFront()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, dequeue=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.Dequeue()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, dequeue=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.Dequeue()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, dequeue=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.Dequeue()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, dequeue=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.Dequeue()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, dequeue=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.Dequeue()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, dequeue=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.Dequeue()))
    fmt.Printf("isEmpty:%v, isFull:%v, len=%v, cap=%v, getFront=%v\n",
        q.IsEmpty(), q.IsFull(), q.Len(), q.Cap(), fmt.Sprintln(q.GetFront()))
}

// 测试结果
isEmpty:false, isFull:false, len=5, cap=8, getFront=0--world  <nil>
isEmpty:false, isFull:false, len=5, cap=8, dequeue=0--world  <nil>
isEmpty:false, isFull:false, len=4, cap=8, dequeue=1--world  <nil>
isEmpty:false, isFull:false, len=3, cap=8, dequeue=2--world  <nil>
isEmpty:false, isFull:false, len=2, cap=8, dequeue=3--world  <nil>
isEmpty:false, isFull:false, len=1, cap=4, dequeue=4--world  <nil>
isEmpty:true, isFull:false, len=0, cap=2, dequeue=<nil> failed to dequeue,queues is empty.
isEmpty:true, isFull:false, len=0, cap=2, getFront=<nil> failed to getFront,queues is empty.

顺序队列取出元素的时间复杂度为O(n)，循环队列取出元素的时间复杂度为O(1)，相对快很多
该实现方法的缺陷是每次扩容缩容，都要给队列初始化capacity数量的元素，一开始初始化较大的空间，并把缩容功能去掉，能一定程度上加快速度，不过应该还有更好的实现方法..

下面地址，用链表实现队列
https://www.jianshu.com/p/6cb6798ecef0