Как реализовать очередь в Go? - PullRequest
Новая
       36

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

6 голосов
/ 15 июня 2010

Текущая библиотека 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 правда 6 правда 7 правда 8 правда 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())
    }   
}

Ответы [ 5 ]

8 голосов
/ 30 июня 2015

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

queue := []int{}

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

queue = append(queue, 6)

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

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

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

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 :

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

2 голосов
/ 21 января 2011

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

2 голосов
/ 15 июня 2010

Это правда, что нет пакета с именем queue, но либо vector , либо list создаст хорошие очереди. Также смотрите этот вопрос .

1 голос
/ 15 июня 2010

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

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

0 голосов
/ 11 августа 2010

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

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())
    }
}
...