Ruby是否具有堆棧，隊列，鏈接列表，映射或集合等容器？

Question

我在網上查了幾篇Ruby教程，看起來他們都用數組。那麼我怎麼能在Ruby中實現以下數據結構？

• 棧
• 隊列
• 鏈表
• 地圖
• 集

Answer 1

（來自評論移動）

好，陣列可以通過限制自己堆疊或隊列的方法（壓入，彈出，移位不印字）是一個堆棧或隊列。使用push/pop可以給出LIFO（後進先出）行爲（堆棧），而使用push/shift可以給出FIFO行爲（隊列）。

地圖是hashes，並且Set類已經存在。

您可以使用類實現鏈表，但數組將使用標準數組方法給出鏈表類行爲。

Answer 2

是的，雖然沒有明確的名字。 Array類可以用作堆棧，隊列或鏈接列表。例如，push和pop使其表現得像一個堆棧。 Ruby的Map是Hash類。 Ruby還有一個Set類，但您必須導入一個模塊才能使用它（require 'set'）。

Answer 3

Ruby語言實際上有一個Queue類可用作....等待...隊列;）

它是線程安全的，易於使用。

@James的其餘部分的答案是偉大的和準確的。

Answer 4

我想大部分是覆蓋在上面的答案，但只是爲了總結起來爲一個更好的解釋：

堆棧：

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 = 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} 

集：

# 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

我想補充的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