# Queue
队列数据结构，包括ArrayQueue, LinkedQueue, CircularQueue, and PriorityQueue。
# 源码
- https://github.com/duke-git/lancet/blob/main/datastructure/queue/arrayqueue.go (opens new window)
- https://github.com/duke-git/lancet/blob/main/datastructure/queue/linkedqueue.go (opens new window)
- https://github.com/duke-git/lancet/blob/main/datastructure/queue/circularqueue.go (opens new window)
- https://github.com/duke-git/lancet/blob/main/datastructure/queue/priorityqueue.go (opens new window)
# 用法
import (
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
# 目录
# 1. ArrayQueue
# 2. LinkedQueue
# 3. CircularQueue
# 4. PriorityQueue
# 文档
# 1. ArrayQueue
切片实现普通队列数据结构
# NewArrayQueue
返回具有特定容量的ArrayQueue指针
函数签名:
func NewArrayQueue[T any](capacity int) *ArrayQueue[T]
type ArrayQueue[T any] struct {
items []T
head int
tail int
capacity int
size int
}
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
fmt.Println(q.Data()) // []
}
# Data
获取队列所有元素的切片
函数签名:
func (q *ArrayQueue[T]) Data() []T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
fmt.Println(q.Data()) // []
}
# Enqueue
元素入队列
函数签名:
func (q *ArrayQueue[T]) Enqueue(item T) bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Data()) // 1,2,3
}
# Dequeue
移除队列的头元素并返回
函数签名:
func (q *ArrayQueue[T]) Dequeue() (T, bool)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Dequeue()) // 1
fmt.Println(q.Data()) // 2,3
}
# Front
获取对列头部元素
函数签名:
func (q *ArrayQueue[T]) Front() T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Front()) // 1
fmt.Println(q.Data()) // 1,2,3
}
# Back
获取对列尾部元素
函数签名:
func (q *ArrayQueue[T]) Back() T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Back()) // 3
fmt.Println(q.Data()) // 1,2,3
}
# Size
获取队列元素的数量
函数签名:
func (q *ArrayQueue[T]) Size() int
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Size()) // 3
}
# IsEmpty
判断对了是否为空
函数签名:
func (q *ArrayQueue[T]) IsEmpty() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
fmt.Println(q.IsEmpty()) // true
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.IsEmpty()) // false
}
# IsFull
判断对了是否为满
函数签名:
func (q *ArrayQueue[T]) IsFull() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](3)
fmt.Println(q.IsFull()) // false
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.IsFull()) // true
}
# Clear
清空队列元素
函数签名:
func (q *ArrayQueue[T]) Clear()
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
q.Clear()
fmt.Println(q.IsEmpty()) // true
}
# Contain
判断队列是否包含某个值
函数签名:
func (q *ArrayQueue[T]) Contain(value T) bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewArrayQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Contain(1)) // true
fmt.Println(q.Contain(4)) // false
}
# 2. LinkedQueue
链表实现普通队列数据结构
# NewLinkedQueue
返回LinkedQueue指针
函数签名:
func NewLinkedQueue[T any]() *LinkedQueue[T]
type LinkedQueue[T any] struct {
head *datastructure.QueueNode[T]
tail *datastructure.QueueNode[T]
length int
}
type QueueNode[T any] struct {
Value T
Next *QueueNode[T]
}
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int]()
fmt.Println(q.Data()) // []
}
# Data
获取队列所有元素的切片
函数签名:
func (q *LinkedQueue[T]) Data() []T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int]()
fmt.Println(q.Data()) // []
}
# Enqueue
元素入队列
函数签名:
func (q *LinkedQueue[T]) Enqueue(value T)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Data()) // 1,2,3
}
# Dequeue
移除队列的头元素并返回
函数签名:
func (q *LinkedQueue[T]) Dequeue() (T, error)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Dequeue()) // 1
fmt.Println(q.Data()) // 2,3
}
# Front
获取对列头部元素
函数签名:
func (q *LinkedQueue[T]) Front() (*T, error)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Front()) // 1
fmt.Println(q.Data()) // 1,2,3
}
# Back
获取对列尾部元素
函数签名:
func (q *LinkedQueue[T]) Back() (*T, error)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Back()) // 3
fmt.Println(q.Data()) // 1,2,3
}
# Size
获取队列元素的数量
函数签名:
func (q *LinkedQueue[T]) Size() int
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Size()) // 3
}
# IsEmpty
判断对了是否为空
函数签名:
func (q *LinkedQueue[T]) IsEmpty() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
fmt.Println(q.IsEmpty()) // true
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.IsEmpty()) // false
}
# Clear
清空队列元素
函数签名:
func (q *LinkedQueue[T]) Clear()
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
q.Clear()
fmt.Println(q.IsEmpty()) // true
}
# Contain
判断队列是否包含某个值
函数签名:
func (q *LinkedQueue[T]) Contain(value T) bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewLinkedQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Contain(1)) // true
fmt.Println(q.Contain(4)) // false
}
# 3. CircularQueue
切片实现的循环队列.
# NewCircularQueue
返回具有特定容量的CircularQueue指针
函数签名:
func NewCircularQueue[T any](capacity int) *CircularQueue[T]
type CircularQueue[T any] struct {
data []T
front int
rear int
capacity int
}
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
fmt.Println(q.Data()) // []
}
# Data
获取队列所有元素的切片
函数签名:
func (q *CircularQueue[T]) Data() []T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
fmt.Println(q.Data()) // []
}
# Enqueue
元素入队列
函数签名:
func (q *CircularQueue[T]) Enqueue(value T) error
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Data()) // 1,2,3
}
# Dequeue
移除队列的头元素并返回
函数签名:
func (q *CircularQueue[T]) Dequeue() (*T, bool)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
val := q.Dequeue()
fmt.Println(*val) // 1
fmt.Println(q.Data()) // 2,3
}
# Front
获取对列头部元素
函数签名:
func (q *CircularQueue[T]) Front() T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Front()) // 1
fmt.Println(q.Data()) // 1,2,3
}
# Back
获取对列尾部元素
函数签名:
func (q *CircularQueue[T]) Back() T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Back()) // 3
fmt.Println(q.Data()) // 1,2,3
}
# Size
获取队列元素的数量
函数签名:
func (q *CircularQueue[T]) Size() int
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Size()) // 3
}
# IsEmpty
判断对了是否为空
函数签名:
func (q *CircularQueue[T]) IsEmpty() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
fmt.Println(q.IsEmpty()) // true
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.IsEmpty()) // false
}
# IsFull
判断对了是否为满
函数签名:
func (q *CircularQueue[T]) IsFull() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](3)
fmt.Println(q.IsFull()) // false
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.IsFull()) // true
}
# Clear
清空队列元素
函数签名:
func (q *CircularQueue[T]) Clear()
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
q.Clear()
fmt.Println(q.IsEmpty()) // true
}
# Contain
判断队列是否包含某个值
函数签名:
func (q *CircularQueue[T]) Contain(value T) bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewCircularQueue[int](5)
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println(q.Contain(1)) // true
fmt.Println(q.Contain(4)) // false
}
# 4. PriorityQueue
切片实现的额优先级队列。
# NewPriorityQueue
返回一个具有特定容量的PriorityQueue指针，参数 `comarator` 用于比较队列中T类型的值。
函数签名:
func NewPriorityQueue[T any](capacity int, comparator lancetconstraints.Comparator) *PriorityQueue[T]
type PriorityQueue[T any] struct {
items []T
size int
comparator lancetconstraints.Comparator
}
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewPriorityQueue[int](3)
fmt.Println(q.Data()) // []
}
# Data
获取队列所有元素的切片
函数签名:
func (q *PriorityQueue[T]) Data() []T
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
func main() {
q := queue.NewPriorityQueue[int](3)
fmt.Println(q.Data()) // []
}
# Enqueue
元素入队列
函数签名:
func (q *PriorityQueue[T]) Enqueue(item T) bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
comparator := &intComparator{}
q := queue.NewPriorityQueue[int](10, comparator)
for i := 1; i < 11; i++ {
q.Enqueue(i)
}
fmt.Println(q.Data()) // 10, 9, 6, 7, 8, 2, 5, 1, 4, 3
}
# Dequeue
移除队列的头元素并返回
函数签名:
func (q *PriorityQueue[T]) Dequeue() (T, bool)
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
comparator := &intComparator{}
q := queue.NewPriorityQueue[int](10, comparator)
for i := 1; i < 11; i++ {
q.Enqueue(i)
}
val, ok := pq.Dequeue()
fmt.Println(val) // 10
fmt.Println(q.Data()) // 9, 8, 6, 7, 3, 2, 5, 1, 4
}
# IsEmpty
判断对了是否为空
函数签名:
func (q *PriorityQueue[T]) IsEmpty() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
comparator := &intComparator{}
q := queue.NewPriorityQueue[int](10, comparator)
fmt.Println(q.IsEmpty()) // true
for i := 1; i < 11; i++ {
q.Enqueue(i)
}
fmt.Println(q.IsEmpty()) // false
}
# IsFull
判断对了是否为满
函数签名:
func (q *PriorityQueue[T]) IsFull() bool
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
comparator := &intComparator{}
q := queue.NewPriorityQueue[int](10, comparator)
fmt.Println(q.IsFull()) // false
for i := 1; i < 11; i++ {
q.Enqueue(i)
}
fmt.Println(q.IsFull()) // true
}
# Size
获取队列元素的数量
函数签名:
func (q *PriorityQueue[T]) Size() int
例子:
package main
import (
"fmt"
queue "github.com/duke-git/lancet/v2/datastructure/queue"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
comparator := &intComparator{}
q := queue.NewPriorityQueue[int](10, comparator)
fmt.Println(q.IsFull()) // false
for i := 1; i < 5; i++ {
q.Enqueue(i)
}
fmt.Println(q.Size()) // 4
}