Help us understand the problem. What is going on with this article?

アルゴリズムとデータ構造の要点メモ in ruby(キュー)

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f

参考

キュー(データ構造)

要点

キューは、一番最初に格納したデータからしか取り出せない

キューというデータ構造にとって、最低限必要な機能は以下のとおり

  • データを追加する (enqueue)
  • データを取り出す (dequeue)
  • キューが空かどうか調べる (is_empty)

実装

  • 配列で実現
  • enqueue, dequeue
  • is_emptyでキューが空かどうか確認
  • nextで次にdequeueされる値を取得
  • clearでキューを再作成
  • キューリストを取得
  • リングバッファ、"末尾の次は先頭" (tail+1)%max_size = front
  • キューが満杯の時に、配列サイズを倍にする
class Queue
  attr_reader :next, :queue, :front, :tail

  def initialize(size)
    @struct_nil = Struct.new("MyNil", :x)
    @size = size
    @queue = arr_new(@size)
    @front = 0
    @tail = 0
    @next = @queue[front]
  end

  def clear
    @queue = arr_new(@size)
  end

  def is_empty
    @front == @tail
  end

  def is_full
    (@tail + 1) % @size == @front
  end

  def enqueue(val)
    @queue[@tail] = val
    resize
    next_tail # 次のエンキューのためにポインタをずらす
  end

  def dequeue
    unless is_empty
      val = @queue[@front]
      @queue[@front] = mynil
      next_front
      @next = @queue[@front]
      val
    end
  end

private
  def resize
    if is_full
      @queue = @queue[@front..-1].concat(@queue[0..@tail]) if @front > @tail
      @front = 0
      @tail = @size - 1
      @queue.concat(arr_new(@size))
      @size = @queue.size
    end
  end

  def next_tail
    @tail = (@tail + 1 == @size)? 0 : @tail + 1
  end

  def next_front
    @front = (@front + 1 == @size)? 0 : @front + 1
  end

  def arr_new(size)
    Array.new(size, mynil)
  end

  def mynil
    @struct_nil.new(nil)
  end
end
irb(main):811:0> q = Queue.new(2)
(irb):748: warning: redefining constant Struct::MyNil
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=0, @tail=0, @next=#<struct Struct::MyNil x=nil>>
irb(main):812:0> q.dequeue
=> nil
irb(main):813:0> q.enqueue(1)
=> 1
irb(main):814:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[1, #<struct Struct::MyNil x=nil>], @front=0, @tail=1, @next=#<struct Struct::MyNil x=nil>>
irb(main):815:0> q.dequeue
=> 1
irb(main):816:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=1, @tail=1, @next=#<struct Struct::MyNil x=nil>>
irb(main):817:0> q.enqueue(2)
=> 0
irb(main):818:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[#<struct Struct::MyNil x=nil>, 2], @front=1, @tail=0, @next=#<struct Struct::MyNil x=nil>>
irb(main):819:0> q.enqueue(3)
=> 2
irb(main):820:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[2, 3, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=0, @tail=2, @next=#<struct Struct::MyNil x=nil>>
irb(main):821:0> q.enqueue(4)
=> 3
irb(main):822:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[2, 3, 4, #<struct Struct::MyNil x=nil>], @front=0, @tail=3, @next=#<struct Struct::MyNil x=nil>>
irb(main):823:0> q.dequeue
=> 2
irb(main):824:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[#<struct Struct::MyNil x=nil>, 3, 4, #<struct Struct::MyNil x=nil>], @front=1, @tail=3, @next=3>
irb(main):825:0> q.enqueue(5)
=> 0
irb(main):826:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[#<struct Struct::MyNil x=nil>, 3, 4, 5], @front=1, @tail=0, @next=3>
irb(main):827:0> q.enqueue(6)
=> 4
irb(main):828:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=8, @queue=[3, 4, 5, 6, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=0, @tail=4, @next=3>

感想

リングバッファ、ポインタが回るあたりで考慮するのがめんどくさかった。
あと、resizeがめんどくさかった。バグありそう

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away