Есть ли реализация очереди?

Question

Может ли кто-нибудь предложить контейнер Go для простой и быстрой FIF/очереди, Go имеет 3 разных контейнера: heap, list и vector. Какой из них более подходит для реализации очереди?

Answer 1

Любой вектор или список должны работать, но вектор - это, вероятно, путь. Я говорю это, потому что вектор, вероятно, будет выделяться реже, чем сбор списков и мусора (в текущей реализации Go) довольно дорого. Однако в небольшой программе это, вероятно, не имеет значения.

Answer 2

Для расширения на стороне реализации, Moraes предлагает в his gist некоторые из очереди-структуру и стек:

// Stack is a basic LIFO stack that resizes as needed. 
type Stack struct { 
    nodes []*Node 
    count int 
} 
// Queue is a basic FIFO queue based on a circular list that resizes as needed. 
type Queue struct { 
    nodes []*Node 
    head int 
    tail int 
    count int 
} 

Вы можете увидеть его в действии в этом playground example.

Answer 3

На самом деле, если вам нужна простая и простая в использовании очередь fifo, срез предоставляет все, что вам нужно.

queue := make([]int, 0) 
// Push 
queue := append(queue, 1) 
// Top (just get next element, don't remove it) 
x = queue[0] 
// Discard top element 
queue = queue[1:] 
// Is empty ? 
if len(queue) == 0 { 
    fmt.Println("Queue is empty !") 
} 

Конечно, мы предполагаем, что мы можем доверять внутренней реализации Append и нарезку, так что избежать бесполезного изменения размера и перераспределить. Для основного использования это вполне достаточно.

Answer 4

Удивлен, что никто не предлагал буферизованные каналы, так как в любом случае FIFO Queue с ограниченным размером.

//Or however many you might need + buffer. 
c := make(chan int, 300) 

//Push 
c <- value 

//Pop 
x <- c 

Answer 5

Используя кусочек и соответствующий («круговой») схема индексации сверху еще, кажется, путь. Вот мой пример: https://github.com/phf/go-queue Тесты там также подтверждают, что каналы быстрее, но по цене более ограниченной функциональности.

Answer 6

Ломтик может использоваться для реализации очереди.

type queue struct { 
    values []*int 
} 

func New() *queue { 
    queue := &queue{} 
    return queue 
} 

func (q *queue) enqueue(val *int) { 
    q.values = append(q.values, val) 
} 

//deque function 

Update:

здесь завершена реализация на моей странице GitHub https://github.com/raiskumar/algo-ds/blob/master/tree/queue.go

Answer 7

Я также реализовать очередь из ломтика, как описано выше. Тем не менее, он не является потокобезопасным. Поэтому я решил добавить блокировку (блокировку мьютекса), чтобы гарантировать потокобезопасность.

package queue 

import (
    "sync" 
) 

type Queue struct { 
    lock *sync.Mutex 
    Values []int 
} 

func Init() Queue { 
    return Queue{&sync.Mutex{}, make([]int, 0)} 
} 

func (q *Queue) Enqueue(x int) { 
    for { 
    q.lock.Lock() 
    q.Values = append(q.Values, x) 
    q.lock.Unlock() 
    return 
    } 
} 

func (q *Queue) Dequeue() *int { 
    for { 
    if (len(q.Values) > 0) { 
     q.lock.Lock() 
     x := q.Values[0] 
     q.Values = q.Values[1:] 
     q.lock.Unlock() 
     return &x 
    } 
    return nil 
    } 
    return nil 
} 

Вы можете проверить мое решение на GitHub здесь simple queue