队列

• 队列是一个有序列表，可以用数组和链表实现。
• 队列遵循先进先出的原则。

普通队列

数组实现

package queue

import (
	"errors"
	"fmt"
)

// queue
// 数组实现的队列

// Queue 使用一个结构体来管理队列
type Queue struct {
	 maxSize int
	 array []any // 存放队列数据 any=interface{}的别名
	 front int //队头
	 rear int //队尾
}

// NewQueue 初始化队列
func (queue *Queue) NewQueue(maxSize int) *Queue {

	queue.maxSize  = maxSize
	queue.array = make([]any,queue.maxSize)
	queue.front = -1
	queue.rear = -1
	return queue
}

// Add 添加数据
func (queue *Queue) Add(i interface{}) (err error)  {
	
	// 先判断队列是否满了
	// 当队尾 rear == maxSize-1 的时候 说明队列装满了
	if queue.rear == queue.maxSize-1 {
		fmt.Println(queue.maxSize-1)
		return errors.New("队列满了")
	}

	// 队尾指针后移
	queue.rear++
	// 添加数据
	queue.array[queue.rear] = i

	return 
}

// Get 取出数据
func (queue *Queue) Get() interface{}{
	// 要取数据，先判断是否有数据
	if queue.rear == queue.front{
		return errors.New("没有数据")
	}
	// 取完数据  对头后移
	queue.front++

	return queue.array[queue.front]
}

// Show 遍历队列
func (queue *Queue) Show()  {
	if queue.rear == queue.front {
		fmt.Println("队列为空")
		return
	}
	for  _,v := range queue.array {
		fmt.Printf("%v\n",v)
	}
}

普通队列带来的问题

环形队列

环形队列详解

初始化一个数组大小为6的环形队列, 头指针front=0, 尾指针rear=0, 刚好front=rear =0的状态,表示环形队列为空.

向环形队列里插入1个元素,则rear指针移动一格,front=0,rear=1

如果把最后一个元素装满，则会导致rear= 6 ，大于数组大小,发生数组溢出.

处理的方法：

当rear=6时与数组大小6进行取模, (rear+1) % maxLen,让rear指针回到开始处rear=0,问题来了,我 们无法判断数组是否满?因为初始化时front=rear=0, 现在数组满也是front=rear=0

上述问题有3种方发处理：

1. 使用一个标记变量，标记数组是否满了
2. 使用一个len变量，每次添加则++
3. 少用一个位置

第三种方法的实现：

当(rear+1) % maxLen == front时,判断环形数组满,则无法添加元素，代价是直接跳过一个位置

当取完值后 0空出来了，在进行入队 此时front = 1 rear = 5 ， (5+1) % 6 = 0 != 1,会直接在5的位置入队，

并将rear = (rear +1) % maxLen , rear = (5+1) % 6 = 0 下次就会在 0 的位置入队

具体实现

• front 和 raer都指向队列的第一个元素，初始值为 0
• 当队列满时：（rear+1）%length==front
• 当队列为空时：rear==front
• 当前队列元素有效个数：（rear+length-front）%length
• 队列新增：rear = (rear+1)%length
• 出队：front = (front +1) % length

package queue

import (
	"fmt"
	"log"
)

// CircleQueue 环形队列
type CircleQueue struct {
	length	int //长度
	front int //队头
	rear int // 队尾
	arr []interface{} // 数组-> 存放队列数据
}

// New 构造函数
func New(length int) *CircleQueue {
	return &CircleQueue{
		length: length,
		arr:    make([]any,length),
	}
}

// IsEmpty 队列是否为空
func (c *CircleQueue) IsEmpty() bool  {
	//front == rear == 0为空
	return c.front == c.rear
}

// IsFull 队列是否已满
func (c *CircleQueue) IsFull() bool  {
	return c.front == (c.rear +1)% c.length
}

// 队列长度
func (c *CircleQueue) len()int  {
	return (c.rear - c.front) % c.length
}
// Add 队尾新增元素
func (c *CircleQueue) Add(val any) {
	// 判断是否已满
	if c.IsFull(){
		fmt.Printf("添加%v失败,队列满了,请先清理\n",val)
		return
	}
	c.arr[c.rear] = val  //crr[5]
	// 将rear后移
	c.rear  = (c.rear+1)%c.length
}

// Get 元素出队列
func (c *CircleQueue) Get() any{
	// 是否nil队列
	if c.IsEmpty(){
		log.Fatalln("队列空的")
	}
	// 元素取出之后 指针后移
	val := c.arr[c.front]
	c.front = (c.front +1) % c.length
	return val
}

// Size 当前队列有效数据个数
func (c *CircleQueue) Size() int  {
	return (c.rear + c.length - c.front) %c.length
}

// Show 打印队列所有元素
func (c *CircleQueue) Show()  {
	if c.IsEmpty() {
		fmt.Println("queue is empty")
		return
	}
	for i := c.front; i < c.front + c.Size(); i++ {
		fmt.Println(c.arr[i%c.length], "\t")
	}
}

// Clear 清空
func (c *CircleQueue) Clear()  {
	c.arr = make([]any,c.length)
	c.front = 0
	c.rear = 0
}