読者です 読者をやめる 読者になる 読者になる

感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

キュー(Queue)の仕組みとデータ構造。

<スポンサーリンク>

キューとは

キューというのは、先入れ先出し(First In First Out)と呼ばれるデータ構造である
順番待ちの列を想像するといい。
キューにデータが追加されると、データはキューの最後尾に入る。
で、キューからデータが取り出される時は、キューの先頭から取り出される。

ラーメンを順番待ちして、先頭から入場していくような感じ。

リングバッファとは

キューを配列として扱うと、キューの位置がどんどん後ろにずれていってしまい、出したり入れたりを繰り返すと、いつの間にかキューの位置が一番後ろになってしまう。配列のインデックスがって意味でね。
で、それを解決するために考えられたのが「リングバッファ」
キューの末尾が配列の催行日に達してしまった場合は、配列の先頭に戻り、再びそこからデータを格納するというもの。
「一列」というか、「輪」になってるイメージだから、リングバッファという。

エンキューとは

エンキューとは、キューにデータを入れることをいう。
pushともいう。

デキューとは

でキュートは、キューからデータを読み出し&削除すること。
popともいう。

Rubyでキューのサンプルを作ってみる。

class IntQueue
  @size
  @queue
  @first
  @last
  attr_accessor:size
  attr_accessor:queue

  def initialize(size)
    @size = size
    @queue = Array.new(size)
    @first = 0
    @last = 0
  end

  def enqueue(val)
    puts 'エンキュー!:' + val.to_s
    if ((@last + 1) % @size == @first) then
      raise 'queue is full!'
    else
      @queue[@last] = val
      @last = (@last + 1) % @size
    end
  end

  def dequeue()
    puts 'デキュー!'
    @ret
    if (@first == @last)
      return -1
    else
      @ret = @queue[@first]
      @first = (@first + 1) % @size
      return @ret
    end
  end
end


queue = IntQueue.new(4)
puts 'キューのサイズは・・・'
puts queue.size()

queue.enqueue(15)
queue.enqueue(10)
queue.enqueue(20)
#queue.enqueue(30) #`enqueue': queue is full! (RuntimeError)というエラーが出る

puts 'デキュー!'
puts queue.dequeue()
puts queue.dequeue()
puts queue.dequeue()
#puts queue.dequeue() #-1が出てくる

結果はこうなる。

キューのサイズは・・・
4
エンキュー!:15
エンキュー!:10
エンキュー!:20
デキュー!
デキュー!
15
デキュー!
10
デキュー!
20

キューを出したり入れたりする場合

こんな感じで入れたり出したりしても、

queue = IntQueue.new(5)
puts 'キューのサイズは・・・'
puts queue.size()

queue.enqueue(15)
puts queue.dequeue()
queue.enqueue(10)
puts queue.dequeue()
queue.enqueue(20)
queue.enqueue(30)
queue.enqueue(40)
queue.enqueue(50)

puts queue.dequeue()
puts queue.dequeue()
puts queue.dequeue()
puts queue.dequeue()

結果は、

キューのサイズは・・・
5
エンキュー!:15
デキュー!
15
エンキュー!:10
デキュー!
10
エンキュー!:20
エンキュー!:30
エンキュー!:40
エンキュー!:50
デキュー!
20
デキュー!
30
デキュー!
40
デキュー!
50

ちゃんとキューを使える!

読んだ本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

感謝のプログラミング

今回で感謝のプログラミングは【616時間目】
10000時間まで、あと【9384時間】