> For the complete documentation index, see [llms.txt](https://koalas-organization.gitbook.io/koala_codingtest_study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koalas-organization.gitbook.io/koala_codingtest_study/data_structure/stack.md).

# 스택

**스택(stack)**이란 **LIFO**(Last In First Out, 후입선출)의 특징을 가지는 자료구조입니다. 후입선출 즉, 나중에 들어온 것이 먼저 나갑니다. 바구니를 연상합시다.

그렇다면 아래 그림을 봅시다. 1, 2, 3을 순서대로 넣은 후, 1을 빼내고 싶을 땐 어떻게 해야할까요?

<figure><img src="/files/UYjDmjTt5gOymQjAYJpj" alt=""><figcaption></figcaption></figure>

어쩔 수 없이 3과 2를 차례로 뺀 후에야 1을 빼낼 수 있습니다.  \
이것이 바로 스택입니다. 가장 나중에 들어온 3이 가장 먼저 나가는 후입선출의 구조죠.\
나갈 구멍이 한 쪽밖에 없다고 생각하시면 편합니다.

스택은 리스트로 구현할 수 있고, 내장 함수를 사용하여 쉽게 삽입/반환 등의 연산을 할 수 있습니다.

```python
li = []
li.append(1)    # li == [1]
li.append(2)    # li == [1, 2]
li.pop()        # li == [1]
li.pop()        # li == []
```

**append(값)**&#xC740; 원소 삽입 시에, **pop()**&#xC740; 반환 시에 사용하는 함수입니다.\
이 두 함수를 사용하여 문제를 풀어보도록 합시다.

## 연습문제

### BOJ 1874

{% embed url="<https://www.acmicpc.net/problem/1874>" %}

처음에 배열에 들어갈 원소를 하나씩 입력받게 됩니다. \
입력받을 때마다 원소를 어떻게 처리할지 판단하는 방식으로 진행해보도록 하겠습니다.

```python
li = []      
ans = []    # '+', '-'를 담을 배열
cnt = 0
flag = True # 불가능한 경우를 위한 flag
```

li 배열을 사용하여 문제의 과정을 진행하고, ans 배열은 삽입/삭제의 여부에 따라 '+', '-' 기호를 넣어줄 용도로 사용합니다.

입력받은 수열을 만들어 낼 수 없을 때 flag를 통해 예외처리를 해줄 예정입니다.

```python
n = int(input())
li = []     
ans = []    
cnt = 0
flag = True
for _ in range(n):
    val = int(input())

    while cnt < val:
        cnt += 1
        li.append(cnt)
        ans.append('+')
    if li[-1] == val:
        li.pop()
        ans.append('-')
    else:
        flag = False
        break

if flag == True:
    print('\n'.join(ans))
else:
    print('NO')
```

cnt 변수는 append() 할지 말지를 결정하는 지표가 됩니다.

입력값이 나올 때까지 수를 삽입하다가, 그 수가 나오면 삭제하는 과정을 반복하면 됩니다.

## 풀어볼 문제

스택의 성질을 응용해서 아래의 문제들을 풀어봅시다 !

{% embed url="<https://school.programmers.co.kr/learn/courses/30/lessons/12909>" %}
\[프로그래머스] 올바른 괄호
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/17298>" %}
\[백준] 오큰수
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/12789>" %}
\[백준] 도키도키 간식드리미&#x20;
{% endembed %}