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

Algorithm Data structure queue

プログラミング

2019-11-17 15:30:27

概要

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

実装は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)]
}
  • 実装内容的にはスタックとほぼ同じ。スライスの添字アクセスが違うだけ。
  • ノート
    • Image from iOS

参考

About the author

Image

bmf san @bmf_san
A web developer in Japan.