1️⃣ 큐
큐는 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한된 자료구조 입니다.
하지만 스택과 차이점이라면 스택이 한곳에서만 들어가고 나가는 작업을 한다면, 큐는 들어가는 곳과 나가는 곳이 따로 존재합니다.
이러한 자료구조를 FIFO(First In First Out) 자료구조 라고 합니다. 먼저 들어간 데이터가 먼저 나온다는 뜻입니다.
그림으로 보면 다음과 같습니다.
보통 큐에서는 삽입 연산을 push라고 하고 삭제 연산을 pop 이라고 합니다.
또한 큐의 가장 앞의 데이터를 front 가장 뒤의 데이터를 rear라고 부르기도 합니다.
2️⃣ 큐의 구현과 종류
파이썬에서는 보통 모듈을 사용하여 큐를 사용합니다.
queue 모듈과 deque 모듈이 있지만 queue 모듈은 멀티 쓰레딩을 가능하게 만들어져서 속도가 많이 느립니다.
따라서 deque모듈을 사용하는 것이 알고리즘을 풀 때는 매우 유용합니다.
1
2
3
4
5
6
from collections import deque
q = deque()
q.append(1) # 푸시 연산
q.popleft() # 팝 연산
보통 위와 같이 구현합니다.
큐의 종류는 크게 세가지로 나눌 수 있습니다.
- 일반적인 선형 큐 : 이 큐는 앞서 말한 큐의 개념과 동일합니다.
- 원형 큐 : 일반 큐의 단점은 큐에 빈 메모리가 남아도, 꽉 차있다고 판단하여 삽입을 거부하는 경우가 있습니다. 이를 개선하기 위해 만들어진 것이 바로 원형 큐 입니다.
- 덱 : deque라고 불리는 이 큐는 스택과 큐를 합쳐놓은 것으로써 양쪽에서 삽입과 삭제가 둘다 가능한 유연한 자료구조 입니다.
3️⃣ 큐의 시간복잡도
큐도 스택과 동일한 시간복잡도를 갖습니다.
대표적으로 삽입, 삭제, 검색 연산이 있습니다.
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| 삽입 | O(1) | 큐의 맨뒤에 바로 넣으면 되어서 O(1)의 시간복잡도가 소요됩니다. |
| 삭제 | O(1) | 큐의 맨앞의 원소를 바로 떼어버리면 되므로 O(1)의 시간복잡도가 소요됩니다. |
| 검색 | O(n) | 큐의 처음부터 찾으면서 검색을 해야하기때문에 최악 O(n)의 시간복잡도가 소요됩니다. |
4️⃣ 큐의 활용
큐가 실생활의 어느 부분에서 이용되는지 확인해보도록 하겠습니다.
- 운영체제의 작업 큐: 보통 운영체제가 스케줄링 큐나 프린터 버퍼 큐를 사용할 때 큐를 많이 사용한다고 합니다. 순서대로 실행되어야 하는 일련의 작업들이 있다면 먼저 실행한것을 끝나고 다음 작업을 실행할 때 큐를 사용합니다.
- 대기 줄 : 예를들어, 공항의 입국심사를 받는 것도 일종의 큐라고 볼 수 있습니다. 줄을 대기할 때 한사람이 끝나고 다음사람이 심사를 받기 때문입니다.
- 수학적인 시뮬레이션 : 시뮬레이션도 일종의 큐입니다. 앞의 작업들이 실행되야만 진행이 가능한 시뮬레이션도 일종의 큐라고 볼 수 있습니다.
5️⃣ 마치며
오늘은 큐에대해 알아보았습니다.
틀리거나 개선사항이 있으면 아래 댓글에 남겨주세요.
다음시간은 좀더 어려운 자료구조인 트리에 대해 알아보도록 하겠습니다.
읽어주셔서 감사합니다.
