Class: Rivulet::Deque

Inherits:
Object
  • Object
show all
Defined in:
lib/rivulet/deque.rb

Overview

A double-ended queue with O(1) push/pop at both ends. Backed by a growing array with a front index; no element is ever shifted.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Deque

Returns a new instance of Deque.



7
8
9
10
 
# File 'lib/rivulet/deque.rb', line 7

def initialize
  @data  = []
  @front = 0
end

Instance Method Details

#any? ⇒ Boolean

Returns:

  • (Boolean) 


24
 
# File 'lib/rivulet/deque.rb', line 24

def any?      = @front < @data.size

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


25
 
# File 'lib/rivulet/deque.rb', line 25

def empty?    = @front >= @data.size

#first ⇒ Object 



22
 
# File 'lib/rivulet/deque.rb', line 22

def first     = @data[@front]

#last ⇒ Object 



23
 
# File 'lib/rivulet/deque.rb', line 23

def last      = @data.last

#pop ⇒ Object 



14
15
16
 
# File 'lib/rivulet/deque.rb', line 14

def pop
  @data.pop unless empty?
end

#push(val) ⇒ Object 



12
 
# File 'lib/rivulet/deque.rb', line 12

def push(val) = @data.push(val)

#shift ⇒ Object 



18
19
20
 
# File 'lib/rivulet/deque.rb', line 18

def shift
  @front += 1 unless empty?
end