Go to Qiita Advent Calendar Top
LoginSignup
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@miyyuk(miyyuk)in株式会社Link Sports

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

Last updated at Posted at 2021-04-18

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

【例】
入力 : 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 (検索アルゴリズム)**です。

6
5
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?