class Containers::RubyDeque

  1. lib/containers/deque.rb
Parent: Containers

A Deque is a container that allows items to be added and removed from both the front and back, acting as a combination of a Stack and Queue.

This implementation uses a doubly-linked list, guaranteeing O(1) complexity for all operations.

Included modules

  1. Enumerable

Constants

Node = Struct.new(:left, :right, :obj)  

Public Instance Aliases

each -> each_forward
length -> size
reverse_each -> each_backward

Public Class methods

new (ary=[])

Create a new Deque. Takes an optional array argument to initialize the Deque.

d = Containers::Deque.new([1, 2, 3])
d.front #=> 1
d.back #=> 3
[show source] 
# File lib/containers/deque.rb, line 17
def initialize(ary=[])
  @front = nil
  @back = nil
  @size = 0
  ary.to_a.each { |obj| push_back(obj) }
end

Public Instance methods

back ()

Returns the object at the back of the Deque but does not remove it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.back #=> 1
[show source] 
# File lib/containers/deque.rb, line 60
def back
  @back && @back.obj
end
clear ()

Removes all the objects in the Deque.

[show source] 
# File lib/containers/deque.rb, line 30
def clear
  @front = @back = nil
  @size = 0
end
each_backward ()

Iterate over the Deque in LIFO order.

[show source] 
# File lib/containers/deque.rb, line 154
def each_backward
  return unless @back
  node = @back
  while node
    yield node.obj
    node = node.left
  end
end
each_forward ()

Iterate over the Deque in FIFO order.

[show source] 
# File lib/containers/deque.rb, line 143
def each_forward
  return unless @front
  node = @front
  while node
    yield node.obj
    node = node.right
  end
end
empty? ()

Returns true if the Deque is empty, false otherwise.

[show source] 
# File lib/containers/deque.rb, line 25
def empty?
  @size == 0
end
front ()

Returns the object at the front of the Deque but does not remove it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.front #=> 2
[show source] 
# File lib/containers/deque.rb, line 50
def front
  @front && @front.obj
end
pop_back ()

Returns the object at the back of the Deque and removes it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.pop_back #=> 1
d.size #=> 1
[show source] 
# File lib/containers/deque.rb, line 128
def pop_back
  return nil unless @back
  node = @back
  if @size == 1
    clear
    return node.obj
  else
    @back.left.right = nil
    @back = @back.left
  end
  @size -= 1
  node.obj
end
pop_front ()

Returns the object at the front of the Deque and removes it.

d = Containers::Deque.new
d.push_front(1)
d.push_front(2)
d.pop_front #=> 2
d.size #=> 1
[show source] 
# File lib/containers/deque.rb, line 107
def pop_front
  return nil unless @front
  node = @front
  if @size == 1
    clear
    return node.obj
  else
    @front.right.left = nil
    @front = @front.right
  end
  @size -= 1
  node.obj
end
push_back (obj)

Adds an object at the back of the Deque.

d = Containers::Deque.new([1, 2, 3])
d.push_back(4)
d.pop_back #=> 4
[show source] 
# File lib/containers/deque.rb, line 87
def push_back(obj)
  node = Node.new(nil, nil, obj)
  if @back
    node.left = @back
    @back.right = node
    @back = node
  else
    @front = @back = node
  end
  @size += 1
  obj
end
push_front (obj)

Adds an object at the front of the Deque.

d = Containers::Deque.new([1, 2, 3])
d.push_front(0)
d.pop_front #=> 0
[show source] 
# File lib/containers/deque.rb, line 69
def push_front(obj)
  node = Node.new(nil, nil, obj)
  if @front
    node.right = @front
    @front.left = node
    @front = node
  else
    @front = @back = node
  end
  @size += 1
  obj
end
size ()

Return the number of items in the Deque.

d = Containers::Deque.new([1, 2, 3])
d.size #=> 3
[show source] 
# File lib/containers/deque.rb, line 39
def size
  @size
end