Go语言-队列

摘要

数据结构里的队列就是模仿现实中的排队。队列简称FIFO。

队列有两个特点:

  • 新来的都排在队尾;
  • 最前面的办理业务后离队,后面一个跟上。

https://blog.csdn.net/u010278923/article/details/72582200

接口说明及实现

Init

初始化队列,其实是初始化里面单链表。

1
2
3
4
5
6
func (queue *Queue) Init() {
lst := new(List)
(*queue).list = lst

lst.Init()
}

Enqueue

1
2
3
func (queue *Queue) Enqueue(data Object) bool {
return (*queue).list.Append(data)
}

Dequeue

1
2
3
func (queue *Queue) Dequeue() Object {
return (*queue).list.RemoveAt(0)
}

Peek

1
2
3
func (queue *Queue) Peek() Object {
return (*queue).list.First()
}

GetSize

1
2
3
func (queue *Queue) GetSize() uint64 {
return (*queue).list.GetSize()
}

container/list

list是一个双向链表。该结构具有链表的所有功能。

1
2
3
type Element struct {
Value interface{} //在元素中存储的值
}

基本用法

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
package main

import (
"fmt"
"container/list"
)

func main() {
// 生成队列
l := list.New()

// 入队, 压栈
l.PushBack(1)
l.PushBack(2)
l.PushBack(3)
l.PushBack(4)

// 出队
i1 := l.Front()
l.Remove(i1)
fmt.Printf("%d\n", i1.Value)

// 出栈
i4 := l.Back()
l.Remove(i4)
fmt.Printf("%d\n", i1.Value)
}

用法详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (e *Element) Next() *Element  //返回该元素的下一个元素,如果没有下一个元素则返回nil
func (e *Element) Prev() *Element//返回该元素的前一个元素,如果没有前一个元素则返回nil
type List
func New() *List //返回一个初始化的list
func (l *List) Back() *Element //获取list l的最后一个元素
func (l *List) Front() *Element //获取list l的第一个元素
func (l *List) Init() *List //list l初始化或者清除list l
func (l *List) InsertAfter(v interface{}, mark *Element) *Element //在list l中元素mark之后插入一个值为v的元素,并返回该元素,如果mark不是list中元素,则list不改变。
func (l *List) InsertBefore(v interface{}, mark *Element) *Element//在list l中元素mark之前插入一个值为v的元素,并返回该元素,如果mark不是list中元素,则list不改变。
func (l *List) Len() int //获取list l的长度
func (l *List) MoveAfter(e, mark *Element) //将元素e移动到元素mark之后,如果元素e或者mark不属于list l,或者e==mark,则list l不改变。
func (l *List) MoveBefore(e, mark *Element)//将元素e移动到元素mark之前,如果元素e或者mark不属于list l,或者e==mark,则list l不改变。
func (l *List) MoveToBack(e *Element)//将元素e移动到list l的末尾,如果e不属于list l,则list不改变。
func (l *List) MoveToFront(e *Element)//将元素e移动到list l的首部,如果e不属于list l,则list不改变。
func (l *List) PushBack(v interface{}) *Element//在list l的末尾插入值为v的元素,并返回该元素。
func (l *List) PushBackList(other *List)//在list l的尾部插入另外一个list,其中lother可以相等。
func (l *List) PushFront(v interface{}) *Element//在list l的首部插入值为v的元素,并返回该元素。
func (l *List) PushFrontList(other *List)//在list l的首部插入另外一个list,其中lother可以相等。
func (l *List) Remove(e *Element) interface{}//如果元素e属于list l,将其从list中删除,并返回元素e的值。

实际用法示例

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package main

import (
"container/list"
"fmt"
)

func main() {
l := list.New() //创建一个新的list
for i := 0; i < 5; i++ {
l.PushBack(i)
}
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value) //输出list的值,01234
}
fmt.Println("")
fmt.Println(l.Front().Value) //输出首部元素的值,0
fmt.Println(l.Back().Value) //输出尾部元素的值,4
l.InsertAfter(6, l.Front()) //首部元素之后插入一个值为10的元素
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value) //输出list的值,061234
}
fmt.Println("")
l.MoveBefore(l.Front().Next(), l.Front()) //首部两个元素位置互换
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value) //输出list的值,601234
}
fmt.Println("")
l.MoveToFront(l.Back()) //将尾部元素移动到首部
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value) //输出list的值,460123
}
fmt.Println("")
l2 := list.New()
l2.PushBackList(l) //将l中元素放在l2的末尾
for e := l2.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value) //输出l2的值,460123
}
fmt.Println("")
l.Init() //清空l
fmt.Print(l.Len()) //0
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value) //输出list的值,无内容
}
}


func my() {
l := list.New()
l.PushBack(path)

var result []string
for l.Len() > 0 {
i1 := l.Front()
l.Remove(i1)
value, ok := i1.Value.(string)
if !ok {
fmt.Println("It's not ok for type string")
continue
}
ret, e := d.SDK.Bucket(d.Bucket).Prefix(value).Delimiter(delimiter).HasCommonPrefix(true).ListObject()
if e != nil {
fmt.Printf("ListObject %v [%s]<%s> failed, %v", d.Bucket, prefix, delimiter, e)
}

for _, dir := range ret.CommonPrefixes {
if strings.HasSuffix(dir, "/") {
dir = strings.TrimSuffix(dir, "/")
}
result = append(result, dir)
l.PushBack(dir+"/")
}

for _, file := range ret.Contents {
result = append(result, file.Key)
}
}
}

Stack

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package algorithm

import (
"errors"
"fmt"
)


type Stack struct {
Element []interface{} //Element
}

func NewStack() *Stack {
return &Stack{}
}

func (stack *Stack)Push(value ...interface{}){
stack.Element = append(stack.Element,value...)
}

//返回下一个元素
func (stack *Stack)Top()(value interface{}){
if stack.Size() > 0 {
return stack.Element[stack.Size() - 1]
}
return nil //read empty stack
}

//返回下一个元素,并从Stack移除元素
func (stack *Stack)Pop()(err error){
if stack.Size()> 0 {
stack.Element = stack.Element[:stack.Size() - 1]
return nil
}
return errors.New("Stack为空.") //read empty stack
}

//交换值
func (stack *Stack)Swap(other *Stack){
switch{
case stack.Size() == 0 && other.Size() == 0:
return
case other.Size() == 0 :
other.Element = stack.Element[:stack.Size()]
stack.Element = nil
case stack.Size()== 0 :
stack.Element = other.Element
other.Element = nil
default:
stack.Element,other.Element = other.Element,stack.Element
}
return
}

//修改指定索引的元素
func (stack *Stack)Set(idx int,value interface{})(err error){
if idx >= 0 && stack.Size() > 0 && stack.Size() > idx{
stack.Element[idx] = value
return nil
}
return errors.New("Set失败!")
}

//返回指定索引的元素
func (stack *Stack)Get(idx int)(value interface{}){
if idx >= 0 && stack.Size() > 0 && stack.Size() > idx {
return stack.Element[idx]
}
return nil //read empty stack
}

//Stack的size
func (stack *Stack)Size()(int){
return len(stack.Element)
}

//是否为空
func (stack *Stack)Empty()(bool){
if stack.Element == nil || stack.Size() == 0 {
return true
}
return false
}

//打印
func (stack *Stack)Print(){
for i := len(stack.Element) - 1; i >= 0; i--{
fmt.Println(i,"=>",stack.Element[i])
}
}

测试

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
54
55
56
57
package main


import (
"fmt"
"github.com/xcltapestry/xclpkg/algorithm"
)

func main(){

stack := algorithm.NewStack()
if stack.Empty() {
fmt.Println("Stack为空! ")
}else{
fmt.Println("Stack不为空! ",stack.Size())
}

stack.Push(10)
stack.Push(20)
stack.Push(30)
stack.Push(40)
fmt.Println("当前Size() = ",stack.Size())
stack.Print()

fmt.Println("当前Top() = ",stack.Top())

stack.Pop()
fmt.Println("执行完Pop()后的Top() = ",stack.Top())
stack.Print()


stack.Set(2,900)
fmt.Println("\n执行完Set(2,900)后的Stack")
stack.Print()

fmt.Println("\nGet()查看指定的元素: ")
fmt.Println("当前idx为1的元素 = ",stack.Get(1))
fmt.Println("当前idx为2的元素 = ",stack.Get(2))

stack2 := algorithm.NewStack()
stack2.Push("111")
stack2.Push("222")
fmt.Println("\nstack2的初始内容:")
stack2.Print()

stack.Swap(stack2)
fmt.Println("Swap()后stack的内容:")
stack.Print()
fmt.Println("Swap()后stack2的内容:")
stack2.Print()


fmt.Println("\nstack增加字符串元素: ")
stack.Push("中文元素")
stack.Push("elem1")
stack.Print()
}