概要
アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。
実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。
キュー
- 常に先に追加されたデータからしかアクセスできないようにデータを一列に並べた構造
- スタックとは追加と削除の方向が逆になる。
- FIFO(First In First Out)
- 先入れ先出し
- 待ち行列ともいう。
- データの追加をenqueue、削除をdequeueという。
計算時間
配列や連結リストなど実装形式による。
実装
package main
// Queue is a queue.
type Queue struct {
nodes []*Node
}
// Node is a item of a stack.
type Node struct {
value string
}
// newQueue create a Stack.
func newQueue() *Queue {
return &Queue{}
}
// enqueue adds an node to the end of the queue.
func (s *Queue) enqueue(n *Node) {
s.nodes = append(s.nodes, n)
}
// dequeue removes an node from the top of the queue.
func (s *Queue) dequeue() {
s.nodes = s.nodes[1:len(s.nodes)]
}
- 実装内容的にはスタックとほぼ同じ。スライスの添字アクセスが違うだけ。
- ノート
