Golang 数据结构——队列

队列是按照先进先出原则的顺序集合。从队列的一端加入元素，从另一端取出元素。
队列应用在现实中有很多场景，我们可以想象超时的结账队列或电影院的检票队列。

1. 实现

我们使用slice作为队列底层结构，暴露下列方法：

• New()
• Enqueue()
• Dequeue()
• Front()
• IsEmpty()
• Size()

New类似构造函数，负责初始化内部切片。我们打算创建一个泛型、并发安全的队列ItemQueue。可以使用genny生成特定类型实现，封装泛型类型值的数据结构。genny介绍可参考上篇文章。

ItemQueue.go

package queue 
 
import ( 
	"github.com/cheekybits/genny/generic" 
	"sync" 
) 
 
// Item the type of the queue 
type Item generic.Type 
 
type ItemQueue struct { 
	data [] Item 
	mux sync.RWMutex 
} 
 
func (s *ItemQueue)New() *ItemQueue { 
	s.data = [] Item{} 
	s.mux = sync.RWMutex{} 
	return s 
} 
 
func (s *ItemQueue) Enqueue(item Item) { 
	s.mux.Lock() 
	defer s.mux.Unlock() 
	s.data = append(s.data, item) 
} 
 
func (s *ItemQueue) Dequeue() Item { 
	s.mux.Lock() 
	defer s.mux.Unlock() 
	item := s.data[0] 
	s.data = s.data[1:] 
 
	return item 
} 
 
func (s *ItemQueue) Front() Item { 
	s.mux.RLock() 
	defer s.mux.RUnlock() 
	return s.data[0] 
} 
 
func (s *ItemQueue) IsEmpty() bool { 
	return len(s.data) == 0 
} 
 
func (s *ItemQueue) Size() int { 
	return len(s.data) 
} 

2. 测试

测试代码描述上面方法的使用。

ItemQueue_test.go

package queue 
 
import ( 
	"log" 
	"testing" 
) 
 
var q ItemQueue 
 
func initQueue()  { 
	if q.data == nil { 
		q = ItemQueue{} 
		q.New() 
	} 
} 
 
func TestIQueue_queue(t *testing.T) { 
	initQueue() 
	q.Enqueue(1) 
	q.Enqueue(2) 
	q.Enqueue(3) 
	q.Enqueue(4) 
 
	log.Println("size",q.Size()) 
	item := q.Dequeue() 
	log.Println("pop item",item) 
	log.Println("queue front item",q.Front()) 
 
	log.Println("size",q.Size()) 
	log.Println("isEmpty",q.IsEmpty()) 
} 
 

输出：

2020/07/12 10:47:29 size 4 
2020/07/12 10:47:29 pop item 1 
2020/07/12 10:47:29 queue front item 2 
2020/07/12 10:47:29 size 3 
2020/07/12 10:47:29 isEmpty false 
--- PASS: TestIQueue_queue (0.11s) 
PASS 
 

3. 创建具体队列数据结构

下面生成具体类型，int和string。

//generate a `IntQueue` queue of `int` values 
genny -in IQueue.go -out queue-int.go gen "Item=int" 
 
//generate a `StringQueue` queue of `string` values 
genny -in IQueue.go -out queue-string.go gen "Item=string" 

4. 总结

本文实现安全的泛型队列数据结构。

本文参考链接：https://blog.csdn.net/neweastsun/article/details/107296558