> 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/undefined.md).

# 큐

**큐(queue)**란 **FIFO**(First In First Out, 선입선출)의 특징을 가지는 자료구조입니다. 선입선출 즉, 먼저 들어온게 먼저 나갑니다. 터널을 연상합시다.

<figure><img src="/files/1JKFXgAI2bXiZxW5k4pq" alt=""><figcaption></figcaption></figure>

스택과는 다르게 양 쪽이 모두 열려 있습니다. 한 쪽에서만 삽입/삭제가 이루어졌던 스택과는 달리, 큐는 삽입과 삭제가 다른 쪽에서 일어납니다. \
한 쪽으로만 들어올 수 있다는 것은 스택과 동일하지만, 다른 쪽으로 나가야 한다는 것이 스택과 차별화된 큐만의 특징입니다. \
그렇기 때문에 **선입선출**이 가능한 것이죠.

스택과 마찬가지로 리스트와 덱(deque)으로 구현이 가능합니다.

## 큐의 삽입, 삭제

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

스택처럼 **append(값)과 pop()** 함수를 모두 사용할 수 있습니다.\
또한 스택과 다르게 전단(front) 삭제도 가능합니다. 이는 **pop(0)**&#xB97C; 사용하여 실행할 수 있습니다.

하지만 pop()과 달리 pop(0)은 '0'이라는 index를 지정해주는 과정이 있기에, 0번째 원소를 꺼낸 후 다시 List를 재정비해주는 과정이 필요하므로 **O(N)**&#xC758; 시간 복잡도를 가집니다.&#x20;

이 때 <mark style="background-color:yellow;">**deque**</mark>의 popleft()를 사용하면 **O(1)**&#xC758; 시간복잡도로 이를 해결할 수 있습니다. 그래서 queue를 구현할 때 List보다는 deque를 쓰는 것이 권장됩니다. 해당 개념은 다음 차시 덱에서 더 알아보기로 합시다.

## 연습문제

### BOJ 1966

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

문제를 읽어보면, 전단(front)에서 원소를 삭제해야 하기 때문에, 큐를 사용해야 합니다.\
하지만 삽입/삭제를 거치면서 원래 지정한 문서의 인덱스마저 바뀌게 됩니다.\
때문에, 중요도를 담은 배열 이외에 **다른 배열**을 하나 더 만들어서, 지정한 문서의 위치를 동시에 저장하는 방식으로 하시면 됩니다.

```python
li = list(map(int, input().split()))
check = [False for _ in range(n)]
check[m] = True
```

위와 같이 중요도를 담은 배열 **li**와, 궁금한 문서의 위치를 저장해줄 배열 check를 만들도록 합시다.\
check 배열의 원소를 모두 False로 만들되, 궁금한 문서는 True로 지정해줘야겠죠?\
while문을 돌다가, 리스트의 0번 인덱스의 값이 최댓값이면서 처음 지정한 문서일 때 반복문을 종료해주시면 됩니다.

```python
t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    li = list(map(int, input().split()))
    check = [False for _ in range(n)]
    check[m] = True
    cnt = 0
    while True:
        if li[0] == max(li):
            cnt += 1
            if check[0] == True:
                print(cnt)
                break
            else:
                li.pop(0)
                check.pop(0)
        else:
            li.append(li.pop(0))
            check.append(chk.pop(0))
```

위에서 말했듯이, 큐는 주로 덱으로 구현하기 때문에 개념적인 것을 이해한 후, 덱에 대해 더 자세히 학습하러 가봅시다 !

##