Golang 中栈、队列的实现及常用操作，数据结构系列原文：flaviocopes.com，翻译已获作者授权。

栈

概述

栈是数据按照后进先出 LIFO(Last-In-First-Out) 原则组成的集合。添加和移除元素都是在栈顶进行，类比书堆，不能在栈底增删元素。

栈的应用很广泛，比如网页跳转后一层层返回，ctrl+z 撤销操作等。

sliceItemStack
1
2
3
New()	// 生成栈的构造器
Push()	
Pull()
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package stack

import (
	"github.com/cheekybits/genny/generic"
	"sync"
)

type Item generic.Type

type ItemStack struct {
	items []Item
	lock  sync.RWMutex
}

// 创建栈
func (s *ItemStack) New() *ItemStack {
	s.items = []Item{}
	return s
}

// 入栈
func (s *ItemStack) Push(t Item) {
	s.lock.Lock()
	s.items = append(s.items, t)
	s.lock.Unlock()
}

// 出栈
func (s *ItemStack) Pop() *Item {
	s.lock.Lock()
	item := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1 ]
	s.lock.Unlock()
	return &item
}

测试用例：stack_test.go

队列

概述

队列是数据按照先进先出 FIFO(First-In-First-Out) 原则组成的集合，类比排队，在队列任一端添加元素，从对应的另一端删除元素。

sliceItemQueue
1
2
3
4
5
6
New()		// 生成队列的构造器
Enqueue()
Dequeue()
Front()
IsEmpty()
Size()
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package queue

import (
	"github.com/cheekybits/genny/generic"
	"sync"
)

type Item generic.Type

type ItemQueue struct {
	items []Item
	lock  sync.RWMutex
}

// 创建队列
func (q *ItemQueue) New() *ItemQueue {
	q.items = []Item{}
	return q
}

// 如队列
func (q *ItemQueue) Enqueue(t Item) {
	q.lock.Lock()
	q.items = append(q.items, t)
	q.lock.Unlock()
}

// 出队列
func (q *ItemQueue) Dequeue() *Item {
	q.lock.Lock()
	item := q.items[0]
	q.items = q.items[1:len(q.items)]
	q.lock.Unlock()
	return &item
}

// 获取队列的第一个元素，不移除
func (q *ItemQueue) Front() *Item {
	q.lock.Lock()
	item := q.items[0]
	q.lock.Unlock()
	return &item
}

// 判空
func (q *ItemQueue) IsEmpty() bool {
	return len(q.items) == 0
}

// 获取队列的长度
func (q *ItemQueue) Size() int {
	return len(q.items)
}

测试用例：queue_test.go