프로그래머스 강의_11

스택(stack)

1. 자료(data)를 보관할 수 있는 (선형) 구조
2. 단, 넣을 때에는 한 쪽 끝에서 밀어넣어야 하고 => 푸시(push) 연산
3. 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 => 팝(pop) 연산
4. 후입선출(LIFO-Last-In First-Out) 특징을 가지는 선형 자료구조

스택의 동작

• 초기 상태 : 비어있는 스택(empty stack)
• S = Stack()
• S.push(A)
• S.push(B)
• r1. = S.pop() ===> B
• r2. = S.pop() ===> A
• 오류 : r3. = S.pop() 비어있는 스택에서 데이터 원소를 꺼내려 할때
  ===> 스택 언더 플로우(stack underflow)
• 오류 : 꽉 찬 스택에 데이터 원소를 넣으려 할 때
  ===> 스택 오버플로우(stack overflow)

스택의 추상적 자료구조 구현

1. 배열 ( array ) 을 이용하여 구현

• Python 리스트와 메서드들을 이용

2. 연결 리스트 ( linked list ) 를 이용하여 구현

• 양방향연결리스트 사용

3. 연산의 정의

• size() : 현재 스택에 들어있는 데이터 원소의 수를 구함
• isEmpty() : 현재 스택이 비어있는지를 판단
• push(x) : 데이터 원소 x를 스택에 추가
• pop() : 스택의 맨 위에 저장된 데이터 원소를 제거( 또한, 반환 )
• peek() : 스택의 맨 위에 저장된 데이터 원소를 반환( 제거하지 않음 )

배열로 구현한 스택

class ArrayStack :
    def __init__(self) :
        self.data = []
    ## 스택의 크기를 리턴
    def size(self):
        return len(self.data)
    ## 스택이 비어있는지 판단
    def isEmpty(self):
        return self.size() == 0
    ## 데이터 원소를 추가
    def push(self, item):
        self.data.append(item)
    ## 데이터 원소를 삭제(리턴)
    def pop(self):
        return self.data.pop()
    ## 스텍의 꼭대기 원소 반훤
    def peek(self):
        return self.data[-1]

from pythondes.basic.stack import Stack 이미 만들어진 스택모듈 사용 가능하다.

연습 문제 - 수식의 괄호 유효성 검사

올바른 수식 :

• ( A + B )
• { ( A + B ) * C }
• [ ( A + B ) * ( C + D ) ]

알고리즘 설계 - 수식을 왼쪽부터 한 글자씩 읽어서 :

• 여는 괄호 - ( 또는 { 또는 [ 를 만나면 스택에 푸시
• 닫는 괄호 - ) 또는 } 또는 ] 를 만나면 :
  스택이 비어있으면 올바르지 않은 수식
  스택에서 pop, 쌍을 이루는 여는괄호인지 검사
  맞지 않으면 올바르지 않은 수식
  ==> 끝까지 검사한 후 , 스택이 비어있어야 올바른 수식이다.

  def solution(expr):
      match = {
          ')': '(',
          '}': '{',
          ']': '['
      }
      S = ArrayStack()
      for c in expr:
          if c in '({[':
              S.push(c)
          elif c in match:
              if S.isEmpty():
                  return False
              else:
                  t = S.pop()
                  if t != match[c]:
                      return False
      return S.isEmpty()