스택이란?

STACK(스택)

• First in Last Out
• Last In First Out
• 이해하기 쉽게 설명하자면, 컴퓨터의 ctrl+z 기능입니다

관련 함수

push()
pop()

스택 구현

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        self.top = Node(value, self.top)

    def pop(self):
        if not self.top:
            return None
        node = self.top
        self.top = node.next
        return node.value

    def is_empty(self):
        return self.top is None

• push
  : self.top을 Node의 value로 추가하고, next로 연결될 값을 현재 self.top으로 지정합니다.
• pop
  : self.top이 없다면, None을 반환하고,
  : 존재한다면, 현재 self.top을 node에 넣고, node의 value를 반환합니다.
  : 그와 동시에, self.top을 현재 노드의 next로 변경해야 합니다.
• is_empty
  : self.top이 존재하지 않는다면, True를 반환합니다.

여닫는 괄호 문제를 스택으로 풀어보자

def test_problem_stack(s):
    # 여는 괄호가 stack에 추가되고, 닫는 괄호가 나오면 stack에서 마지막 요소를 꺼내 비교합니다.
    # stack이 비어 있으면, 현재 닫는 괄호에 맞는 여는 괄호가 없다는 의미이므로 False를 반환해야 합니다.
    stack = []
    pair = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            if len(stack) == 0:
                # 문자열이 ")"로 시작한다면, 스택에는 아무 것도 없지만 닫는 괄호가 나왔으므로, stack.pop()을 실행하면 에러가 발생
                # 이를 방지하려면 스택이 비어 있는지 먼저 확인
                return False
            top = stack.pop()
            if pair[char] != top:
                return False
    return len(stack) == 0

• 여는 괄호가 stack에 추가되고, 닫는 괄호가 나오면 stack에서 마지막 요소를 꺼내 비교합니다.
• stack이 비어 있으면, 현재 닫는 괄호에 맞는 여는 괄호가 없다는 의미이므로 False를 반환해야 합니다.
• 핵심 포인트는 pair 딕셔너리입니다.
• pair[닫는괄호타입] = 여는 괄호 타입 을 이용합니다.

테스트 케이스

• 앞의 두 예제에 대한 테스트 케이스는 다음과 같습니다.

def test_stack():
    stack = Stack()

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    assert stack.pop() == 5
    assert stack.pop() == 4
    assert stack.pop() == 3
    assert stack.pop() == 2
    assert stack.pop() == 1
    assert stack.pop() is None
    assert stack.is_empty()


assert test_problem_stack("()")
assert test_problem_stack("()[]{}")
assert test_problem_stack("({[][]})")
assert test_problem_stack("({[]})")
assert not test_problem_stack("(]")
assert not test_problem_stack("(()]")
assert not test_problem_stack("(((])")
assert not test_problem_stack("((())")