Goでプログラミングの基礎を学ぶシリーズ

スクールでは教えてくれないプログラミングの基礎、データ構造とアルゴリズムをGoで学んでいくシリーズです。
そのデータ構造がどのようなものであるかは、理解を助けてくれるサイトを紹介しつつ、簡単に説明に留めさせていただきます。(ご自身でも調べてみてください！)
筆者自身、Exerciseに取り組みながら理解を深めていったので、コードの解説を中心に記事を書いていきたいと思います。

	タイトル
#0	はじめに (環境構築と勉強方法)
#1	Pointer, Array, String (ポインタと配列と文字列と)
#2	File operations (ファイル操作)
#3	Linked List (連結リスト)
#4	Stack & Queue (スタックとキュー) ☜ here
#5	Search algorithms (探索アルゴリズム)
#6	Tree (木構造)
#7	Sorting algorithms (ソートアルゴリズム)
#8	String pattern matching algorithms (文字列探索アルゴリズム)

今回は**#4 Stack & Queue (スタックとキュー)**です。

Stack とは, Queue とは

Stack はデータを後入れ先出し( LIFO: Last In First Out )の構造で保持するものです。
Queue はデータを先入れ先出し( FIFO: First In First Out )の構造で保持するものです。

詳細な説明や、使いどころ、例題まで以下の記事を読めば、完全に理解できるかと思います。

この記事ではStackやQueueの説明は割愛し、Goでの実装を中心にしています。
はじめに、上の記事のStackとQueueの簡易実装例を、Goで実装してみました。
Exerciseは、Stackで実装する括弧列の整合性チェックと、QueueをDoubly Linked Listで実装した問題です。
おまけで、筆者がメンターに泣きつきながらなんとか実装した、逆ポーランド記法(Stack)の問題も載せておきます。

Stack の簡易実装例

package main

import "fmt"

var max int = 100000

type Stack struct {
	data []int
}

type StackI interface {
	isEmpty() bool
	isFull() bool
	push(int)
	pop() int
}

var _ StackI = &Stack{}

func (s *Stack) isEmpty() bool {
	return len(s.data) == 0
}

func (s *Stack) isFull() bool {
	return len(s.data) == max
}

func (s *Stack) push(n int) {
	if s.isFull() {
		fmt.Println("error: stack is full")
		return
	}
	s.data = append(s.data, n)
}

func (s *Stack) pop() int {
	if s.isEmpty() {
		fmt.Println("error: stack is empty")
		return 0
	}
	last := len(s.data) - 1
	popData := s.data[last]
	s.data = s.data[:last]
	return popData
}

func main() {
	var s *Stack = &Stack{} // Stackを初期化

	s.push(3) // [] -> [3]
	s.push(5) // [3] -> [3, 5]
	s.push(7) // [3, 5] -> [3, 5, 7]

	fmt.Println(s.pop()) // [3, 5, 7] -> [3, 5] で 7 を出力
	fmt.Println(s.pop()) // [3, 5] -> [3] で 5 を出力

	s.push(9)  // [3] -> [3, 9]
	s.push(11) // [3, 9] -> [3, 9, 11]

	s.pop() // [3, 9, 11] -> [3, 9]
	s.pop() // [3, 9] -> [3]
	s.pop() // [3] -> []

	if s.isEmpty() {
		fmt.Println("empty")
	} else {
		fmt.Println("not empty")
	}
}

☟ 出力結果

7
5
empty

参考記事に似せて実装してみました。
より簡単にするために、Sliceを使って実装しています。
Stackのサイズなど甘い実装ではありますが、初心者向けということで、簡略化しております。
interfaceの参考記事:
初心者に送りたいinterfaceの使い方[Golang]
【Go】基本文法⑥(インターフェース)

Queue の簡易実装例

package main

import "fmt"

var max int = 10000

type Queue struct {
	data []int
}

type QueueI interface {
	isEmpty() bool
	isFull() bool
	enqueue(int)
	dequeue() int
}

var _ QueueI = &Queue{}

func (q *Queue) isEmpty() bool {
	return len(q.data) == 0
}

func (q *Queue) isFull() bool {
	return len(q.data) == max
}

func (q *Queue) enqueue(n int) {
	if q.isFull() {
		fmt.Println("error: queue is full")
		return
	}
	q.data = append(q.data, n)
}

func (q *Queue) dequeue() int {
	if q.isEmpty() {
		fmt.Println("error: queue is empty")
		return 0
	}
	dequeueData := q.data[0]
	q.data = q.data[1:]
	return dequeueData
}

func main() {
	var q *Queue = &Queue{}

	q.enqueue(3) // [] -> [3]
	q.enqueue(5) // [3] -> [3, 5]
	q.enqueue(7) // [3, 5] -> [3, 5, 7]

	fmt.Println(q.dequeue()) // [3, 5, 7] -> [5, 7] で 3 を出力
	fmt.Println(q.dequeue()) // [5, 7] -> [5] で 5 を出力

	q.enqueue(9)  // [7] -> [7, 9]
	q.enqueue(11) // [7, 9] -> [7, 9, 11]

	q.dequeue() // [7, 9, 11] -> [9, 11]
	q.dequeue() // [9, 11] -> [11]
	q.dequeue() // [11] -> []

	if q.isEmpty() {
		fmt.Println("empty")
	} else {
		fmt.Println("not empty")
	}
}

☟ 出力結果

3
5
empty

こちらも簡単のため、headやtailを用いずSliceで実装しています。

💻 Exercise

(())(())((()())))()))()
のような括弧列がすべてペアを作ることができるか（整合性が取れているか）確認するプログラムを実装しましょう。

☟ 解答例

package main

import "fmt"

// 成立したペア用のstruct
type Pair struct {
	begin int
	end   int
}

type Stack struct {
	data []int
}

type StackI interface {
	isEmpty() bool
	push(int)
	pop() int
}

var _ StackI = &Stack{}

func (s *Stack) isEmpty() bool {
	return len(s.data) == 0
}

func (s *Stack) push(i int) {
	s.data = append(s.data, i)
}

func (s *Stack) pop() int {
	if s.isEmpty() {
		fmt.Println("error")
		return 0
	}
	last := len(s.data) - 1
	j := s.data[last]
	s.data = s.data[:last]
	return j
}

func check(brackets string) bool {
	fmt.Printf("\n\ncheck: %s\n", brackets)
	var s *Stack = &Stack{} // Stackを初期化
	var pairs []Pair        // 成立したペアを格納するSlice

	// 括弧列を一括弧ずつ処理する
	for i, b := range brackets {
		if fmt.Sprintf("%c", b) == "(" { // "(" のとき
			s.push(i) // "("の index を Stack に push
		} else { // ")" のとき
			if s.isEmpty() {
				fmt.Printf("error") // ペアになる "(" が Stack にないので error!
				return false
			}
			j := s.pop()                                  // ペアが成立したので、 Stack から pop
			pairs = append(pairs, Pair{begin: j, end: i}) // 成立したペアの index を Sliceに格納
		}
	}

	// 括弧列の処理が終了したとき、 Stack が空でなければ、ペアが成立しなかった index が残っているということ
	if !s.isEmpty() {
		fmt.Printf("too many (")
		return false
	}

	// 成立したペアを出力(おまけ)
	for _, pair := range pairs {
		fmt.Printf("(%d, %d)", pair.begin, pair.end)
	}

	return true
}

func main() {
	check("((()())())") // (2, 3)(4, 5)(1, 6)(7, 8)(0, 9)
	check("())")        // error
	check("(()")        // too many (
}

☟ 出力結果



check: ((()())())
(2, 3)(4, 5)(1, 6)(7, 8)(0, 9)

check: ())
error

check: (()
too many (

成立したペアの出力はおまけのようなものなので、なくてもよいと思います。
Stackのpushやpopは簡易実装例と同じです。
ポイントは(のときはStackにpush、)のときはStackからpopしてペアが成立した！と判定することでしょうか。
)のときにStackが空であれば、ペアが成立しないのでfalseを返します。
また、入力値の処理がすべて終了したときにStackが空でなければ )とペアにならなかった(があるということですので、falseを返します。

💻 Exercise

キャンセル待ちのお客様リストを想定します。
お客様の情報には、名前、電話番号、メールアドレスを登録します。
キャンセル待ちのお客様情報をリストに登録していきましょう。
キャンセルが出たら、一番最初に登録されたお客様の情報をリストから削除し、出力しましょう。
※解答例ではDoubly Linked Listを用いて実装しますが、上記が実現できればどのような実装方法でも問題ないです。

☟ 解答例

package main

import (
	"fmt"
)

type Customer struct {
	name             string
	telephone_number string
	email_address    string
}

type Node struct {
	data *Customer
	prev *Node
	next *Node
}

type Queue struct {
	front *Node
	rear  *Node
}

type QueueI interface {
	isEmpty() bool
	Enqueue(Customer)
	Dequeue() *Node
}

var _ QueueI = &Queue{}

func (q *Queue) isEmpty() bool {
	return q.front == q.rear && q.front == nil
}

func (q *Queue) Enqueue(c Customer) {
	var node *Node = &Node{data: &c}
	if q.isEmpty() { // Queue が空のとき、 front も rear も node をさす
		q.front = node
		q.rear = node
	} else { // Queue が空ではないとき、
		q.rear.next = node // リストの最後尾に node をリンクする
		node.prev = q.rear // node の　prev はそれまでリスト最後尾だった Node になる
		q.rear = node      // リストの最後尾を node にする
	}
}

func (q *Queue) Dequeue() *Node {
	if q.isEmpty() {
		fmt.Println("No one is waiting for cancellation")
		return nil
	}

	node := q.front        // 取り除く Node
	q.front = q.front.next // リストの先頭の Node は先頭の次の Node になる
	if q.front != nil {    // リストが空ではない
		q.front.prev = nil
	} else { // リストが空
		q.rear = nil
	}

	fmt.Printf("\nSomeone canceled!! %s can now be booked.\n", node.data.name)
	return node
}

// キャンセル待ちリストの出力
func (q *Queue) Traverse() {
	node := q.front
	for i := 1; ; i++ {
		if node == nil {
			break
		} else {
			fmt.Printf("%d: %v\n", i, *node.data)
			node = node.next
		}
	}
}

func main() {
	var q *Queue = &Queue{} // Queue を初期化

	var c1 *Customer = &Customer{name: "Sakura", telephone_number: "090-1234-5678", email_address: "sakura@example.com"}
	fmt.Printf("\n%s is waiting for cancellation\n", c1.name)
	q.Enqueue(*c1) // キャンセル待ちリストに追加
	q.Traverse()

	var c2 *Customer = &Customer{name: "Kaede", telephone_number: "080-1234-5678", email_address: "kaede@example.com"}
	fmt.Printf("\n%s is waiting for cancellation\n", c2.name)
	q.Enqueue(*c2)
	q.Traverse()

	q.Dequeue() // キャンセルが出たので、キャンセル待ちリストの先頭を Dequeue する
	q.Traverse()

	var c3 *Customer = &Customer{name: "Yuzu", telephone_number: "070-1234-5678", email_address: "yuzu@example.com"}
	fmt.Printf("\n%s is waiting for cancellation\n", c3.name)
	q.Enqueue(*c3)
	q.Traverse()
}

☟ 出力結果


Sakura is waiting for cancellation
1: {Sakura 090-1234-5678 sakura@example.com}

Kaede is waiting for cancellation
1: {Sakura 090-1234-5678 sakura@example.com}
2: {Kaede 080-1234-5678 kaede@example.com}

Someone canceled!! Sakura can now be booked.
1: {Kaede 080-1234-5678 kaede@example.com}

Yuzu is waiting for cancellation
1: {Kaede 080-1234-5678 kaede@example.com}
2: {Yuzu 070-1234-5678 yuzu@example.com}

💻 おまけExercise

Stackを使用して、中置記法 (Infix Notation) の式を逆ポーランド記法 (Reverse Polish Notation)へ変換するプログラムを実装しましょう。
【条件】

式は、1桁の正の数（1~9）と4つの演算子（+, -, *, /）で構成されます。
標準入力から中置記法の式を読み取り、それを逆ポーランド記法に変換し、出力します。
変換した式を計算し、計算結果を出力します。

【例】
入力 : 3+54
出力 : 354+ = 23

参考:
THE POLISH NOTATION
逆ポーランド記法変換 (計算機)

☟ 解答例

package main

import (
	"fmt"
	"strconv"
)

// 特に置き換える必要はありませんが、汎用性のため Element に置き換えています
type Element string

type Stack struct {
	data []Element
}

type StackI interface {
	isEmpty() bool
	Push(operator Element)
	Pop() Element
	Top() Element
}

var _ StackI = &Stack{}

func (stack *Stack) isEmpty() bool {
	return len(stack.data) == 0
}

func (stack *Stack) Push(operator Element) {
	stack.data = append(stack.data, operator)
}

func (stack *Stack) Pop() Element {
	top := stack.Top()
	stack.data = stack.data[:len(stack.data)-1]
	return top
}

func (stack *Stack) Top() Element {
	if stack.isEmpty() {
		return ""
	}
	return stack.data[len(stack.data)-1]
}

// 演算子であるかどうかの判定
func isOperator(s string) bool {
	operators := []string{"+", "-", "*", "/"}
	for _, o := range operators {
		if s == o {
			return true
		}
	}
	return false
}

func inStackPriority(s string) int {
	switch s {
	case "+", "-":
		return 1
	case "*", "/":
		return 2
	default:
		return 0
	}
}

func inComingPriority(s string) int {
	switch s {
	case "+", "-":
		return 1
	case "*", "/":
		return 2
	default:
		return 0
	}
}

func convertRPN(input string) string {
	var stack *Stack = &Stack{} // Stack の初期化, 演算子を Push/Pop していく
	var expression string       // 出力する式
	for _, v := range input {
		s := fmt.Sprintf("%c", v)
		if isOperator(s) { // 演算子のとき
			for {
				if inComingPriority(s) > inStackPriority(string(stack.Top())) {
					stack.Push(Element(s))
					break
				} else {
					top := stack.Pop()
					expression += string(top)
				}
			}
		} else { // 正数のとき
			expression += s
		}
	}

	for {
		if stack.isEmpty() {
			break
		} else {
			top := stack.Pop()
			expression += string(top)
		}
	}

	return expression
}

func check(e error) {
	if e != nil {
		panic(e)
	}
}

// 計算
func operate(s string, a, b int) int {
	switch s {
	case "+":
		return b + a
	case "-":
		return b - a
	case "*":
		return b * a
	case "/":
		return b / a
	default:
		return 0
	}
}

func calculateRPN(expRPN string) int {
	var stack *Stack = &Stack{} // Stack の初期化, 正数を Push/Pop していく
	for _, v := range expRPN {
		s := fmt.Sprintf("%c", v)
		if isOperator(s) { // 演算子のとき
			a, err := strconv.Atoi(string(stack.Pop()))
			check(err)
			b, err := strconv.Atoi(string(stack.Pop()))
			check(err)
			stack.Push(Element(fmt.Sprintf("%d", operate(s, a, b)))) // 計算結果を Stack に Push
		} else { // 正数のとき
			stack.Push(Element(s))
		}
	}
	n, err := strconv.Atoi(string(stack.Pop()))
	check(err)
	return n
}

func main() {
	var input string
	fmt.Println("計算式を入力してください (1~9,+,-,*,/) 例: 3+5*4")
	fmt.Scanf("%s", &input)

	expRPN := convertRPN(input)
	fmt.Printf(expRPN)
	result := calculateRPN(expRPN)
	fmt.Printf(" = %d", result)
}

☟ 出力結果

計算式を入力してください (1~9,+,-,*,/) 例: 3+5*4
7-3*4/2+1
734*2/-1+ = 2

わかりにくいのはPriorityのところですかね。
演算子には優先度があって、大きい方が先に計算されます(中置記法でも同じですね)。
StackのTopにある演算子の優先度と比較して大きい場合と小さい場合で、演算子をPushするか、StackからPopするか処理が異なります。

おわりに

Exerciseの解答例はあくまで例なので、もっといい書き方あるよ！という方、ぜひコメントをお寄せください！
説明についても、筆者自身が初心者であるため、ご指摘や補足は大歓迎でございます。

株式会社Link Sportsでは、あらゆるスポーツを楽しむ人たちに送る、チームマネジメントアプリを開発しています。
未経験でも経験豊富なエンジニアの方でも、スポーツ好きなら活躍できる環境があります！
絶賛エンジニア募集中です！
Wantedly ▶︎ https://www.wantedly.com/projects/324177
Green ▶︎ https://www.green-japan.com/job/82003

次回は、データ構造とアルゴリズム**#5 Search algorithms (検索アルゴリズム)**です。