원형 배열을 사용하여 Go에서 큐 데이터 구조를 올바르게 구현하는 방법은 무엇입니까?

Go에서 대기열을 구현하는 방법은 무엇입니까?

배경:

Go에서 표준 라이브러리에는 대기열 컨테이너가 없습니다. . 대기열을 구현하려면 원형 배열을 기본 데이터 구조로 활용할 수 있습니다.

초기 구현:

제공된 코드는 다음 알고리즘과 함께 원형 배열을 사용합니다.

• 삽입: 큐 X에 Y 삽입: X[R] <-Y; R
• 삭제: 대기열 X에서 Y를 삭제합니다. F = R이면 UNDERFLOW; Y

여기서 F는 앞, R은 뒤, M은 배열 길이입니다.

코드 및 올바르지 않음 출력:

제공된 코드는 이러한 알고리즘을 구현하지만 출력이 잘못되었습니다. 동작:

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

Output:

1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
10 false
11 true
12 true

11 true
12 true
0 false
0 false
0 false
0 false
0 false
0 false
0 false
0 false
0 false
0 false

해결책:

이 문제를 해결하려면 추가 필드가 필요합니다. 수정된 코드에는 업데이트된 꼬리 위치가 머리와 일치하지 않는지 확인하는 검사가 포함되어 있습니다.

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

이 수정을 통해 출력은 정확합니다.

1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
10 true
11 true
12 true

1
2
3
4
5
6
7
8
9
10
11
12

슬라이스를 사용한 대체 구현:

최신 Go 버전에서는 다음을 사용하여 더 간단한 구현이 가능합니다. Slices:

package main

import (
    "fmt"
)

// Queue implements a queue using a slice.
type Queue []int

// Enqueue adds an element to the end of the queue.
func (q *Queue) Enqueue(x int) {
    *q = append(*q, x)
}

// Dequeue removes and returns the first element of the queue.
func (q *Queue) Dequeue() (int, bool) {
    if len(*q) == 0 {
        return 0, false
    }
    x := (*q)[0]
    *q = (*q)[1:]
    return x, true
}

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

    for i := 0; i < 12; i++ {
        x, _ := q.Dequeue()
        fmt.Println(x)
    }
}

이 구현은 Slice의 동적 성장과 가비지 수집을 활용하여 효율적이고 실용적입니다.

위 내용은 원형 배열을 사용하여 Go에서 큐 데이터 구조를 올바르게 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!