¿Tiene Ruby contenedores como pilas, colas, listas de enlaces, mapas o conjuntos?

Question

Comprobé varios tutoriales de Ruby en línea y parecían utilizar una matriz para todo. Entonces, ¿cómo podría implementar las siguientes estructuras de datos en Ruby?

• Pilas
• Colas
• Las listas enlazadas
• Mapas
• Conjuntos

Answer 1

(Trasladado del comentario)

Bueno, una matriz puede ser una pila o cola limitando a sí mismo para apilar o métodos de cola (push, pop, turno, unshift). El uso de push/pop da el comportamiento LIFO (último en entrar, primero en salir), mientras que usar push/shift da el comportamiento FIFO (cola).

Los mapas son hashes, y ya existe una clase Set.

Puede implementar una lista vinculada utilizando clases, pero las matrices darán un comportamiento similar a la lista de enlaces utilizando los métodos de matriz estándar.

Answer 2

Sí, aunque no expresamente en nombre. La clase Array se puede usar como una pila, una cola o una lista vinculada. Por ejemplo, push y pop hacen que se comporte como una pila. Ruby's Map es la clase Hash. Ruby también tiene una clase Set, aunque debe importar un módulo para usarlo (require 'set').

Answer 3

El lenguaje Ruby tiene en realidad una clase Queue que puede ser utilizado como .... esperar a que ... una cola;)

Es hilo seguro y fácil de usar.

El resto de la respuesta de @James es excelente y precisa.

Answer 4

supongo que la mayoría de los que se trata en las respuestas anteriores, pero sólo para resumirlo para una mejor explicación:

Pila:

stack = [] 
stack << 2 # push 2 => stack = [2] 
stack << 3 # push 3 => stack = [2, 3] 
stack.pop # pop => 3, stack = [2] 

cola:

# we have a Queue class 
queue = Queue.new 
queue << 2 # push 2 => queue = [2] 
queue << 3 # push 3 => queue = [2, 3] (just a representation, it will be an object though) 
queue.pop # pop 2 

lista enlazada:

# A very simple representation 
class Node 
    attr_accessor :value, :next_node 

    def initialize(value, next_node=nil) 
    @value = value 
    @next = next_node 
    end 
end 

class LinkedList 

    def initialize(value) 
    @head = Node.new(value) 
    end 

    def add(value) 
    current = @head 
    while !current.next_node.nil? 
     current = current.next_node 
    end 
    current.next_node = Node.new(value) 
    end 
end 

ll = LinkedList.new 
ll.add(10) 
ll.add(20) 

Maps:

# Hash incase of ruby 
a = {} (or a = Hash.new) 
a['one'] = 1 # a = {"one"=>1} 
a['two'] = 2 # a = {"one"=>1, "two"=>2} 

Set:

# we have a Set class 
require 'set' 
s = Set.new   # <Set: {}> 
s.add(1)   # <Set: {1}> 
s.add(2)   # <Set: {1, 2}> 
s.add(1)   # <Set: {1, 2}> 
s.instance_of?(Set) # true 

Answer 5

me gustaría añadir aplicación deque (que es más genérico en el uso lineal DS) en Ruby:

class Node 
    attr_accessor :value, :next, :prev 
    def initialize(value, next_node, prev_node) 
    @value = value 
    @next = next_node 
    @prev = prev_node 
    end 
end 


class Deque 
    attr_accessor :start, :end 
    def initialize 
    @start = @end = nil 
    end 

    def push_back(val) 
    if @start.nil? 
     @start = @end = Node.new(val, nil, nil) 
    else 
     @end.next = Node.new(val, nil, @end) 
     @end.next.prev = @end 
     @end = @end.next 
    end 
    end 

    def pop_back 
    if @start == @end #only one node 
     @start = @end = nil 
    else 
     @end = @end.prev 
     @end.next = nil 
    end 
    end 

    def push_front(val) 
    @start.prev = Node.new(val, @start, nil) 
    @start = @start.prev 
    end 

    def pop_front 
    if @start == @end #only one node 
     @start = @end = nil 
    else 
     @start = @start.next 
     @start.prev.next = nil 
     @start.prev = nil 
    end 
    end 

    def empty? 
    @start.nil? && @end.nil? 
    end 

    def front 
    @start.value unless self.empty? 
    end 

    def back 
    @end.value unless self.empty? 
    end 

    def print(node) 
    arr = [] 
    while node 
     arr << node.value 
     node = node.next 
    end 
    p arr 
    end 
end 


q = Deque.new 
q.push_back(1) 
q.push_back(2) 
q.push_back(3) 
q.push_back(4) 
q.print(q.start) 
q.push_front(0) 
q.push_front(-1) 
q.print(q.start) 
q.pop_back() 
q.pop_back() 
q.print(q.start) 
q.pop_front() 
q.pop_front() 
q.print(q.start) 
p q.front 
p q.back 

Salida:

[1, 2, 3, 4] 
[-1, 0, 1, 2, 3, 4] 
[-1, 0, 1, 2] 
[1, 2] 
1 
2