스택 (Stack)

스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

 

단순히 생각하면 프링글스 통에 비유할 수 있는데, 바닥이 막혀있고 한쪽만 뚫려있는 구조라고 생각하면 된다.

 

바닥이 막혀있으니 과자를 넣을 때도 입구로 집어넣고, 뺄 때도 입구로 뺄 수 밖에 없다.

 

스택이 바로 이런 자료구조이다.

 

한쪽으로 넣고 뺄 수 밖에 없으므로 마지막에 넣은 것이 가장 먼저 나오게된다. 때문에

 

Last in First Out(LIFO)라고 한다.

 

 

 

---

연산

스택의 대표적인 연산들을 살펴보면, 아래와 같다.

• push: 스택에 자료를 넣는 연산.
• pop: 스택에서 자료를 빼는 연산
• top: 스택의 가장 위에 있는 자료를 보는 연산
• empty: 스택이 비어있는지 아닌지를 알아보는 연산
• size: 스택에 저장되어있는 자료의 개수를 알아보는 연산

---

구현

스택은 일차원 배열 하나로 구현할 수 있다. 구현 방법은 여러가지가 있겠지만 가장 단순한 배열로만 구현해보도록 하자.

 

위에서 설명한 연산들을 배열을 이용해서 구현하면 되는데, 대표적인 두가지 연산만 구현해보자.

 

정수형 데이터만 넣을 수 있는 스택을 구현한다 했을 때, 먼저 스택에 자료를 넣는 연산인 push를 구현해보자.

 

<push>

stack = [0] * 9999
size = 0


def push(data):
  stack[size] = data
  size += 1

push 연산은 단순히 배열에 데이터를 넣고, 사이즈를 1 증가시켜주면 된다.

 

다음은 스택에서 자료를 빼는 pop 연산을 구현해보자.

 

pop을 했을 때는 맨 위의 자료를 가져오는것이 아니라 해당 데이터를 삭제한다.

 

<pop>

def pop():
  statck[size-1] = 0
  size -= 1

데이터를 삭제해야 함으로 해당 인덱스의 데이터를 0으로 만들어주고 인덱스를 1개 내려주면 된다.

 

다른연산들도 push와 pop과 크게 다르지 않다.

 

파이썬은 리스트에서 제공하는 메서드를 조금만 이용하면 간단히 구현할 수 있을 것이다.

---

이렇게 스택은 맨 위에다가 뭘 쌓고 빼거나, 맨 위에 뭐가 있는지에만 관심을 가질 때 사용한다.

 

스택을 사용하는 대표적인 예시를 보자.

 

스택 자료구조를 이야기 할 때 빠지지 않는(?).. 단골인 괄호문제를 보자

 

https://www.acmicpc.net/problem/9012

9012번: 괄호

괄호

괄호 문자열은 다음 규칙으로 생성된다.

1. 빈 문자열, (), []은 괄호 문자열이다.
2. S, T가 괄호 문자열이면 ST도 괄호 문자열이다.
3. S가 괄호 문자열이면 (S), [S]도 괄호 문자열이다.

즉, 같은 종류로 열린 괄호가 있으면 닫히는 쌍도 있어야 올바른 괄호 문자열인것이다!

()[], (([][])), [[()()()]] ... 이런 괄호 문자열은 올바른 것으로 볼 수 있다.

 

반대로 닫히는 괄호 쌍이 없으면 틀린 문자열이다.

[(]], ([)), [[[[) ...

 

올바른 괄호 문자열을 판별하는 방법은 간단하다!

 

1. 여는 괄호(ex (, [ )가 나올 때마다 스택에 push 한다.

 

2-1. 닫는 괄호가 나오면 스택의 top과 비교하고, 종류가 맞는다면 스택에서 pop한다. 만약 종류가 맞지 않으면 올바르지 못한 문자열이다!

 

2-2. 만약 닫는 괄호를 비교할 때 스택이 비어있으면 안된다.

 

3. 1~2번 과정을 반복하고 마지막 문자열을 처리했는데, 스택에 비지 않으면 올바르지 못한 괄호 문자열이다!

 

 

2-2 의 경우, 만약 ]를 비교하려 하는데, 스택이 비어있다면 top을 할 수 없기 때문에 올바르지 못한 괄호 문자열이라는 것이다.

 

완성된 코드는 다음과 같다.

 

<코드>

# 괄호
import sys
k = int(sys.stdin.readline())

for _ in range(k):
    stack = []
    ps = sys.stdin.readline().rstrip()
    for c in ps:
        if c == '(':
            stack.append(c)
        else:
            if len(stack) != 0:
                stack.pop()
            else:
                stack.append('-1')
                break
    if len(stack) != 0:
        print('NO')
    else:
        print('YES')

 

---

이렇게 스택에 대해서 짧막하게 말해보았는데, 스택은 주로 훑어가는 방식과 많이 쓰인다. 배열을 for문을 두번써서 비교할

때는 시간복잡도가 많이 상승하므로, 원소를 스택에 넣고 배열의 다음 원소와 스택의 top을 비교할 때 효과적으로 사용할

수 있다.