概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

スタック

• 常に最新のデータからしかアクセスできないようにデータを一列に並べた構造
  • LIFO(Last In First Out)
    • 後入れ先出し
• 常に最新のデータへアクセスしたいときに便利な構造
• データの追加をPush、削除をPopという。
  • 他にDup、Peek、Swap(またはExchange)、Rotateといった操作がある。
    • cf. Wikipedia - スタック

計算時間

配列や連結リストなど実装形式による。

実装

package main

// Stack is a stack.
type Stack struct {
    nodes []*Node
}

// Node is a item of a stack.
type Node struct {
    value string
}

// newStack create a Stack.
func newStack() *Stack {
    return &Stack{}
}

// push adds an node to the top of the stack.
func (s *Stack) push(n *Node) {
    s.nodes = append(s.nodes[:len(s.nodes)], n)
}

// pop removes an node from the top of the stack.
func (s *Stack) pop() {
    s.nodes = s.nodes[:len(s.nodes)-1]
}

• Goのスライスに慣れていれば難しいところは特にないはず
• ノート
  • 

参考

• Golang program for implementation LIFO Stack and FIFO Queue