🛠️

Go言語 (Golang) でintのスタックとキューを実装してみる

2021/02/17に公開

アルゴリズム

tech

はじめに

最近Go言語に興味が出てきて，過去にアルゴリズム理解のため勉強したプログラミングコンテストチャレンジブック [第2版] をGoで解き直し始めました．

で，初級編の 2-1 すべての基本 "全探索" > スタック/キュー で早速あれ？となりました．以前はC++で勉強していたため，サンプルコードをそのまま追っていればよかったのですが，Goでは標準でスタックとキューの実装がありません．

Goでのスタックもただのスライス＋appendで実装できるを参考にすると，単純なsliceを用いてスタックとキューの機能は実現できそうだったので，メモリ管理に気を付けながらstructで実装してみました．

設計

実装方針

もともとJavaをやっていたのではじめはGenericsを用いて汎用的なスタック・キューを実装しようと思いましたが，そもそもGoにはまだGenericsが存在しません．The Next Step for Generics を見ると，2021年8月リリースのGo1.17で追加される予定はありそうですが，現在のバージョンでGenericsっぽいことをするためには，interface{} を使って頑張るか，各型毎に個別に実装していくことになります．

もともとプログラミングコンテストチャレンジブックを解き進めることが目的だったので，本記事では汎用的なスタック・キューを作成することはせず，intのスタック・キューに絞って実装していきます．

前述の記事に倣い，Goの可変長配列であるsliceを用いてスタックとキューを実装します．スタックの実装はキューより簡単で，可変長配列を利用すれば道なりに実装できます．

キューの実装については方針を決めるのがちょっと難しくて (実装自体はシンプル)，初めは線形キューだとメモリ使用量の増加やメモリリークが問題になりそうなので循環キューでの実装を考えていましたが，Goでのキューはただのスライス＋appendで実装できるでも紹介されているように，sliceを上手に利用すればよしなにメモリ効率化ができそうなので，循環配列ではなくsliceで実装することにしました．

とはいえで，メモリの初期割当やガベージコレクションの振る舞いに気をつけないと，予期せぬパフォーマンスの悪化やメモリリークを引き起こしてしまうので，色々調べながら慎重に進めてみます．

sliceの初期化について

まず，スタックやキューを初期化するときに，内部で保持するsliceも初期化する必要があります．スタックやキューを実装している色々な方の記事を読んでいると，この初期化の際にキャパシティを確保していない方が多いように見えます．

data := make([]int, 0)

Go初学者が学んだことまとめ〜appendがどのくらい遅いか検証してみた〜の記事がとても参考になりました．適切なキャパシティをsliceに割り当てていない場合，appendの処理の効率がかなり落ちます．appendする度にslice用の新しいメモリ領域を確保→容量を拡張する必要があるからです．

上記記事でもパフォーマンスを測定していますが，個人的にも簡易的なTestファイルを作成してパフォーマンスを測定してみました．0から10の9乗までループしながらsliceに追加していくという単純な処理です．

slice_test.go

package datastruct

import (
    "fmt"
    "testing"
)

// Test_NotAllocate is performance test without allocating any capacity to slice.
func Test_NotAllocate(t *testing.T) {
    s := make([]int, 0)
    for i := 0; i < 1e9; i++ {
        s = append(s, i)
    }
    fmt.Println(len(s))
}

// Test_Allocate is performance test with allocating enough capacity to slice.
func Test_Allocate(t *testing.T) {
    s := make([]int, 0, 1e9)
    for i := 0; i < 1e9; i++ {
        s = append(s, i)
    }
    fmt.Println(len(s))
}

// Test_Initialize is performance test with initializing the elements of slice.
func Test_Initialize(t *testing.T) {
    s := make([]int, 1e9, 1e9)
    for i := 0; i < 1e9; i++ {
        s[i] = i
    }
    fmt.Println(len(s))
}

結果は以下のようになりました．振る舞いとしては上記記事と同様で，容量を確保していないsliceへのappend (Test_NotAllocate) は非常に重いという結果でした．

=== RUN   Test_NotAllocate
1000000000
--- PASS: Test_NotAllocate (36.94s)
=== RUN   Test_Allocate
1000000000
--- PASS: Test_Allocate (6.38s)
=== RUN   Test_Initialize
1000000000
--- PASS: Test_Initialize (12.78s)
PASS

Process finished with exit code 0

この結果で確信が持てたので，スタックとキューの初期化ではキャパシティに適切な値をセットする方針で実装したいと思います．

メモリリーク

※これは私もまだあまり詳しくない部分なので，間違ったことを書いている場合には指摘頂ければ嬉しいです．

キューのPopを実装しようとすると，Goでのキューはただのスライス＋appendで実装できると同様に，スライスを用いた以下のコードを書きたくなります．

q := make([]int, 0, cap)
q = append(q, 1)

// Pop
ret := q[0]
q = q[1:]

return ret

実際，intのsliceをキューと見なしている上記コードではこれで問題なく動きます．が，q = q[1:] として q[0] への参照を切った場合のガベージコレクションの振る舞いを興味本位で調べてみたところ，Does go garbage collect parts of slices? のstack overflowを見つけました．ベストアンサーの通り，sliceをスライスした結果参照されない領域が発生したとしても，その領域がslice外のメモリへの参照を持つ場合，Goのガベージコレクションは動かないようです．^[1]

具体的には，文字列やポインタのsliceの場合には，スライスによるメモリリークの可能性がある，とのことでした．今回実装するのはintのスライスなので一安心ですが，もしstringやポインタのスタックを実装する場合には，キューのPopで q[0] への参照を明示的に切る必要があるのでご注意ください．

スタック

実装

スタックは以下のように実装しました．structの内部にデータを保持させるsliceとスタックのサイズを持たせ，初期化用の関数 NewStack とスタック操作用の関数 Push, Pop, Top, IsEmpty を実装しました．また，デバッグ用に Stringer インタフェースを実装しています．

stack.go

package datastruct

import "fmt"

// Stack implementation
type Stack struct {
    data []int
    size int
}

// NewStack instantiates a new stack
func NewStack(cap int) *Stack {
    return &Stack{data: make([]int, 0, cap), size: 0}
}

// Push adds a new element at the end of the stack
func (s *Stack) Push(n int) {
    s.data = append(s.data, n)
    s.size++
}

// Pop removes the last element from stack
func (s *Stack) Pop() bool {
    if s.IsEmpty() {
        return false
    }
    s.size--
    s.data = s.data[:s.size]
    return true
}

// Top returns the last element of stack
func (s *Stack) Top() int {
    return s.data[s.size-1]
}

// IsEmpty checks if the stack is empty
func (s *Stack) IsEmpty() bool {
    return s.size == 0
}

// String implements Stringer interface
func (s *Stack) String() string {
    return fmt.Sprint(s.data)
}

ソースの通り，初期化関数 NewStack でキャパシティを割り当てられるようにしています．その他の部分は割と自明かなと思います．

なお，Top関数において，スタックが空か否かの判定は入れていません．ので，スタックが空の状態でTopを実行すると下記panicが発生して落ちます．

panic: runtime error: index out of range [-1] [recovered]

ここは，Topの結果 (int) とerrorの2つを呼び出し元に返却し，エラーハンドリングさせてもいいかなと思いました．ただ，今回は競技プログラミング等での個人利用を想定していてエラー判定はしないこと，またスタックが空の状態でTopを呼んでしまうのは呼び出し元の設計が悪そうという考えから，スタックの空チェックは除外しました．

テスト

前節で実装したスタックの動作確認をしてみます．テストコードは以下のように書きました．

stack_test.go

package datastruct

import (
    "testing"
)

func TestStack(t *testing.T) {
    stack := NewStack(100)

    fmt.Println(stack)
    if !stack.IsEmpty() {
        t.Fatalf("True is expected, but %v\n", stack.IsEmpty())
    }

    stack.Push(10)
    fmt.Println(stack)
    stack.Push(1)
    fmt.Println(stack)
    stack.Push(-5)
    fmt.Println(stack)

    if stack.IsEmpty() {
        t.Fatalf("False is expected, but %v\n", stack.IsEmpty())
    }

    if stack.Top() != -5 {
        t.Fatalf("-5 is expected, but %v\n", stack.Top())
    }

    stack.Pop()
    fmt.Println(stack)
    if stack.Top() != 1 {
        t.Fatalf("1 is expected, but %v\n", stack.Top())
    }

    stack.Pop()
    fmt.Println(stack)
    if stack.Top() != 10 {
        t.Fatalf("10 is expected, but %v\n", stack.Top())
    }

    stack.Pop()
    fmt.Println(stack)
    if !stack.IsEmpty() {
        t.Fatalf("True is expected, but %v\n", stack.IsEmpty())
    }
}

10, 1, -5 の順にスタックにPushした結果，その逆順でPopできることを確認しています．これをIDE (私はGolandを利用しています) やコマンドラインから実行すると PASS することが確認できます．

=== RUN   TestStack
[]
[10]
[10 1]
[10 1 -5]
[10 1]
[10]
[]
--- PASS: TestStack (0.00s)
PASS

Process finished with exit code 0

キュー

実装

キューは以下のように実装しました．structの内部にデータを保持させるsliceとキューのサイズを持たせるのはスタックと同じです．structの関数としては，初期化用の関数 NewQueue とキュー操作用の関数 Push, Pop, Front, IsEmpty を実装しました．また，デバッグ用に Stringer インタフェースを実装しています．

queue.go

package datastruct

import "fmt"

// Queue implementation
type Queue struct {
    data []int
    size int
}

// NewQueue instantiates a new queue
func NewQueue(cap int) *Queue {
    return &Queue{data: make([]int, 0, cap), size: 0}
}

// Push adds a new element at the end of the queue
func (q *Queue) Push(n int) {
    q.data = append(q.data, n)
    q.size++
}

// Pop removes the first element from queue
func (q *Queue) Pop() bool {
    if q.IsEmpty() {
        return false
    }
    q.size--
    q.data = q.data[1:]
    return true
}

// Front returns the first element of queue
func (q *Queue) Front() int {
    return q.data[0]
}

// IsEmpty checks if the queue is empty
func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

// String implements Stringer interface
func (q *Queue) String() string {
    return fmt.Sprint(q.data)
}

スタックとの差はPopで要素を削除する部分と，Frontで返却するインデックスのみです．設計の章で述べましたが，stringやポインタ等のキューを実装する場合には，Popで q.data[0] への参照を切らないとメモリリークしますので気をつけてください．例えばstringのキューを実装するのであれば，以下のようにゼロ文字列をセットすることで参照を切ります．

func (q *Queue) Pop() bool {
    if q.IsEmpty() {
        return false
    }
    q.size--
    q.data[0] = "" // Important!!
    q.data = q.data[1:]
    return true
}

テスト

前節で実装したキューの動作確認をしてみます．スタックとは逆に，10, 1, -5の順でPushした要素がそのままの順番でPopされることを確認します．

queue_test.go


import (
    "fmt"
    "testing"
)

func TestQueue(t *testing.T) {
    queue := NewQueue(10)
    fmt.Println(queue)

    if !queue.IsEmpty() {
        t.Fatalf("True is expected, but %v\n", queue.IsEmpty())
    }

    queue.Push(10)
    fmt.Println(queue)
    queue.Push(1)
    fmt.Println(queue)
    queue.Push(-5)
    fmt.Println(queue)

    if queue.IsEmpty() {
        t.Fatalf("False is expected, but %v\n", queue.IsEmpty())
    }

    if queue.Front() != 10 {
        t.Fatalf("10 is expected, but %v\n", queue.Front())
    }

    queue.Pop()
    fmt.Println(queue)
    if queue.Front() != 1 {
        t.Fatalf("1 is expected, but %v\n", queue.Front())
    }

    queue.Pop()
    fmt.Println(queue)
    if queue.Front() != -5 {
        t.Fatalf("-5 is expected, but %v\n", queue.Front())
    }

    queue.Pop()
    fmt.Println(queue)
    if !queue.IsEmpty() {
        t.Fatalf("True is expected, but %v\n", queue.IsEmpty())
    }
}

テストコードの実行結果は以下の通りです．正常にPushとPopができていることがわかります．

=== RUN   TestQueue
[]
[10]
[10 1]
[10 1 -5]
[1 -5]
[-5]
[]
--- PASS: TestQueue (0.00s)
PASS

Process finished with exit code 0

まとめ

以上でintのスタックとキューは実装完了です．stringやカスタムのstructのスタック・キューが必要な場面に遭遇したら，上記コードを微修正して使い回そうかなと思います．Go1.17のリリースでGenericsが追加されるのが待ち遠しいです．．．

本記事で紹介したソースコードはGitHub (こちら) で公開していますので，参考までに．

脚注

このstack overflowは5年以上前のものなので，最新のGoではGCの振る舞い変わってるよーとか，もしご存知であれば教えて下さいm(_ _)m ↩︎