[Coding Test][Python] Stack 개념, Stack 구현 및 예제

※ Stack 이란?

데이터를 선형으로 저장하는 자료 구조로 LIFO(Last In, First Out) 구조를 가진다.

Stack 주요 연산

• Push : Stack의 맨 위(Top)에 데이터 삽입
• Pop : Stack의 맨 위(Top)에 있는 데이터 제거하고 return
• Top : Stack의 맨 위(Top)에 있는 데이터를 조회

Stack 활용 사례

• 재귀 함수 처리
• 괄호 매칭
• DFS
• 문자열 뒤집기
• 등등

1. Stack  구현

Stack은 Python에 특별한 라이브러리가 존재하지 않고 List를 Stack으로 사용한다.

아래 코드에서는 Stack Class를 정의하여 사용하였지만 바로 List에 적용하면 된다.

class Stack(object):
    def __init__(self):
        self.list = []

    # O(1) : 맨 뒤에 append
    def push(self, val):
        self.list.append(val)
        
    # O(1) : 맨 뒤에 pop
    def pop(self):
        return self.list.pop()
    
    def top(self):
        return self.list[-1]

    def is_empty(self):
        return True if len(self.list)==0 else False

    def size(self):
        return len(self.list)

 

s = Stack()

print(s.is_empty())

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

print(s.pop())
print(s.pop())
print(s.pop())

print(s.top())

print(s.is_empty())

True
5
4
3
2
False

2. Stack을 이용한 문제 풀이

Valid Parentheses
'(), {}, []'를 포함하고 있는 문자열 s가 주어졌을 때, 괄호가 유효한지 아닌지를 판별하시오       

----- 제약조건 ------
$1 <= s.length <= 10^4$
문자열 s는 '(), {}, []'의 괄호 들로만 구성되어 있다     

def valid_parentheses(data):
    stack = list()
    
    for p in data:
        if p == "(":
            stack.append(")")
        elif p == "{":
            stack.append("}")
        elif p == "[":
            stack.append("]")
        elif not stack or stack.pop() != p:
            return False
    # not stack : stack이 비어있으면 True, 비어있지 않으면 False
    return not stack

 

아래의 코드는 괄호가 열릴 때( "(", "{", "[") Stack에 닫히는 괄호를 넣어주게 됩니다.

if p == "(":
    stack.append(")")
elif p == "{":
    stack.append("}")
elif p == "[":
    stack.append("]")

 

그리고 Input p가 닫힌 괄호(")", "}", "]")일 때 stack의 pop을 하여 같은지 확인합니다.

즉, 괄호의 쌍이 맞아지는지 확인하게 됩니다.

이 조건을 중족하기 않으면 제대로 된 괄호 매칭이 되지 않은 것이므로 False를 반환합니다.

elif not stack or stack.pop() != p:
            return False