Ruby에는 스택, 대기열, 연결 목록, 맵 또는 세트와 같은 컨테이너가 있습니까?

Ruby에는 스택, 대기열, 연결 목록, 맵 또는 세트와 같은 컨테이너가 있습니까?

---

온라인에서 여러 루비 튜토리얼을 확인했는데 모든 것에 배열을 사용하는 것 같았습니다. 그렇다면 Ruby에서 다음 데이터 구조를 어떻게 구현할 수 있습니까?

• 스택
• 대기열
• 연결된 목록
• 지도
• 세트

---

(댓글에서 이동)

음, 배열은 스택 또는 큐 메서드 (push, pop, shift, unshift)로 제한하여 스택 또는 큐가 될 수 있습니다. push / pop을 사용하면 LIFO (last in first out) 동작 (스택)이 제공되고 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}

세트:

# 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 's Map는 Hash클래스입니다. 루비에도 Set클래스가 있지만 사용하려면 모듈을 가져와야합니다 ( require 'set').

---

Ruby 언어에는 실제로 사용할 수 있는 Queue 클래스가 있습니다. .... wait for it ... a Queue;)

스레드 안전하고 사용하기 쉽습니다.

나머지 @James 답변은 훌륭하고 정확합니다.

---

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

출력 :

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

참조 URL : https://stackoverflow.com/questions/5006395/does-ruby-have-containers-like-stacks-queues-linked-lists-maps-or-sets