【Goで学ぶコンピューターサイエンス】スタックとキュー

スタック (Stack)

スタックは LIFO (Last In First Out)、つまり「最後に入れたものが最初に取り出される」データ構造です。
お皿を積み重ねて、一番上に置いた皿を最初に取り出すようなイメージです。

使用例

• 関数呼び出しの管理 (コールスタック)
• Undo機能の実装

主な操作

• Push
  • データをスタックの一番上に追加する
• Pop
  • データをスタックの一番上から取得する

Goサンプルコード

package main

import "fmt"

// スタックの定義
type Stack struct {
	data []int
}

// データを追加
func (s *Stack) Push(value int) {
	s.data = append(s.data, value)
}

// データを取得
func (s *Stack) Pop() (int, bool) {
	if len(s.data) == 0 {
		// 空の場合
		return 0, false
	}
	value := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return value, true
}

func main() {
	stack := &Stack{}

	// データを追加
	stack.Push(10)
	stack.Push(20)
	stack.Push(30)

	// データを取得
	value, ok := stack.Pop()
	fmt.Println("Pop:", value, "result:", ok)
	value, ok = stack.Pop()
	fmt.Println("Pop:", value, "result:", ok)
	value, ok = stack.Pop()
	fmt.Println("Pop:", value, "result:", ok)
	value, ok = stack.Pop()
	fmt.Println("Pop:", value, "result:", ok)
}

Pop: 30 result: true
Pop: 20 result: true
Pop: 10 result: true
Pop: 0 result: false

キュー (Queue)

キューは FIFO (First In First Out)、つまり「最初に入れたものが最初に取り出される」データ構造です。
飲食店の待ち行列のようなもので、先頭の人から順番に呼ばれるイメージです。

使用例

• タスクスケジューリング
• メッセージキュー

主な操作

• エンキュー
  • データをキューの末尾に追加する
• デキュー
  • データをキューの先頭から取得する

Goサンプルコード

package main

import "fmt"

// キューの定義
type Queue struct {
	data []int
}

// データを追加
func (q *Queue) Enqueue(value int) {
	q.data = append(q.data, value)
}

// データを取得
func (q *Queue) Dequeue() (int, bool) {
	if len(q.data) == 0 {
        // 空の場合
		return 0, false
	}
	value := q.data[0]
	q.data = q.data[1:]
	return value, true
}

func main() {
	queue := &Queue{}

	// データを追加
	queue.Enqueue(10)
	queue.Enqueue(20)
	queue.Enqueue(30)

	// データを取得
	fmt.Println("Dequeue:", queue.Dequeue())
	fmt.Println("Dequeue:", queue.Dequeue())
	fmt.Println("Dequeue:", queue.Dequeue())
	fmt.Println("Dequeue:", queue.Dequeue())
}

Dequeue: 10 result: true
Dequeue: 20 result: true
Dequeue: 30 result: true
Dequeue: 0 result: false