queue.md

Queue

A queue is a kind of linear table. It only allows delete operations at the front of the table and insert operations at the rear of the table. This package includes ArrayQueue, LinkedQueue, CircularQueue, and PriorityQueue.

Source

• https://github.com/duke-git/lancet/blob/main/datastructure/queue/arrayqueue.go
• https://github.com/duke-git/lancet/blob/main/datastructure/queue/linkedqueue.go
• https://github.com/duke-git/lancet/blob/main/datastructure/queue/circularqueue.go
• https://github.com/duke-git/lancet/blob/main/datastructure/queue/priorityqueue.go

Usage

import (
    queue "github.com/duke-git/lancet/v2/datastructure/queue"
)

Index

1. ArrayQueue

• NewArrayQueue
• Data
• Enqueue
• Dequeue
• Front
• Back
• Size
• IsEmpty
• IsFull
• Clear
• Contain

2. LinkedQueue

• NewLinkedQueue
• Data
• Enqueue
• Dequeue
• Front
• Back
• Size
• IsEmpty
• Clear
• Contain

3. CircularQueue

• NewCircularQueue
• Data
• Enqueue
• Dequeue
• Front
• Back
• Size
• IsEmpty
• IsFull
• Clear
• Contain

4. PriorityQueue

• NewPriorityQueue
• Data
• Enqueue
• Dequeue
• IsEmpty
• IsFull
• Size

Documentation

1. ArrayQueue

Common queue implemented by slice.

NewArrayQueue

Return a ArrayQueue pointer with specific capacity

Signature:

func NewArrayQueue[T any](capacity int) *ArrayQueue[T]

type ArrayQueue[T any] struct {
	items    []T
	head     int
	tail     int
	capacity int
	size     int
}

Example:

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

Get all queue data

Signature:

func (q *ArrayQueue[T]) Data() []T

Example:

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

Put element into queue, if queue is full, return false

Signature:

func (q *ArrayQueue[T]) Enqueue(item T) bool

Example:

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

Remove head element of queue and return it

Signature:

func (q *ArrayQueue[T]) Dequeue() (T, bool)

Example:

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

Just get the head element of queue

Signature:

func (q *ArrayQueue[T]) Front() T

Example:

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

Just get the tail element of queue

Signature:

func (q *ArrayQueue[T]) Back() T

Example:

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

Get the number of elements in queue

Signature:

func (q *ArrayQueue[T]) Size() int

Example:

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

Check if queue is empty or not

Signature:

func (q *ArrayQueue[T]) IsEmpty() bool

Example:

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

Check if queue is full or not

Signature:

func (q *ArrayQueue[T]) IsFull() bool

Example:

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

Clean all data in queue

Signature:

func (q *ArrayQueue[T]) Clear()

Example:

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

Check if the value is in queue or not

Signature:

func (q *ArrayQueue[T]) Contain(value T) bool

Example:

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

Common queue implemented by link.

NewLinkedQueue

Return a LinkedQueue pointer

Signature:

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]
}

Example:

package main

import (
    "fmt"
    queue "github.com/duke-git/lancet/v2/datastructure/queue"
)

func main() {
    q := queue.NewLinkedQueue[int]()
    fmt.Println(q.Data()) // []
}

Data

Get all queue data

Signature:

func (q *LinkedQueue[T]) Data() []T

Example:

package main

import (
    "fmt"
    queue "github.com/duke-git/lancet/v2/datastructure/queue"
)

func main() {
    q := queue.NewLinkedQueue[int]()
    fmt.Println(q.Data()) // []
}

Enqueue

Put element into queue

Signature:

func (q *LinkedQueue[T]) Enqueue(value T)

Example:

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

Remove head element of queue and return it

Signature:

func (q *LinkedQueue[T]) Dequeue() (T, error)

Example:

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

Just get the head element of queue

Signature:

func (q *LinkedQueue[T]) Front() (*T, error)

Example:

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

Just get the tail element of queue

Signature:

func (q *LinkedQueue[T]) Back() (*T, error) 

Example:

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

Get the number of elements in queue

Signature:

func (q *LinkedQueue[T]) Size() int

Example:

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

Check if queue is empty or not

Signature:

func (q *LinkedQueue[T]) IsEmpty() bool

Example:

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

Clean all data in queue

Signature:

func (q *LinkedQueue[T]) Clear()

Example:

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

Check if the value is in queue or not

Signature:

func (q *LinkedQueue[T]) Contain(value T) bool

Example:

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

Circular queue implemented by slice.

NewCircularQueue

Return a CircularQueue pointer with specific capacity

Signature:

func NewCircularQueue[T any](capacity int) *CircularQueue[T]

type CircularQueue[T any] struct {
	data  []T
	front int
	rear  int
	capacity  int
}

Example:

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

Get all queue data

Signature:

func (q *CircularQueue[T]) Data() []T

Example:

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

Put element into queue, if queue is full, return error

Signature:

func (q *CircularQueue[T]) Enqueue(value T) error

Example:

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

Remove head element of queue and return it

Signature:

func (q *CircularQueue[T]) Dequeue() (*T, bool)

Example:

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

Just get head element of queue

Signature:

func (q *CircularQueue[T]) Front() T

Example:

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

Just get tail element of queue

Signature:

func (q *CircularQueue[T]) Back() T

Example:

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

Get the number of elements in queue

Signature:

func (q *CircularQueue[T]) Size() int

Example:

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

Check if queue is empty or not

Signature:

func (q *CircularQueue[T]) IsEmpty() bool

Example:

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

Check if queue is full or not

Signature:

func (q *CircularQueue[T]) IsFull() bool

Example:

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

Clean all data in queue

Signature:

func (q *CircularQueue[T]) Clear()

Example:

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

Check if the value is in queue or not

Signature:

func (q *CircularQueue[T]) Contain(value T) bool

Example:

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

Common queue implemented by slice.

NewPriorityQueue

Return a PriorityQueue pointer with specific capacity, param `comparator` is used to compare values of type T in the queue.

Signature:

func NewPriorityQueue[T any](capacity int, comparator constraints.Comparator) *PriorityQueue[T]

type PriorityQueue[T any] struct {
	items      []T
	size       int
	comparator constraints.Comparator
}

Example:

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

Get all queue data

Signature:

func (q *PriorityQueue[T]) Data() []T

Example:

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

Put element into queue, if queue is full, return false

Signature:

func (q *PriorityQueue[T]) Enqueue(item T) bool

Example:

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

Remove head element of queue and return it

Signature:

func (q *PriorityQueue[T]) Dequeue() (T, bool)

Example:

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

Check if queue is empty or not

Signature:

func (q *PriorityQueue[T]) IsEmpty() bool

Example:

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

Check if queue is full or not

Signature:

func (q *PriorityQueue[T]) IsFull() bool

Example:

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

Get nubmers of elements in queue

Signature:

func (q *PriorityQueue[T]) Size() int

Example:

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
}