Раздел «Язык Ruby».IsArrayLinearQueue:

Is Array good enough to be used as queue?

YES, it is:

QueueNode = Struct.new(:value, :prev, :next)

class MyQueue
  attr_accessor :first, :last, :size
  
  def initialize
    @first = @last = nil
    @size = 0
  end
  
  def push(a)
    new_last = QueueNode.new(a, @last, nil)
    @last.next = new_last if @last
    @last = new_last
    @size += 1
    self
  end
  
  def unshift(a)
    new_first = QueueNode.new(a, @last, nil)
    @first.prev = new_first if @first
    @first = new_first
    @size += 1
    self
  end
  
  def pop
    @last && (
      @size -= 1
      res = @last.value
      @last = @last.prev
      res
    )
  end
  
  def shift
    @first && (
      @size -= 1
      res = @first.value
      @first = @first.next
      res
    )
  end
end


if $0 == __FILE__
  require 'benchmark'
  Benchmark.bm do |b|
    [ 
      [[:unshift, 10000], [:pop, 10000/2]], 
      [[:push, 10000], [:shift, 10000/2]] 
    ].each do |cfg|
      [MyQueue.new, Array.new].each do |c|
        [100,200].each do |n|
          b.report("#{n}-#{c.class}:#{cfg.inspect}\n") do 
            n.times do |i|   
              cfg.each do |method, count|
                if c.method(method).arity == 1
                  count.times{|j| c.send(method, j)}
                else
                  count.times{ c.send(method) }
                end
              end
            end
          end
        end
      end
    end
  end 
end

artem@greck:~/ruby-samples$ multiruby queue_vs_array.rb 

VERSION = v1_9_1_0
CMD     = ~/.multiruby/install/v1_9_1_0/bin/ruby q.rb
user     system      total        real
100-MyQueue:[[:unshift, 10000], [:pop, 5000]]
1.840000   0.000000   1.840000 (  1.836684)
200-MyQueue:[[:unshift, 10000], [:pop, 5000]]
3.640000   0.000000   3.640000 (  3.634492)
100-Array:[[:unshift, 10000], [:pop, 5000]]
0.260000   0.000000   0.260000 (  0.259179)
200-Array:[[:unshift, 10000], [:pop, 5000]]
0.520000   0.000000   0.520000 (  0.529136)
100-MyQueue:[[:push, 10000], [:shift, 5000]]
1.870000   0.020000   1.890000 (  1.879077)
200-MyQueue:[[:push, 10000], [:shift, 5000]]
3.630000   0.030000   3.660000 (  3.654197)
100-Array:[[:push, 10000], [:shift, 5000]]
0.270000   0.000000   0.270000 (  0.272359)
200-Array:[[:push, 10000], [:shift, 5000]]
0.530000   0.000000   0.530000 (  0.535008)

RESULT = 0

TOTAL RESULT = 0 failures out of 2

Passed: v1_9_1_0
Failed: 

-- ArtemVoroztsov - 02 May 2009