Queue

A queue is a linear structure that follows FIFO order in which the operations are performed.

Below queues are provided:

• Concurrent Linked [Blocking] Queue
• Concurrent Array Blocking Queue

Before getting started, u need to import these packages in src.

import (
    "github.com/KokoiRuby/generickit/queue"
    "github.com/KokoiRuby/generickit/list"
)

Concurrent Linked Queue

This queue is unbound, using sync.atomic & CAS operation to secure concurrency.

// head(val + next) → head.next(val + next) → ...  → tail (val + next)     Node Layer
//
//
// &head                  &(head.next)                    &(tail)          Pointer Layer
//
//   ↑                                                       ↑
//
// q.head                                                  q.tail          ConcurrentLinkedQueue

func NewConcurrentLinkedQueue

func NewConcurrentLinkedQueue[T any]() *ConcurrentLinkedQueue[T]

Constructor.

Example:

func ExampleConcurrentLinkedQueue() {
    q := queue.NewConcurrentLinkedQueue[int]()
    _ = q.Enqueue(1)
    val, _ := q.Dequeue()
    fmt.Println(val)
    // output:
    // 1
}

Concurrent Linked Blocking Queue

Leverage Go built-in sync primitive sync.RWMutex & sync.Cond to secure concurrency & blocking.

Leverage Go built-in context to achieve timeout control.

func NewConcurrentLinkedBlockingQueue

func NewConcurrentLinkedBlockingQueue[T any](capacity int) *ConcurrentLinkedBlockingQueue[T]

Constructor. Whether queue is bound is controlled by capacity where negative val indicates unbound.

Example:

func ExampleConcurrentLinkedBlockingQueue() {
	q := queue.NewConcurrentLinkedBlockingQueue[int](3)
    ctx, cancel := context.WithTimeout(context.Background(), time.Second)
	defer cancel()
    
	_ = q.Enqueue(1)
	val, err := q.Dequeue()
    switch err {
	case context.Canceled:
        // cancel() called
	case context.DeadlineExceeded:
		// timeout
	case nil:
		fmt.Println(val)
	default:
		// TODO
	}
	// Output:
	// 1
}

Concurrent Array Blocking Queue

Leverage Go built-in sync primitive sync.RWMutex & sync.Cond to secure concurrency & blocking.

Leverage Go built-in context to achieve timeout control.

Note: This queue only provides bound version. (slice expansion overhead if unbound)

func NewConcurrentArrayBlockingQueue

func NewConcurrentArrayBlockingQueue[T any](capacity int) *ConcurrentArrayBlockingQueue[T]

Constructor.

Example:

func ExampleConcurrentLinkedBlockingQueue() {
	q := queue.NewConcurrentArrayBlockingQueue[int](3)
    ctx, cancel := context.WithTimeout(context.Background(), time.Second)
	defer cancel()
    
	_ = q.Enqueue(1)
	val, err := q.Dequeue()
    switch err {
	case context.Canceled:
        // cancel() called
	case context.DeadlineExceeded:
		// timeout
	case nil:
		fmt.Println(val)
	default:
		// TODO
	}
	// Output:
	// 1
}