go 环形队列

solate

发布于 2022-06-12 06:44:45

1.1K00

代码可运行

文章被收录于专栏：solate 杂货铺solate 杂货铺

运行总次数：0

代码可运行

环形队列

队列又称为“先进先出”(FIFO)线性表，限定只能在队尾插入，在队首删除

顺序队列：顺序存储结构，数组
链队列：链表结构。

内存上并没有环形的结构，因此环形队列实际上是数组的线性空间来实现的。

当数据到了尾部该如何处理呢？它将转回到原来位置进行处理，通过取模操作来实现

golang环形队列实现

什么是环形队列

如图所示,一个环形队列.含有二个指针: 队列头指针,队列尾指针.

实现环形队列图示过程

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

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

3.继续添加a2,a3,a4,a5元素,rear指针指到末尾处,front=0, reat=5

4.如果再继续添加a6元素,则rear=6,大于数组大小,发生数组溢出.

5.如上图所示添加a6时,rear指针发生溢出.我们使用一个小技巧,当rear=6时与数组大小6进行取模, (rear+1) % maxLen,让rear指针回到开始处rear=0,问题来了,我们无法判断数组是否满?因为初始化时front=rear=0, 现在数组满也是front=rear=0

6.解决以上问题有三种办法,我们采用第3种方法实现.

使用第3种方法: 即当(rear+1) % maxLen == front时,判断环形数组满,则无法添加元素

实现

package circleQueue

import (
	"errors"
)

// 环形队列
type CircleQueue struct {
	length int   // 队列长度
	head   int   // 指向队列首 0
	tail   int   // 指向队列尾 0
	data   []any // 数组 => 模拟队列
}

func New(length int) *CircleQueue {
	return &CircleQueue{
		length: length,
		data:   make([]any, length),
	}
}

// 队列是否为空
func (s *CircleQueue) IsEmpty() bool {
	return s.head == s.tail
}

// 队列是否已经满了, 采用空一格的方式
func (s *CircleQueue) IsFull() (res bool) {
	return s.head == (s.tail+1)%s.length
}

// 环形队列长度
func (s *CircleQueue) Len() (res int) {
	return (s.tail - s.head + s.length) % s.length
}

// 队列尾新增元素
func (s *CircleQueue) Push(val any) (b error) {
	if s.IsFull() {
		return errors.New("队列已满！")
	}
	s.data[s.tail] = val
	s.tail = (s.tail + 1) % s.length
	return
}

// 队列头弹出元素
func (s *CircleQueue) Pop() (val any, err error) {
	if s.IsEmpty() {
		return nil, errors.New("队列为空！")
	}
	val = s.data[s.head]
	s.head = (s.head + 1) % s.length
	return
}

func (s *CircleQueue) Each(fn func(node any)) {
	for i := s.head; i < s.tail+s.length; i++ {
		fn(s.data[i%s.length])
	}
}

// 清空
func (s *CircleQueue) Clear() {
	s.head = 0
	s.tail = 0
	s.data = make([]any, s.length)
}

测试

package circleQueue

import (
	"fmt"
	"testing"
)

func TestNew(t *testing.T) {

	queue := New(5)
	err := queue.Push(1)
	err = queue.Push(2)
	err = queue.Push(3)
	err = queue.Push(4)
	if err != nil {
		t.Error(err)
	}
	err = queue.Push(5)
	if err != nil {
		t.Error(err)
	}

	fn := func(node any) {
		fmt.Println(node)
	}
	queue.Each(fn)

	t.Log("Push End: ")
	val, err := queue.Pop()
	if err != nil {
		t.Error(err)
		return
	}
	t.Log(val)
	t.Log("Pop End: ")

	err = queue.Push(6)
	if err != nil {
		t.Error(err)
	}
	t.Log("Len: ", queue.Len())
	t.Log("Each End: ")

	queue.Pop()
	queue.Pop()
	t.Log("Len: ", queue.Len())
	queue.Push(7)
	queue.Push(8)
	t.Log("Len: ", queue.Len())

	queue.Clear()
	t.Log("Clear End: ")
	t.Log("Len: ", queue.Len())

}