概要

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

実装は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)]
}

• 実装内容的にはスタックとほぼ同じ。スライスの添字アクセスが違うだけ。
• ノート
  • 

参考

• flaviocopes.com - Go Data Structures: Queue
• Wikipedia - キュー)