(자료구조) 스택

1. 스택이란

- 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터구조 (LIFO)

 

2. 스택의 제약

- 데이터는 스택의 끝에만 삽입가능

- 데이터는 스택의 끝에서만 읽을 수 있다.

- 데이터는 스택의 끝에서만 삭제할 수 있다.

 

3. 스택의 활용

- 오래 사용할 데이터를 저장할 때는 일반적으로 스택을 사용하지 않지만 임시 데이터를 다뤄야 하는 알고리즘에서는 스택이 유용한 도구

- 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

 

4. 스택 예제

- 재귀함수가 대표적인 예제이다.

def recursive(data)
	if data < 0
     	puts "end"
    else
    	puts data
        recursive(data-1)
        puts "returned #{data}"
    end
end

 

5. 스택의 장단점

- 장점 : 구현이 쉽고 데이터 저장/읽기 속도가 빠르다

- 단점

• 데이터 최대 갯수를 미리 정해야 한다 (파이썬의 경우 재귀함수는 1000번까지만 호출 가능)
• 저장공간 낭비가 발생 (미리 최대갯수만큼 저장공간 확보해야되기 때문)

6. 괄호 문법 검사 코드 예제

- 괄호 문법 오류 3가지

• 오류타입1 : 여는 괄호는 있는데 대응하는 닫는 괄호 없는 경우
• 오류타입2 : 여는 괄호가 나오지 않았는데 닫는 괄호 나오는 경우
• 오류타입3 : 닫는 괄호가 바로 앞에 나온 여는 괄호와 종류가 다른 경우

- 규칙

• 괄호가 아닌 모든 문자는 무시하고 넘어감
• 여는 괄호가 나오면 스택에 푸시. 스택에 넣는다는 것은 이 괄호가 닫히기를 기다린다는 의미이다
• 닫는 괄호가 나오면 스택 확인. 그리고 아래와 같이 분석
  • 스택에 원소가 없으면 닫는 괄호에 대응하는 여는 괄호가 없는 것이다. 오류타입2이다.
  • 스택에 데이터가 있지만, 괄호 종류가 다르다. 오류타입3이다.
  • 닫는 괄호가 스택 위에 있는 원소와 괄호 종류와 같다면 여는 괄호를 성공적으로 닫았다는 뜻이다. 해당 원소를 스택에서 팝한다.
• 줄 끝에 도달했는데 스택에 여전히 남아있는 괄호가 있다면 닫는 괄호가 없다는 의미이다. 오류타입1이다.

- 코드예제

class Linter
  attr_reader :error

  def initialize
      @stack = []
  end

  def lint(text)
      text.each_char.with_index do |char, index|
          if opening_brace?(char)
              @stack.push(char)
          elsif closing_brace?(char)
              if closes_most_recent_opening_brace?(char)
                  # 닫는 괄호 문자가 가장 최근에 나온 여는 괄호를 닫았다면 스택에서 해당 괄호를 팝한다
                  @stack.pop
              else # 닫는 괄호문자가 가장 최근에 나온 여는 괄호를 닫지 않았다면
                  @error = "incorrect closing brace: #{char} at index #{index}"
                  return
              end
          end
      end

      if @stack.any?
          # 줄 끝에 도달했는데 스택이 비어있지 않다면 대응하는 닫는 괄호가 나오지 않은 여는 괄호가 있는 것
          @error = "#{@stack.last} does not have a closing brace"
      end
  end

  private

  def opening_brace?(char)
      ["(", "[", "{"].include?(char)
  end

  def closing_brace?(char)
      [")", "]", "}"].include?(char)
  end

  def opening_brace_of(char)
      {")"=>"(", "]"=>"[", "}"=>"{"}[char]
  end

  def most_recent_opening_brace
      @stack.last
  end

  def closes_most_recent_opening_brace?(char)
      opening_brace_of(char) == most_recent_opening_brace
  end

end

linter = Linter.new
lint.lint("(var x = {y: [1,2,3])}")
puts linter.error # Incorrect closing brace: ) at index 25


linter1 = Linter.new
lint1.lint("(var x = {y: [1,2,3])}")
puts linter1.error # ( does not have a closing brace

 

 

** 패스트캠퍼스의 '알고리즘/기술면접 완전 정복 올인원 패키지' 강의를 듣고 작성한 글입니다