Class: Containers::RubyDeque

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/containers/deque.rb

Overview

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.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(ary = []) ⇒ RubyDeque

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



17
18
19
20
21
22
 
# 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

Instance Method Details

#back ⇒ Object

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



60
61
62
 
# File 'lib/containers/deque.rb', line 60

def back
  @back && @back.obj
end

#clear ⇒ Object

Removes all the objects in the Deque.



30
31
32
33
 
# File 'lib/containers/deque.rb', line 30

def clear
  @front = @back = nil
  @size = 0
end

#each_backward ⇒ Object Also known as: reverse_each

Iterate over the Deque in LIFO order.



154
155
156
157
158
159
160
161
 
# 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 ⇒ Object Also known as: each

Iterate over the Deque in FIFO order.



143
144
145
146
147
148
149
150
 
# 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? ⇒ Boolean

Returns true if the Deque is empty, false otherwise.

Returns:

  • (Boolean) 


25
26
27
 
# File 'lib/containers/deque.rb', line 25

def empty?
  @size == 0
end

#front ⇒ Object

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



50
51
52
 
# File 'lib/containers/deque.rb', line 50

def front
  @front && @front.obj
end

#pop_back ⇒ Object

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



128
129
130
131
132
133
134
135
136
137
138
139
140
 
# 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 ⇒ Object

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



107
108
109
110
111
112
113
114
115
116
117
118
119
 
# 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) ⇒ Object

Adds an object at the back of the Deque.

d = Containers::Deque.new([1, 2, 3])
d.push_back(4)
d.pop_back #=> 4



87
88
89
90
91
92
93
94
95
96
97
98
 
# 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) ⇒ Object

Adds an object at the front of the Deque.

d = Containers::Deque.new([1, 2, 3])
d.push_front(0)
d.pop_front #=> 0



69
70
71
72
73
74
75
76
77
78
79
80
 
# 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 ⇒ Object Also known as: length

Return the number of items in the Deque.

d = Containers::Deque.new([1, 2, 3])
d.size #=> 3



39
40
41
 
# File 'lib/containers/deque.rb', line 39

def size
  @size
end