Как реализовать очередь в Go?

Question

Текущая библиотека Go не предоставляет контейнер очереди. Чтобы реализовать простую очередь, я использую кругный массив в качестве базовой структуры данных. Отсюда следует алгоритмы, указанные в TAOCP:

Insert Y into queue X: X[R]<-Y; R<-(R+1)%M; if R=F then OVERFLOW. 
Delete Y from queue X: if F=R then UNDERFLOW; Y<-X[F]; F<-(F+1) % M. 
F: Front, R: Rear, M: Array length. 

Ниже приводится код:

package main 

import (
    "fmt" 
) 

type Queue struct { 
    len  int 
    head, tail int 
    q   []int 
} 

func New(n int) *Queue { 
    return &Queue{n, 0, 0, make([]int, n)} 
} 

func (p *Queue) Enqueue(x int) bool { 
    p.q[p.tail] = x 
    p.tail = (p.tail + 1) % p.len 
    return p.head != p.tail 
} 

func (p *Queue) Dequeue() (int, bool) { 
    if p.head == p.tail { 
     return 0, false 
    } 
    x := p.q[p.head] 
    p.head = (p.head + 1) % p.len 
    return x, true 
} 

func main() { 
    q := New(10) 
    for i := 1; i < 13; i++ { 
     fmt.Println(i, q.Enqueue(i)) 
    } 
    fmt.Println() 
    for i := 1; i < 13; i++ { 
     fmt.Println(q.Dequeue()) 
    } 
} 

Но выход, очевидно, неправильно:

1 истинный 2 истинный 3 истинный 4 истинный 5 true 6 true 7 true true 9 истинный 10 ложного 11 истинно 12 истинно

11 истинно 12 истинны 0 ложных 0 ложных 0 ложных 0 ложных 0 ложных 0 ложных 0 ложных 0 ложных 0 ложных 0 ложных

Я думаю, мне нужно еще одно поле, чтобы код работал правильно. Что вы предлагаете?

Усовершенствованный код имеет небольшой недостаток: массив размером n может содержать только n-1 элементов.

package main 

import (
    "fmt" 
) 

type Queue struct { 
    len  int 
    head, tail int 
    q   []int 
} 

func New(n int) *Queue { 
    return &Queue{n, 0, 0, make([]int, n)} 
} 

func (p *Queue) Enqueue(x int) bool { 
    p.q[p.tail] = x 
    ntail := (p.tail + 1) % p.len 
    ok := false 
    if ntail != p.head { 
     p.tail = ntail 
     ok = true 
    } 
    return ok 
} 

func (p *Queue) Dequeue() (int, bool) { 
    if p.head == p.tail { 
     return 0, false 
    } 
    x := p.q[p.head] 
    p.head = (p.head + 1) % p.len 
    return x, true 
} 

func main() { 
    q := New(10) 
    for i := 1; i < 13; i++ { 
     fmt.Println(i, q.Enqueue(i)) 
    } 
    fmt.Println() 
    for i := 1; i < 13; i++ { 
     fmt.Println(q.Dequeue()) 
    } 
} 

Answer 1

Когда Enqueue выходит из строя, вы еще приращением p.tail, поэтому в следующий раз он не будет отображаться на провал - это объясняет в своем первом цикле единственный false (и портит все для второго) , Исходный алгоритм говорит OVERFLOW, что означает «дать все», а не «просто продолжать, как будто ничего не случилось» ;-).

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

Answer 2

Это правда, что нет очереди с пакетом, но либо vector, либо list сделают прекрасные очереди. См. Также this question.

Answer 3

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

package main 

import (
    "fmt" 
) 

type Queue struct { 
    len  uint 
    head, tail uint 
    q   []int 
} 

func NextPowerOfTwo(v uint) uint { 
    if v == 0 { 
     return 1 
    } 
    v-- 
    v |= v >> 1 
    v |= v >> 2 
    v |= v >> 4 
    v |= v >> 8 
    v |= v >> 16 
    v++ 
    return v 
} 

func NewQueue(n uint) *Queue { 
    n = NextPowerOfTwo(n) 
    if n < 4 { 
     n = 4 
    } 
    println("create queue of", n) 
    return &Queue{n, 0, 0, make([]int, n)} 
} 

func (p *Queue) Resize() { 
    if p.head == (p.tail + 1) % p.len { 
     new_len := p.len * 2; 
     new_q := make([]int, new_len) 
     // currently there are (len - 1) items in the queue 
     var i uint 
     for i = 0; i < p.len - 1; i++ { 
      n, _ := p.Dequeue() 
      new_q[i] = n 
     } 
     p.q = new_q 
     p.head, p.tail = 0, p.len - 1 
     p.len = new_len 
     println("queue resized to ", p.len) 
    } 
} 

func (p *Queue) Enqueue(x int) { 
    p.Resize(); 
    p.q[p.tail] = x 
    p.tail = (p.tail + 1) % p.len 
} 

func (p *Queue) Dequeue() (int, bool) { 
    if p.head == p.tail { 
     return -1, false 
    } 
    x := p.q[p.head] 
    p.head = (p.head + 1) % p.len 
    return x, true 
} 

func main() { 
    q := NewQueue(1) 
    for i := 1; i < 13; i++ { 
     q.Enqueue(2 * i + 1) 
     println("enqueued item ", i) 
    } 
    println("** queue content **") 
    for i := 1; i < 13 + 1; i++ { 
     fmt.Println(q.Dequeue()) 
    } 
} 

Answer 4

Буферизованный канал создает точную очередь, хотя и имеет фиксированную максимальную длину очереди, выбранную во время создания. Канал имеет полезное свойство, что dequeues являются потокобезопасными (ваш код не является).

Answer 5

Вам не нужна вся эта суета в любой разумной версии go (после 1.x).Все может быть достигнуто с помощью slices.

queue := []int{}

Добавить в очередь:

queue = append(queue, 6)

Поп из очереди:

el := queue[0] 
queue = queue[1:] 

---

Вот реализация, которая показывает, что поп не занимает много времени (на самом деле здесь она короче, чем толчок, потому что, на мой взгляд, перераспределение памяти при росте очереди).

package main 

import (
    "fmt" 
    "time" 
) 

func main() { 
    n := 10000000 
    queue := []int{1, 2, 3} 

    start := time.Now() 
    for i := 0; i < n; i++ { 
     queue = append(queue, i) 
    } 
    elapsed := time.Since(start) 
    fmt.Println(elapsed) 

    start = time.Now() 
    for i := 0; i < n; i++ { 
     _ = queue[0] 
     queue = queue[1:] 
    } 
    elapsed = time.Since(start) 
    fmt.Println(elapsed) 
    fmt.Println(queue) 
} 

На моей машине цифры:

216.611664ms 
13.441106ms 

От @DaveC «s комментарий:

Это очень просто и работает очень хорошо для всего, кроме критического кода , где распределения (давление на сборщик мусора) составляет . Нежелательно. Два примечания: сначала он сохраняет перераспределение базовый массив при нажатии (хотя эффективно и не на каждом вызове) и поп не освобождают место, пока это не произойдет. Это приводит к второй вещи, если (как это обычно бывает) очередь содержит указатель на что-то, тогда хорошо сделать очередь [0] = nil; queue = queue [1:] до имеют остановку очереди, непосредственно ссылающуюся на указатель.