How to Correctly Implement a Queue in Go Using a Circular Array?

How to Implement a Queue in Go

This question explores the implementation of a simple queue in Go using a circular array as the underlying data structure. The approach follows algorithms outlined in "The Art of Computer Programming." However, the initial code presented encountered an issue with incorrect output.

Understanding the Discrepancy

The main issue with the code lies in the lack of a mechanism to handle the situation where the queue is full. The circular array approach requires a way to determine when it's at capacity. The original code lacked this check, resulting in an attempt to overwrite elements beyond the end of the array.

Refining the Implementation

To resolve this issue, a simple modification is introduced. The Enqueue function now includes a condition to verify whether the tail index is not equal to the head index. If they are equal, the queue is full, and the function returns false. Otherwise, it adds the element to the queue, increments the tail index, and returns true.

Improved Code

Here's the updated code:

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
    if ntail != p.head {
        p.tail = ntail
        return true
    }
    return false
}

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

With this modification, the code correctly handles enqueuing and dequeuing elements, resulting in the expected output:

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

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

The above is the detailed content of How to Correctly Implement a Queue in Go Using a Circular Array?. For more information, please follow other related articles on the PHP Chinese website!