【アルゴリズムとデータ構造】Go言語でスタックを実装する

投稿日：2020年11月2日更新日：2021年8月10日

Go言語でスタックを簡易実装します。

データに対する操作として、

以下の３つを実装します。

New() : スタックの初期化

Push() : 要素の追加

Pop() : 要素の取り出し

コードは以下のようになります。

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

type Stack struct {
	arr []int
	top int
}

func (s *Stack) New() {
	s.arr = make([]int, 0)
	s.top = -1
}

func (s *Stack) Pop() int {
	/*if s.top > -1 {
		return
	}*/
	ele := s.arr[s.top]
	if s.top > 0 { //削っても1個以上残る場合
		s.arr = append(s.arr[0:], s.arr[:s.top]...) //[:s.top]は未満なので注意。以下ではない
	} else { //削ったら何も残らなくなる場合
		s.arr = nil
	}
	s.top--
	return ele
}

func (s *Stack) Push(ele int) {
	s.arr = append(s.arr, ele)
	s.top++
}

func main() {
	s := Stack{}
	s.New()

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	for scanner.Scan() {
		switch scanner.Text() {
		case "push":
			scanner.Scan()
			str := scanner.Text()
			ele, _ := strconv.Atoi(str)
			s.Push(ele)
		case "pop":
			fmt.Println("Pop number: ", s.Pop())
		}
		if err := scanner.Err(); err == io.EOF {
			break
		}
	}

	for s.top != -1 {
		fmt.Println(s.Pop())
	}
}

package main

import (

"bufio"

"fmt"

"io"

"os"

"strconv"

)

type Stack struct {

arr []int

top int

}

func (s *Stack) New() {

s.arr = make([]int, 0)

s.top = -1

}

func (s *Stack) Pop() int {

/*if s.top > -1 {

return

}*/

ele := s.arr[s.top]

if s.top > 0 { //削っても1個以上残る場合

s.arr = append(s.arr[0:], s.arr[:s.top]...) //[:s.top]は未満なので注意。以下ではない

} else { //削ったら何も残らなくなる場合

s.arr = nil

}

s.top--

return ele

}

func (s *Stack) Push(ele int) {

s.arr = append(s.arr, ele)

s.top++

}

func main() {

s := Stack{}

s.New()

scanner := bufio.NewScanner(os.Stdin)

scanner.Split(bufio.ScanWords)

for scanner.Scan() {

switch scanner.Text() {

case "push":

scanner.Scan()

str := scanner.Text()

ele, _ := strconv.Atoi(str)

s.Push(ele)

case "pop":

fmt.Println("Pop number: ", s.Pop())

}

if err := scanner.Err(); err == io.EOF {

break

}

for s.top != -1 {

fmt.Println(s.Pop())

}

例として以下の実行画面も載せます。

ちなみにscan()を抜けるとき、

スタックに要素が残っている場合は、

全て吐き出すようにしてあります。

Goだとスライスの概念があるので、

スタックの長さ事前に決める必要がないのは、

ありがたいですね！

スライスが可変長配列を実現してくれるおかげです。

しかし実際は、要素をappend()するたびに、

固定長配列が作成されなおすので、

スライスが示すアドレスも変わります。

これが意味するのは、

旧配列がゴミになるということです。

これを取り除かないとメモリを圧迫します。

とはいえ、、、

Goにはガベージコレクタが標準であるので、

ランタイムが定期的にこのゴミ掃除をしてくれます。

自分で切り出しておいて結局のところ、

メモリ解放は気にする必要はないですけどね。

上述したことをもっと詳しく知りたい方は、

こちらの記事を参考にして下さい^^

メモリとガベージコレクタについて書いてあります。

さらに補足ですが、

今回はスタック構造体でint型のスライスを宣言しましたが、

実際は []*int のようにポインタにした方が良いと思います。

intなので１要素あたりのバイトはたかが知れていますが、

サイズの大きい構造体などを出し入れする場合は、

メモリ上でまとまった領域を確保することが

困難になる可能性があります。

したがってポインタを出し入れすることで、

実態はメモリ上で不連続に確保されても

良いようにしておきます。

最後まで読んでいただきありがとうございました。