首页 > 后端开发 > Golang > Go语言数据结构探究:队列与栈的应用

Go语言数据结构探究:队列与栈的应用

PHPz
发布: 2024-04-08 12:57:01
原创
861 人浏览过

Go 语言中,队列遵守先进先出 (FIFO) 原则,使用标准库中的 list 包实现,常用于消息传递系统;栈遵守后进先出 (LIFO) 原则,常用于函数调用跟踪和括号匹配,可以使用切片实现。

Go语言数据结构探究:队列与栈的应用

Go语言数据结构漫谈:队列与栈的应用

队列

队列是一种遵守先进先出(FIFO)原则的数据结构。这意味着最早进入队列的元素将首先被移除。队列在以下场景中非常有用:

  • 消息传递系统,如消息队列
  • 缓冲区,如网络请求队列

Go语言中队列的实现

Go语言中的队列最常见的实现方式是使用container/list标准库包:

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

import (

    "container/list"

)

 

// 定义队列类型

type Queue struct {

    items *list.List

}

 

// 创建队列

func NewQueue() *Queue {

    return &Queue{

        items: list.New(),

    }

}

 

// 进队

func (q *Queue) Enqueue(item interface{}) {

    q.items.PushBack(item)

}

 

// 出队

func (q *Queue) Dequeue() interface{} {

    if q.IsEmpty() {

        return nil

    }

    front := q.items.Front()

    q.items.Remove(front)

    return front.Value

}

 

// 判断队列是否为空

func (q *Queue) IsEmpty() bool {

    return q.items.Len() == 0

}

登录后复制

实战案例:消息队列

消息队列是队列的一个典型应用场景。我们可以使用Go语言中的队列来实现一个消息队列:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

func main() {

    // 创建消息队列

    queue := NewQueue()

 

    // 向队列发送消息

    queue.Enqueue("消息 1")

    queue.Enqueue("消息 2")

 

    // 接收消息

    for {

        msg := queue.Dequeue()

        if msg == nil {

            break

        }

        fmt.Println(msg)

    }

}

登录后复制

栈是一种遵守后进先出(LIFO)原则的数据结构。这意味着最后进入栈中的元素将首先被移除。栈在以下场景中非常有用:

  • 函数调用跟踪
  • 括号匹配

Go语言中栈的实现

Go语言中的栈最简单的实现方式是使用切片:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

// 定义栈类型

type Stack []interface{}

 

// 进栈

func (s *Stack) Push(item interface{}) {

    *s = append(*s, item)

}

 

// 出栈

func (s *Stack) Pop() interface{} {

    if s.Empty() {

        return nil

    }

    top := (*s)[len(*s)-1]

    *s = (*s)[:len(*s)-1]

    return top

}

 

// 判断栈是否为空

func (s *Stack) Empty() bool {

    return len(*s) == 0

}

登录后复制

实战案例:括号匹配

栈是一个检查括号匹配的好工具:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

func isBalanced(expr string) bool {

    stack := Stack{}

    for _, char := range expr {

        if char == '(' || char == '[' || char == '{' {

            stack.Push(char)

        } else if char == ')' || char == ']' || char == '}' {

            if stack.Empty() {

                return false

            }

            top := stack.Pop()

            if (char == ')' && top != '(') || (char == ']' && top != '[') || (char == '}' && top != '{') {

                return false

            }

        }

    }

    return stack.Empty()

}

登录后复制

以上是Go语言数据结构探究:队列与栈的应用的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板