I checked several Ruby tutorials online and they seemed to use array for everything. So how could I implement the following data structures in Ruby?
我在网上查看了几个Ruby教程，它们似乎对所有东西都使用数组。那么如何在Ruby中实现以下数据结构呢?
- Stacks
- 栈
- Queues
- 队列
- Linked lists
- 链表
- Maps
- 地图
- Sets
- 集
5 个解决方案
#1
72
(Moved from Comment)
(从评论)
Well, an array can be a stack or queue by limiting yourself to stack or queue methods (push, pop, shift, unshift). Using push / pop gives LIFO(last in first out) behavior (stack), while using push / shift gives FIFO behavior (queue).
好吧，数组可以是堆栈或队列，限制自己使用堆栈或队列方法(push、pop、shift、unshift)。使用push / pop给出LIFO(后进先出)行为(堆栈)，使用push / shift给出FIFO行为(队列)。
Maps are hashes, and a Set class already exists.
映射是散列，集合类已经存在。
You could implement a linked list using classes, but arrays will give linked-list like behavior using the standard array methods.
您可以使用类实现链表，但是数组将使用标准数组方法提供链表之类的行为。
#2
21
I guess most of it is covered in above answers but just for summing it up for a better explanation:
我猜上面的答案大部分都包含在内，只是为了更好地解释一下:
Stack:
栈:
stack = []
stack << 2 # push 2 => stack = [2]
stack << 3 # push 3 => stack = [2, 3]
stack.pop # pop => 3, stack = [2]
Queue:
队列:
# 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
Linked List:
链表:
# 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
#3
8
Yes, although not expressly in name. The Array class can be used as a stack, queue, or linked list. For example, push and pop make it behave like a stack. Ruby's Map is the Hash class. Ruby also has a Set class, although you have to import a module to use it (require 'set').
是的，虽然名义上不明确。数组类可以用作堆栈、队列或链表。例如，push和pop使其表现为堆栈。Ruby的映射是散列类。Ruby也有一个Set类，不过您必须导入一个模块才能使用它(需要' Set ')。
#4
3
The Ruby language actually has a Queue class which can be used as .... wait for it... a Queue ;)
Ruby语言实际上有一个队列类可以作为....等待……一个队列。
It is thread safe and easy to use.
螺纹安全，使用方便。
The rest of @James answer is great and accurate.
其余的@James的回答是伟大和准确的。
#5
0
I would like to add Deque implementation (which is more generic in linear DS usage) in Ruby :
我想在Ruby中添加Deque实现(在线性DS使用中更通用):
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
Output :
输出:
[1, 2, 3, 4]
[-1, 0, 1, 2, 3, 4]
[-1, 0, 1, 2]
[1, 2]
1
2
#1
72
(Moved from Comment)
(从评论)
Well, an array can be a stack or queue by limiting yourself to stack or queue methods (push, pop, shift, unshift). Using push / pop gives LIFO(last in first out) behavior (stack), while using push / shift gives FIFO behavior (queue).
好吧，数组可以是堆栈或队列，限制自己使用堆栈或队列方法(push、pop、shift、unshift)。使用push / pop给出LIFO(后进先出)行为(堆栈)，使用push / shift给出FIFO行为(队列)。
Maps are hashes, and a Set class already exists.
映射是散列，集合类已经存在。
You could implement a linked list using classes, but arrays will give linked-list like behavior using the standard array methods.
您可以使用类实现链表，但是数组将使用标准数组方法提供链表之类的行为。
#2
21
I guess most of it is covered in above answers but just for summing it up for a better explanation:
我猜上面的答案大部分都包含在内，只是为了更好地解释一下:
Stack:
栈:
stack = []
stack << 2 # push 2 => stack = [2]
stack << 3 # push 3 => stack = [2, 3]
stack.pop # pop => 3, stack = [2]
Queue:
队列:
# 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
Linked List:
链表:
# 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
#3
8
Yes, although not expressly in name. The Array class can be used as a stack, queue, or linked list. For example, push and pop make it behave like a stack. Ruby's Map is the Hash class. Ruby also has a Set class, although you have to import a module to use it (require 'set').
是的，虽然名义上不明确。数组类可以用作堆栈、队列或链表。例如，push和pop使其表现为堆栈。Ruby的映射是散列类。Ruby也有一个Set类，不过您必须导入一个模块才能使用它(需要' Set ')。
#4
3
The Ruby language actually has a Queue class which can be used as .... wait for it... a Queue ;)
Ruby语言实际上有一个队列类可以作为....等待……一个队列。
It is thread safe and easy to use.
螺纹安全，使用方便。
The rest of @James answer is great and accurate.
其余的@James的回答是伟大和准确的。
#5
0
I would like to add Deque implementation (which is more generic in linear DS usage) in Ruby :
我想在Ruby中添加Deque实现(在线性DS使用中更通用):
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
Output :
输出:
[1, 2, 3, 4]
[-1, 0, 1, 2, 3, 4]
[-1, 0, 1, 2]
[1, 2]
1
2