[Python] Stack(스택) 과 Queue(큐) 정리 및 예제

자료구조를 공부하다 보면 반드시 배우는 개념이 Stack & Queue입니다.

# Stack

Stack은 선입 후출 방식으로 가장 나중에 들어오는 데이터를 제일 먼저 반환하는 방식입니다.

파이썬으로 구현하는 방법은 리스트에 자료를 넣고 빼는 방식으로 구현하면 되며 자료를 넣을 땐 append함수를 이용하면 리스트에 넣는 순서대로 데이터가 들어가기 때문에 간단히 구현할 수 있습니다.

Stack : Push

반대로 stack에서 데이터를 빼내는 과정은 가장 마지막 자료부터 빼야 합니다. 이때, 빼낸 자료는 리스트에 없어야 합니다.

이때 사용하는 함수는 pop 함수를 이용합니다.

Stack : pop

 

# Queue

다음으로 Queue는 Stack과는 다르게 선입선출 방식으로써 먼저 들어온 데이터를 먼저 처리하게 됩니다.

 

데이터를 넣는 방식은 Stack과 동일하지만, 빼내는 방식은 Stack과는 다릅니다.

Queue에서 데이터를 넣는 방식은 Enqueue라고 부르며, 반대로 데이터를 빼는 방식은 Dequeue라고 부릅니다.

Python에서 구현은 pop() 함수에 인자로 0을 넣은 pop(0)를 이용하여 구현할 수 있습니다.

# 정리

마지막으로 Stack과 Queue에서 자료가 어떻게 흘러가는지 정리하면 다음과 같습니다.

DataFlow

# Example

이를 이용한 예제 문제도 같이 알아보겠습니다.

문제 출처는 프로그래머스 코딩 테스트 연습문제에 있는 문제입니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

# 문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()"는 올바른 괄호입니다.
• ")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예)

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

# 예시 풀이

위 문제는 Stack 혹은 Queue를 이용하면 간단하게 해결할 수 있습니다.(조건에 문자열 s가 "(" 또는 ")"로만 이루어져 있기 때문)

괄호가 "()" 뿐만 아니라 "{}" 혹은 "[]" 등이 섞여서 주어지는 경우에는 Stack을 적용할 수 있습니다.(ex : [{()()}] / {((([))])}})

 

저는 괄호의 시작은 무조건 "("이며, 짝(")")이 없거나 ")"가 더 많은 경우(리스트가 비어있어서 pop을 할 수 없는 경우)에는 괄호가 올바르게 짝지어있지 않는 것이기 때문에 바로 False를 출력할 수 있도록 하였습니다.

또한, "("가 ")"보다 많은 경우 try~except는 통과할 수 있지만, 이러한 경우에는 리스트에 데이터가 남아있게 됩니다. 따라서 이를 방지하기 위해 for~else 구문을 사용하여 처리하였습니다.

def solution(s):

    #자료를 담을 리스트를 생성
    check = []
    
    for i in s:
        if i == "(":
            check.append(i)
        else:
            try:
                check.pop()
            except:
                return False
    else:
        if len(check) != 0:
            return False
        else:
            return True