アルゴリズムとデータ構造 - スタック

アルゴリズムとデータ構造

概要

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

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

スタック

  • 常に最新のデータからしかアクセスできないようにデータを一列に並べた構造
    • LIFO(Last In First Out)
      • 後入れ先出し
  • 常に最新のデータへアクセスしたいときに便利な構造
  • データの追加をPush、削除をPopという。

計算時間

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

実装

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のスライスに慣れていれば難しいところは特にないはず
  • ノート
    • Image from iOS (1)

参考


関連書籍