Class: Containers::Stack
- Inherits:
-
Object
- Object
- Containers::Stack
- Includes:
- Enumerable
- Defined in:
- lib/containers/stack.rb
Overview
A Stack is a container that keeps elements in a last-in first-out (LIFO) order. There are many
uses for stacks, including prefix-infix-postfix conversion and backtracking problems.
This implementation uses a doubly-linked list, guaranteeing O(1) complexity for all operations.
Instance Method Summary collapse
-
#each(&block) ⇒ Object
Iterate over the Stack in LIFO order.
-
#empty? ⇒ Boolean
Returns true if the stack is empty, false otherwise.
-
#initialize(ary = []) ⇒ Stack
constructor
Create a new stack.
-
#next ⇒ Object
Returns the next item from the stack but does not remove it.
-
#pop ⇒ Object
Removes the next item from the stack and returns it.
-
#push(obj) ⇒ Object
(also: #<<)
Adds an item to the stack.
-
#size ⇒ Object
Return the number of items in the stack.
Constructor Details
#initialize(ary = []) ⇒ Stack
Create a new stack. Takes an optional array argument to initialize the stack.
s = Containers::Stack.new([1, 2, 3])
s.pop #=> 3
s.pop #=> 2
16 17 18 |
# File 'lib/containers/stack.rb', line 16 def initialize(ary=[]) @container = Containers::Deque.new(ary) end |
Instance Method Details
#each(&block) ⇒ Object
Iterate over the Stack in LIFO order.
63 64 65 |
# File 'lib/containers/stack.rb', line 63 def each(&block) @container.each_backward(&block) end |
#empty? ⇒ Boolean
Returns true if the stack is empty, false otherwise.
58 59 60 |
# File 'lib/containers/stack.rb', line 58 def empty? @container.empty? end |
#next ⇒ Object
Returns the next item from the stack but does not remove it.
s = Containers::Stack.new([1, 2, 3])
s.next #=> 3
s.size #=> 3
25 26 27 |
# File 'lib/containers/stack.rb', line 25 def next @container.back end |
#pop ⇒ Object
Removes the next item from the stack and returns it.
s = Containers::Stack.new([1, 2, 3])
s.pop #=> 3
s.size #=> 2
45 46 47 |
# File 'lib/containers/stack.rb', line 45 def pop @container.pop_back end |
#push(obj) ⇒ Object Also known as: <<
Adds an item to the stack.
s = Containers::Stack.new([1])
s.push(2)
s.pop #=> 2
s.pop #=> 1
35 36 37 |
# File 'lib/containers/stack.rb', line 35 def push(obj) @container.push_back(obj) end |
#size ⇒ Object
Return the number of items in the stack.
s = Containers::Stack.new([1, 2, 3])
s.size #=> 3
53 54 55 |
# File 'lib/containers/stack.rb', line 53 def size @container.size end |