Class Containers::RubyDeque

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

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 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
17:   def initialize(ary=[])
18:     @front = nil
19:     @back = nil
20:     @size = 0
21:     ary.to_a.each { |obj| push_back(obj) }
22:   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
60:   def back
61:     @back && @back.obj
62:   end
clear ()

Removes all the objects in the Deque.

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

Alias for each_forward

each_backward () {|node.obj| ...}

Iterate over the Deque in LIFO order.

[show source]
     # File lib/containers/deque.rb, line 154
154:   def each_backward
155:     return unless @back
156:     node = @back
157:     while node
158:       yield node.obj
159:       node = node.left
160:     end
161:   end
each_forward () {|node.obj| ...}

Iterate over the Deque in FIFO order.

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

Returns true if the Deque is empty, false otherwise.

[show source]
    # File lib/containers/deque.rb, line 25
25:   def empty?
26:     @size == 0
27:   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
50:   def front
51:     @front && @front.obj
52:   end
length ()

Alias for size

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
128:   def pop_back
129:     return nil unless @back
130:     node = @back
131:     if @size == 1
132:       clear
133:       return node.obj
134:     else
135:       @back.left.right = nil
136:       @back = @back.left
137:     end
138:     @size -= 1
139:     node.obj
140:   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
107:   def pop_front
108:     return nil unless @front
109:     node = @front
110:     if @size == 1
111:       clear
112:       return node.obj
113:     else
114:       @front.right.left = nil
115:       @front = @front.right
116:     end
117:     @size -= 1
118:     node.obj
119:   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
87:   def push_back(obj)
88:     node = Node.new(nil, nil, obj)
89:     if @back
90:       node.left = @back
91:       @back.right = node
92:       @back = node
93:     else
94:       @front = @back = node
95:     end
96:     @size += 1
97:     obj
98:   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
69:   def push_front(obj)
70:     node = Node.new(nil, nil, obj)
71:     if @front
72:       node.right = @front
73:       @front.left = node
74:       @front = node
75:     else
76:       @front = @back = node
77:     end
78:     @size += 1
79:     obj
80:   end
reverse_each ()

Alias for each_backward

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
39:   def size
40:     @size
41:   end