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 (検索アルゴリズム)**です。