Class: Containers::Stack

Inherits:
Object
  • Object
show all
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

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.

Returns:

  • (Boolean) 


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