Как реализовать очередь в Движении?
Текущая библиотека 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())
}
}
3 ответа
Когда Enqueue терпит неудачу, вы все еще увеличиваете p.tail, так что в следующий раз он, похоже, не потерпит неудачу - это объясняет единственную false в вашем первом цикле (и путает все во втором). Оригинальный алгоритм говорит OVERFLOW, что означает "бросить все", а не "просто продолжать, как будто ничего страшного не произошло";-).
Все, что вам нужно сделать, это уменьшить p.tail, если вы проверили, что происходит сбой - или поместить увеличенное значение в локальный временный файл и переместить его в p.tail только если сбой не происходит, это может быть более элегантно. Таким образом, при отказе Enqueue не зачисляет новое значение, но сама очередь (без переполненного значения) остается семантически целой и корректной для будущих операций.
Это правда, что нет пакета с именем queue, но либо vector , либо list могут создать прекрасные очереди. Также см. этот вопрос .
Я изменяю исходную реализацию, чтобы сделать динамическую очередь. Т.е. когда очередь заполняется, она выделяет большую очередь и перемещает все элементы.
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())
}
}