스택

마치 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료 구조를 스택 (stack) 이라고 부릅니다. 이처럼 마지막에 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 스택을 다른 말로는 후입선출 (LIFO; last-in first-out) 자료 구조라고도 합니다.

스택에서 발생하는 오류

• 비어 있는 스택에서 데이터 원소를 꺼내려 할 때

  -> 스택 언더 플로우(Stack underflow)

• 꽉 찬 스택에 데이터 원소를 넣으려 할 때

  -> 스택 오버 플로우(Stack overflow)

연산

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

배열로 구현한 스택

위 연산 을 코드로 구현 하면 다음과 같다.

class ArrayStack:
    def __init__(self) -> None:
        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]

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

알고리즘 설계

수식을 왼쪽 부터 한 글자씩 읽어서

• 여는 괄호를 만나면: 스택에 푸시(=단기 저장)

• 닫는 괄호를 만나면:

  • 스택이 비어 있으면 올바르지 않은 수식
  • 스택에서 pop, 쌍을 이루는 여는 괄요인지 검사
    • 맞지 않으면 올바르지 않은 수식

• 끝까지 검사후, 스택이 비어 있어야 올바른 수식