植物のミカタ

字句解析器を作る為にデータ構造のスタックを見るの記事で、データ構造のスタックを見た。

オリジナルのアップロード者は英語版ウィキペディアのR. Kootさん - en.wikipedia からコモンズに移動されました。, CC 表示-継承 3.0, リンクによる

スタックはデータの後入れ先出しで配列に値を入れた際、一番最後の値を取り出すというものだった。

今回はデータ構造でスタックと合わせて紹介されるキューについて見てみる。

This Image was created by User:Vegpuff.If you are using the image under the creative commons share alike license please credit the photo Vegpuff/Wikipedia and include a link to this page. No explicit permission is needed from me, but an email if my work has been of help to you.If you dont want to release your work under a creative commons license, please mail me at vegpuff@gmail.com or catch me at my twitter stream for a custom license. - 投稿者自身による作品, CC 表示-継承 3.0, リンクによる

キューは先入れ先出しのデータ構造になっていて、複数のタスクが待機して順に実行する時に用いられる。

ちなみにキューの用語はデータの挿入がEnqueue(エンキュー)でデータの取り出しがDequeue(デキュー)と呼ぶ。

それでは上のイメージに合わせてGoで書いてみることにする。

---

最初にディレクトリ構造は下記のようにする

queue
├── main.go
└── queue
    └── queue.go

queue/queue.goは下記のように書いた。

package queue

import (
	"log"
)

const capacity int = 10

var first int
var last int = -1

//キュー用の配列
func New() []int {
	return make([]int, capacity)
}

//エンキュー
func Enqueue(s []int, x int) {
	//キューが満杯になっているか？は下記の式で確かめられる
	last++
	if last >= capacity {
		log.Fatal("キューが満杯です")
	}

	s[last] = x
}

//デキュー
func Dequeue(s []int) int {
	if first-1 == last {
		log.Fatal("ジョブがありません")
	}

	x := s[first]
	s[first] = 0 //値を空にする
	first++
	return x
}

firstとlastで最初に入れた位置と最後の位置を管理する。

このコードを用いて、EnqueueとDequeueを試してみる。

main.go

package main

import (
	"fmt"

	"./queue"
)

func main() {
	s := queue.New()
	fmt.Println(s)

	fmt.Println("5,3,7を入れてみる")
	queue.Enqueue(s, 5)
	queue.Enqueue(s, 3)
	queue.Enqueue(s, 7)

	fmt.Println("0,3,7であれば良い")
	fmt.Println(s)

	fmt.Println("値を取り出してみる。5であれば良い")
	fmt.Println(queue.Dequeue(s))

	queue.Enqueue(s, 2)
	queue.Enqueue(s, 4)

	fmt.Println("0,3,7,2,4であれば良い")
	fmt.Println(s)

	fmt.Println("値を取り出してみる。3であれば良い")
	fmt.Println(queue.Dequeue(s))
}

実行結果は下記の通り

$ go run main.go
[0 0 0 0 0 0 0 0 0 0]
5,3,7を入れてみる
0,3,7であれば良い
[5 3 7 0 0 0 0 0 0 0]
値を取り出してみる。5であれば良い
5
0,3,7,2,4であれば良い
[0 3 7 2 4 0 0 0 0 0]
値を取り出してみる。3であれば良い
3

期待通りの動作となっている。

---

ここで一つ気になる事がある。

キューを管理する配列を最後まで到達したらどうなるのだろう？

先程のコードであればオーバーフローになるが、ここで使い勝手を良くする為に、

直線だった配列の両端を繋いでリングバッファにする。

それでは、リングバッファになるようにコードを書き換えてみる。

queue/queue.go

package queue

import (
	"log"
)

const capacity int = 10

var first int
var last int = capacity - 1

//キュー用の配列
func New() []int {
	return make([]int, capacity)
}

//エンキュー
func Enqueue(s []int, x int) {
	//キューが満杯になっているか？は下記の式で確かめられる(動作が怪しい)
	if first > 0 && (last+1)%capacity == first {
		log.Fatal("ジョブが満杯です")
	}

	last++
	if last == capacity {
		last = 0
	}
	s[last] = x
}

//デキュー
func Dequeue(s []int) int {
	if first-1 == last { lastが9の時は正常に動作しないので要検討
		log.Fatal("ジョブがありません")
	}

	x := s[first]
	s[first] = 0 //値を空にする
	first++
	if first == capacity {
		first = 0
	}
	return x
}

書き換えたコードを試してみる。

main.go

package main

import (
	"fmt"

	"./queue"
)

func main() {
	s := queue.New()

	//オーバーフローの準備 値を10個
	for i := 1; i <= 10; i++ {
		queue.Enqueue(s, i)
	}

	fmt.Println("値がすべて埋まっている状態")
	fmt.Println(s)

	fmt.Println("最初にいれた1を取り出す")
	fmt.Println(queue.Dequeue(s))

	fmt.Println("リングバッファになっているか確認するため、新たに値を入れてみる")
	queue.Enqueue(s, 11)

	fmt.Println("値がすべて埋まっている状態")
	fmt.Println(s)

	fmt.Println("値を追加してオーバーフローにする")
	queue.Enqueue(s, 12)
}

実行結果は下記の通り

$ go run main.go
値がすべて埋まっている状態
[1 2 3 4 5 6 7 8 9 10]
最初にいれた1を取り出す
1
リングバッファになっているか確認するため、新たに値を入れてみる
値がすべて埋まっている状態
[11 2 3 4 5 6 7 8 9 10]
値を追加してオーバーフローにする
2020/10/01 15:40:48 ジョブが満杯です
exit status 1

想定通りの処理になったかなと。

前回同様、事前にたくさんのケースを加えたテストコードを作る必要があるけれども、今回は端折る。

golangでテストを書いてみたのでメモ