Class: Containers::RubyDeque
- Inherits:
-
Object
- Object
- Containers::RubyDeque
- 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
-
#back ⇒ Object
Returns the object at the back of the Deque but does not remove it.
-
#clear ⇒ Object
Removes all the objects in the Deque.
-
#each_backward ⇒ Object
(also: #reverse_each)
Iterate over the Deque in LIFO order.
-
#each_forward ⇒ Object
(also: #each)
Iterate over the Deque in FIFO order.
-
#empty? ⇒ Boolean
Returns true if the Deque is empty, false otherwise.
-
#front ⇒ Object
Returns the object at the front of the Deque but does not remove it.
-
#initialize(ary = []) ⇒ RubyDeque
constructor
Create a new Deque.
-
#pop_back ⇒ Object
Returns the object at the back of the Deque and removes it.
-
#pop_front ⇒ Object
Returns the object at the front of the Deque and removes it.
-
#push_back(obj) ⇒ Object
Adds an object at the back of the Deque.
-
#push_front(obj) ⇒ Object
Adds an object at the front of the Deque.
-
#size ⇒ Object
(also: #length)
Return the number of items in the Deque.
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.
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 |