Go 语言中,队列遵守先进先出 (FIFO) 原则,使用标准库中的 list 包实现,常用于消息传递系统;栈遵守后进先出 (LIFO) 原则,常用于函数调用跟踪和括号匹配,可以使用切片实现。
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中文网其他相关文章!