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

Ответ 1

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

Ответ 2

Фактически, если вы хотите, это простая и простая в использовании очередь 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 и slicing, чтобы избежать бесполезного изменения размера и перераспределения. Для базового использования это вполне достаточно.

Ответ 3

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

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

//Push
c <- value

//Pop
x <- c

Ответ 4

Чтобы расширить область реализации, Moraes предлагает в его 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
}

Вы можете увидеть это в действии в этом примере игровой площадки.

Ответ 5

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

Ответ 6

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

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

Ответ 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 здесь простая очередь