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