【Go】Stack & Queue (スタックとキュー)

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

|  | タイトル |
|------|---------|
| #0 | [はじめに (環境構築と勉強方法)](https://qiita.com/miyyuk/items/0b959774a2e436f087c0) |
| #1 | [Pointer, Array, String (ポインタと配列と文字列と)](https://qiita.com/miyyuk/items/75fad6c02b76354fa49d) |
| #2 | [File operations (ファイル操作)](https://qiita.com/miyyuk/items/641faf682e09709727af) |
| #3 | [Linked List (連結リスト)](https://qiita.com/miyyuk/items/af9d3352f89f11365dc4) |
| #4 | Stack & Queue (スタックとキュー) **☜ here** |
| #5 | [Search algorithms (探索アルゴリズム)](https://qiita.com/miyyuk/items/91920dee5151e9c4c43e) |
| #6 | [Tree (木構造)](https://qiita.com/miyyuk/items/a11c22a62bb95c1996ba) |
| #7 | [Sorting algorithms (ソートアルゴリズム)](https://qiita.com/miyyuk/items/85c2ed8176e9bdf7e677)|
| #8 | [String pattern matching algorithms (文字列探索アルゴリズム)](https://qiita.com/miyyuk/items/bce37f7f8c24b48cfd3f) |

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

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

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

https://qiita.com/drken/items/6a95b57d2e374a3d3292

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

## Stack の簡易実装例

```golang
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]](https://medium.com/since-i-want-to-start-blog-that-looks-like-men-do/%E5%88%9D%E5%BF%83%E8%80%85%E3%81%AB%E9%80%81%E3%82%8A%E3%81%9F%E3%81%84interface%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9-golang-48eba361c3b4)
[【Go】基本文法⑥(インターフェース)](https://qiita.com/k-penguin-sato/items/885a61d819cc431304f5)

## Queue の簡易実装例

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

☟ 解答例

```golang
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`を用いて実装しますが、上記が実現できればどのような実装方法でも問題ないです。

☟ 解答例

```golang
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`を使用して、[中置記法](https://ja.wikipedia.org/wiki/%E4%B8%AD%E7%BD%AE%E8%A8%98%E6%B3%95) (Infix Notation) の式を[逆ポーランド記法](https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95) (Reverse Polish Notation)へ変換するプログラムを実装しましょう。
【条件】
1. 式は、1桁の正の数（1~9）と4つの演算子（`+`, `-`, `*`, `/`）で構成されます。
2. 標準入力から中置記法の式を読み取り、それを逆ポーランド記法に変換し、出力します。
3. 変換した式を計算し、計算結果を出力します。

【例】
入力 : 3+5*4
出力 : 354*+ = 23

参考:
[THE POLISH NOTATION](https://www.cp.eng.chula.ac.th/~somchai/spj/slides/171622/OHP2/04RPN.pdf)
[逆ポーランド記法変換](https://ynm.securesite.jp/app/math_rpn/index.html) (計算機)

☟ 解答例

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