1. 스택(Stack)

스택(stack:무더기, 쌓다, 채우다)은 그 의미와 같이 데이터를 쌓아올린 형태인데, 하나의 출입구를 통해서 데이터가 들어오고 나가는 구조의 형태를 띄고 있다. 그래서 먼저 들어온 데이터는 제일 늦게 나가게 되고 맨 마지막에 들어온 자료가 제일 먼저 나가게 된다. 예로 출퇴근 시간의 지하철은 사람이 가득차서 제일 늦게 탄 사람이 문 쪽에서 밖으로 자리를 비켜주지 않으면 먼저 탔던 사람이 나갈 수가 없는 구조와 같다. 이를 두고 후입선출(LIFO:Last In First Out) 구조라고 하며 그 반대의 구조인 선입선출(FIFO:First In First out) 구조로는 큐(Queue)가 있다.
파이썬에서 스택의 자료구조는 배열 순서에 따른 배열 리스트(Array list)와 논리 순서에 따른 연결 리스트(linked list) 두 가지로 활용되는데, 알고리즘 코딩테스트에서는 주로 배열 리스트(Array list)의 형식인 list 자료구조로 스택을 사용한다. 그래서 앞으로 스택 구조의 문제풀이는 리스트(list)로 사용하겠다.
list자료구조에서 스택으로 활용하려면 데이터의 입력과 출력은 제일 마지막 인덱스에서만 진행되도록 한다. 스택으로 활용될 때 입력은 'append(리스트 제일 뒤에 데이터 입력)', 출력은 'pop(리스트 제일 뒤의 데이터 출력)'을 사용한다.
실제로 어떻게 활용되는지 문제를 풀어보며 확인해보자.

2. 문제

문자와 괄호가 섞여있는 문자가 입력되면 괄호 안에 들어있지 않은 문자만 출력하는 프로그램을 완성하시오.
(괄호는 열었으면 반드시 닫았다는 전제를 가진다)
예) 입력 : (QO)D(A), 출력 : D
입력 : ((Z)OP(DL)A)D(W)I(DL(HV))K

3. 풀이

1. 스택으로 리스트 자료구조를 활용한다.
2. 문자열을 반복문으로 앞에서부터 순회하며 스택에 append를 하고, 닫는 괄호 ')'가 나온다면 여는 괄호 '('가 pop 될 때까지 pop을 한다.
   ')'가 반복문 변수에 할당되었다는 것은 앞에 여는 괄호 '('가 나왔다는 것이니 '(', ')' 사이의 문자도 제거해야 하기에 '('괄호까지 모두 pop을 한다.
3. 괄호를 빼내며 괄호 사이의 문자도 자연스럽게 빠져나오게 되고 스택에 남은 것은 괄호 안에 없었던 문자만 스택에 쌓여있어 스택(list)를 출력하면 된다.
   직접 풀어보도록 하자.

n = input()
stack = [] # 스택자료구조 생성
for i in n:
    if i == ')': # ')'가 할당 된 경우 : while문을 이용하여 '('가 나올 때까지 pop하여 제거한다.
        while True:
            p = stack.pop() # pop은 lsit 자료구조의 마지막 데이터를 빼서 변수에 할당할 수 있다.
            if p == '(':
                break
    else: # ')'가 아닌 경우 : 스택에 쌓는다
        stack.append(i)
for i in stack:
    print(i, end= ' ')
입력 : ((Z)OP(DL)A)D(W)I(DL(HV))K
출력 : D I K