Go で Stack と FIFO

はじめに

Go 強化月間 と聞いたので Go の記事を書きます。

Go で Stack や FIFO を実装する時には container/list を使います。この container/list は Stack と FIFO に必要となるベースのみ提供されます。なぜなら Stack も FIFO も仕組みは同じで、取り出す時に先頭か最後かの違いしかないからです。

Stack

container/list をフィールドに持ち、末端に追加、末端から取り出すのが Stack ですね。

package main

import (
	"container/list"
	"fmt"
)

type Stack struct {
	v *list.List
}

func NewStack() *Stack {
	return &Stack{v: list.New()}
}

func (s *Stack) Push(v interface{}) {
	s.v.PushBack(v)
}

func (s *Stack) Pop() interface{} {
	b := s.v.Back()
	if b == nil {
		return nil
	}
	return s.v.Remove(b)
}


func main() {
	s := NewStack()
	s.Push(1)
	s.Push(2)
	s.Push(3)
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
	fmt.Println(s.Pop())
}

FIFO

同じく container/list をフィールドに持ち、末端に追加、先頭から取り出すのが FIFO ですね。

package main

import (
	"container/list"
	"fmt"
)

type FIFO struct {
	v *list.List
}

func NewFIFO() *FIFO {
	return &FIFO{v: list.New()}
}

func (s *FIFO) Push(v interface{}) {
	s.v.PushBack(v)
}

func (s *FIFO) Pop() interface{} {
	b := s.v.Front()
	if b == nil {
		return nil
	}
	return s.v.Remove(b)
}

func main() {
	f := NewFIFO()
	f.Push(1)
	f.Push(2)
	f.Push(3)
	fmt.Println(f.Pop())
	fmt.Println(f.Pop())
	fmt.Println(f.Pop())
}

int に限定したい場合は こんな 感じ。

まとめ

Go には Stack や FIFO が無い様に見えて実はある、というお話でした。ちなみに FIFO は chan を使っても実現できます。chan は通常、goroutine でデータを通信する為に使われますが、バッファがあれば同一のメイン goroutine 内で FIFO としても使えます。

package main

import "fmt"

func main() {
    fifo := make(chan int, 5)
    fifo <- 1
    fifo <- 2
    fifo <- 3
    fmt.Println(<-fifo)
    fmt.Println(<-fifo)
    fmt.Println(<-fifo)
}