队列

数组模拟队列(单向)

1. 队列三个要素, head,指向队列头; tail, 指向队列尾; maxCap, 队列总容量。
2. 队列初始化的时候, head和tail都指向-1位置。
3. 对于head而言, 指向的位置为弹出的元素. 在弹出的时候,head先+1, 再弹出head此时指向的元素。
4. 对于tail而言, 指向的位置为队尾. 在压入元素的时候, tail先+1, 再放入元素。
5. 当head == tail的时候, 说明队列为空。
6. 当tail == maxCap-1的时候, 说明队列已满, 之所以要-1 是因为下标是从0开始的。
7. 数组单向队列, 压入元素的时候会占用一个位置,当占满后,即便弹出元素,也无法释放空间。
8. 所有的弹出都是伪弹出, 因为随着head的移动, 当查看队列内容的时候, 只是查看head到tail区间的元素。
9. 单向队列, 当存储满之后, 哪怕取出数据也无法再往里塞入数据。

go代码实现数组模拟单向队列

package main

import "fmt"

/*

 */
type Queue struct {
	head int
	tail int
	maxCap int
	array [4]int
}

func (q *Queue) isFull() bool {
	// q.tail为下标，队列最大容量需要 - 1
	if q.tail == q.maxCap - 1 {
		fmt.Println("队列已满")
		return false
	}
	return true
}

func (q *Queue) isEmpty() bool {
	if q.head == q.tail {
		fmt.Println("队列为空")
		return false
	}
	return true
}


func (q *Queue) pushQueue(value int) {
	// 先判断队列是否满 true为不满
	if q.isFull() {
		q.tail += 1
		q.array[q.tail] = value
	}
}

func (q *Queue) popQueue() {
	// 先判断队列是否为空 true为不空
	if q.isEmpty() {
		q.head += 1
		fmt.Println("弹出元素为")
		fmt.Println(q.array[q.head])
	}
}

func (q *Queue) showQueue() {
	// 获取从head+1到tail+1位切片, 所以需要从head+1号位进行遍历到tail的位置。
	// 需要判断是否为空
	if q.isEmpty() {
		// 因为被head指向的元素是已经被视为弹出了,所以要从head的下一位开始算.
		tmpHead := q.head + 1
		for i:=tmpHead; i<=q.tail;i++ {
			fmt.Println(q.array[i])
		}
	} else {
		fmt.Println("空队列")
	}
}

func main() {
	Q := &Queue{
		head:-1,
		tail:-1,
		maxCap:4,
	}
	Q.pushQueue(1)
	Q.pushQueue(2)
	Q.pushQueue(3)
	Q.pushQueue(3)
	Q.pushQueue(4)
	Q.popQueue()
	Q.showQueue()
}

环形队列

1. 环形队列克服了单向队列的问题，只要数据被取出，就可以一直被填充新数据。
2. 环形队列其实也是数组实现的，只是当数据填入队尾后，使用取模的方式，重新将tail移动至队头。
3. 一般情况下，比如单向队列，填充数据，队尾+1，也就是tail+1, 当队列非空的时候，tail的角标一定大于队头head的角标，但环形数组不同，因为tail会产生移动到队头的情况，所以存在head的角标大于tail角标的情况。但无论如何，tail和head相等的情况有且只会产生两次，一次是空队列的时候，还有一次是队列满的时候。
4. 正因为存在当tail和head相等的时候有两种不确定性，所以我们可以在塞入数据后，限制tail追赶且跟head平齐，预留一个空位的方式，当tail+1除以队列长度，如果等于head，则表示队列满，这种情况，队列的可用度为队列长度-1。
5. 那么tail和head相等的情况只会发生在队列为空的时候，此时的相等是tail被head追赶并平齐了。
6. tail和head的起始位置角标都为0。
7. 如果要计算当前队列长度，如果是单向队列，那么只需要获取head至tail位置的内容即可，但环形队列存在重置队头的情况，队列长度为(tail+队列长度-head) % 队列长度。
8. 为什么用这个长度算法公式？因为存在tail重置队头的情况，直接tail加上队列长度则假定每次都重置队头，最后除以队列长度，则是获取真实长度。
9. 每次塞入数据，都是先塞入，然后(tail+1) % 队列长度； 同样，每次取出数据，都是先取出，然后(head+1) % 队列长度，两者都需要取模，防止溢出。

go代码实现环形队列

package main

import (
	"fmt"
	"errors"
)

// 声明队列结构体, 四个要素, 长度, head, tail, 数组
type queue struct {
	head int
	tail int
	array [4]int
	maxCap int
}


func (q *queue) isFull() bool {
	// 判断队列是否满
	if (q.tail + 1) % q.maxCap == q.head {
		fmt.Println("队列已满")
		return true
	}
	return false
}

func (q *queue) isEmpty() bool {
	// 判断队伍是否为空
	if q.tail == q.head {
		fmt.Println("队列为空")
		return true
	}
	return false
}

func (q *queue) pushQueue(value int)  {

	if q.isFull() {
		fmt.Println("队列满了")
		//// 此时队列满了, 需要取模后重新开始
		//q.tail = (q.tail + 1) % q.maxCap
		//q.array[q.tail] = value
		//q.tail += 1
	} else {
		q.array[q.tail] = value
		// 自增因为存在循环情况, 所以要取模才不会溢出
		q.tail = (q.tail + 1) % q.maxCap
	}


}

func (q *queue) popQueue() error{
	// 弹出之前先判断数组是否为空
	if q.isEmpty() {
		fmt.Println("队列为空")
		return errors.New("队列为空")
	}

	val := q.array[q.head]
	// 自增因为存在循环情况, 所以要取模才不会溢出
	q.head = (q.head + 1) % q.maxCap

	fmt.Printf("弹出了%v\n", val)
	return nil

}

func (q *queue) showQueue() {
	// 因为可能tail会进行下一轮,导致tail的下标比head小, 所以要先得到队列中当前有多少个元素, 那么以head为起点, 循环这些元素个数次数, 则就是队列总的元素内容了
	count := (q.tail + q.maxCap - q.head) % q.maxCap
	if count == 0 {
		fmt.Println("当前为空队列")
		return
	}
	tempHead := q.head
	// 循环元素个数的次数, 因为i的起始值为0, 如果count是5, 那么其实是0,1,2,3,4 所以是i<count,而非i<=count
	for i:=0 ; i<count; i++ {
		fmt.Printf("q.array[%v], 值为%v\n", tempHead, q.array[tempHead])
		// 然后tempHead +1, 但因为是循环, 到了最大空间后, 又从第一个元素开始, 所以要取模
		tempHead = (tempHead + 1) % q.maxCap
	}
}

func main() {
	Q := &queue{
		head:0,
		tail:0,
		maxCap:4,
	}
	Q.pushQueue(4)
	Q.pushQueue(5)
	Q.pushQueue(3)
	fmt.Println("push 4, 5, 3后为")
	Q.showQueue()

	Q.popQueue()
	Q.popQueue()
	fmt.Println("pop两次后为")
	Q.showQueue()

}