Go言語で汎用両端キューの実装

Go でキューの実装は、上記事で append を使って簡単にしています。なるほどと思いました。

ふつうはこれで充分ですよね。スタックは2本のキューで実装できるので、これも簡単です。しかし、任意の型を入れられるキュー、しかもメモリを効率よく使うキューがあれば便利かと思って、遊びで実装してみました。Go は3日前にさわり始めたばかりなので、おそらくはおかしなことをしていると思います。

queue.go

package main
import "fmt"
import "os"

const QueueMax = 100      //キューのサイズ
var qfield [QueueMax]interface{}    //実際に使う配列の宣言

type Queue struct {
    out int
    in  int
    length int
    field []interface{}
}

func (q *Queue) enqueue(obj interface{}) {
    if q.length == QueueMax {
       fmt.Println("Queue Overflow")
       os.Exit(1)
    }
    q.field[q.in] = obj
    q.in++
    q.length++
    if q.in == QueueMax {q.in = 0}
}

func (q *Queue) dequeue() (obj interface{}) {
    if q.length == 0 {return false}
    obj = q.field[q.out]
    q.out++
    q.length--
    if q.out == QueueMax {q.out = 0}
    return obj
}

どんな型でも入れられるように、空のインターフェースを使っています。
　
実際に使ってみます。わかりやすいように、const QueueMax = 2（長さ 2 の配列を使う）としています。

func main() {
    queue := &Queue{out: 0, in: 0, length: 0, field: qfield[:]}
    
    queue.enqueue(100)
    queue.enqueue("二百")
    fmt.Println(queue.field)       //=>[100 二百]
    fmt.Println(queue.dequeue())   //=>100
    fmt.Println(queue.field)       //=>[100 二百]
    queue.enqueue(300)
    fmt.Println(queue.field)       //=>[300 二百]
    fmt.Println(queue.dequeue())   //=>二百
    queue.enqueue([1]int{400})
    fmt.Println(queue.field)       //=>[300 [400]]
    fmt.Println(queue.dequeue())   //=>300
    fmt.Println(queue.dequeue())   //=>[400]
    fmt.Println(queue.dequeue())   //=>false
    fmt.Println(queue.dequeue())   //=>false
}

どうでしょうか。いろんな型が入り混じっていると思います。長さ 2 の配列を使っているのに、途中で dequeue しているので 4 回 enqueue できていますね。まあ遊びですが。
なお、空のキューに dequeue すると、エラーではなくて false を返します。キューが溢れるとエラー終了します。

ちなみに、上記事と同じ人の書いたこれも、ハマりやすいことをわかりやすく教えてくれるなあと思いました。
これも構造体とポインタの話でわかりやすかった。

※追記
pop() と shift() も加えて、両端キューにしてみました。

func (q *Queue) pop() (obj interface{}) {
    if q.length == 0 {return false}
    q.in--
    q.length--
    if q.in == -1 {q.in = QueueMax - 1}
    obj = q.field[q.in]
    return obj
}

func (q *Queue) shift(obj interface{}) {
    if q.length == QueueMax {
       fmt.Println("Queue Overflow")
       os.Exit(1)
    }
    q.out--
    q.length++
    if q.out == -1 {q.out = QueueMax - 1}
    q.field[q.out] = obj
}

メソッドの名前は言語によっていろいろです。上で enqueue() というのは push() がふつうですかね。shift() ってのはどうなのか知りませんが、僕は Ruby から採りました。
しかし、こうなると out, in ではなくて head, tail とでもしておけばよかったかな。

ここまでとりあえず、図書館から借りてきた下の本と Google 先生だけでやっています。まだゴルーチンとかわからない…。

改訂2版 基礎からわかる Go言語

Go は簡単だっていうけれど、ポインタとかあるしやはり初心者にはそんなに簡単でもない。「参照型」の考え方とかも必須だし。でも、やはり C よりははるかにラクですっきりしていますね。コードの見た目がすっきりしていて好きだ。必要ない記述は書かないでよいという態度がいいですね。DRY 精神として Ruby と似ている。
でも素人が3日でこの程度は書けるようになるから、やはり簡単なのかなあ…。