队列的实现方法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
有bug欢迎指出，转载请注明出处。
网友评论