[프로그래머스 알고리즘] 11강: 스택 (Stacks)

스택 (Stacks)

한 쪽 끝에서 데이터를 push 하거나 pop해야한다.

즉, 후입선출 (LIFO : Last In First Out) 특징을 가지는 선형 자료구조

 

스택에서 발생하는 오류

• 비어있는 스택에서 데이터 원소를 꺼내려 할 때 : Stack underflow
• 꽉 찬 스택에 데이터 원소를 넣으려 할 때 : Stack overflow라고 부름

 

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

1. 배열
   • Python 리스트와 메서드를 이용해 구현
2. 연결리스트
   • 양방향 연결리스트를 이용해 구현

 

연산의 정의

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

 

11강 과제: 수식의 괄호 검사

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]


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()