Я проверил несколько рубиновых учебников онлайн, и они, казалось, использовали массив для всего. Итак, как я мог реализовать следующие структуры данных в Ruby?
- Стеки
- Очередь
- Связанные списки
- Карты
- Наборы
Я проверил несколько рубиновых учебников онлайн, и они, казалось, использовали массив для всего. Итак, как я мог реализовать следующие структуры данных в Ruby?
(Перенесено из комментария)
Ну, массив может быть стеком или очередью, ограничивая себя методами стека или очереди (push, pop, shift, unshift). Использование push/pop дает поведение LIFO (последний пришел первым вышел) (стек), а использование push/shift или unshift/pop дает поведение FIFO (очередь).
Карты - это хеши, а класс Set уже существует.
Вы можете реализовать связанный список, используя классы, но массивы будут давать поведение, подобное связному списку, используя стандартные методы массива.
Я предполагаю, что большая часть этого покрыта в ответах выше, но только для того, чтобы подвести итог для лучшего объяснения:
Стек:
stack = []
stack << 2 # push 2 => stack = [2]
stack << 3 # push 3 => stack = [2, 3]
stack.pop # pop => 3, stack = [2]
Очередь:
# 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
Связанный список:
# A very simple representation
class Node
attr_accessor :value, :next_node
def initialize(value, next_node=nil)
@value = value
@next_node = 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)
Карты:
# 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
Да, хотя это явно не указано. Класс Array
может использоваться как стек, очередь или связанный список. Например, push
и pop
заставляют его вести себя как стек. Ruby Map
- класс Hash
. Ruby также имеет класс Set
, хотя вам нужно импортировать модуль для его использования (require 'set'
).
Язык Ruby на самом деле имеет класс Queue, который можно использовать как.... ждать его... Queue;)
Это потокобезопасный и простой в использовании.
Остальная часть ответа @James великолепна и точна.
Я хотел бы добавить реализацию Deque (более общую для линейного использования DS) в 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
Выход:
[1, 2, 3, 4]
[-1, 0, 1, 2, 3, 4]
[-1, 0, 1, 2]
[1, 2]
1
2