코딩하는 학생이라면 큐를 알고 있을 것입니다.
흔히 알고 있는 Queue는 FIFO 특징을 가지고 있습니다. (저는 일단 이렇게 배우고 넘어갔답니다..ㅎㅎ)
더 배운 내용은 있었지만 간단하게 넘어갔는데
코딩테스트를 공부하면서 Queue의 종류가 있다는 것을 알고 코테를 하면서는 알고리즘, 자료구조가 필수 인것 같아서 차근차근 공부하려고 합니다!
Queue란?
큐(queue)란 컴퓨터과학에서 중요한 추상적 자료구조 중 하나입니다. 큐는 항목의 컬렉션으로, 두가지 주요 작업이 있습니다.
- Enqueue: 큐의 뒤쪽에 항목을 추가합니다.
- Dequeue: 큐의 앞쪽에서 항목을 제거하고 반환합니다
이러한 동작은 FIFO(First In First Out) 원칙을 따르며, 첫번째로 들어온 요소가 가장 먼저 출력되는 것을 말합니다.
예를 들어,
기차표를 끊을 때 먼저 줄을 선사람이 먼저 들어가서 기차표를 끊고 나오는 특징과 같습니다.
스택(Stack)은 LIFO(Last In First Out)의 특징을 가지고 있습니다.
일반적인 큐가 이런 것이고
그 외에는 우선순위 큐(Priority Queue), 원형 큐(Circular Queue), 덱(Deque: 양쪽 끝에서 삽입 및 삭제가 가능한 자료구조) 등 여러 종류의 큐가 있습니다.
이번 포스팅에서는 6가지 큐에 대해 원리와 특징을 작성하겠습니다.
- 일반 큐(Queue)
- 원형 큐 (Circular Queue)
- 우선순위 큐 (Priority Queue)
- 덱( Deque; Double Ended Queue)
- 블로킹큐(Blocking Queue)
- 워크스틸링(Workstealing Queue)
이렇게 6가지 큐에 대해 설명하겠습니다.
1. 일반 큐 (Queue)
위에 설명한 내용과 같이 FIFO 특징을 가지고 있습니다.
First In First Out의 특징을 가지고 있습니다.
Enqueue와 Dequeue는 제일 처음에 설명했으므로 생략하겠습니
특징
- 큐의 한쪽 끝은 front로 정하여 삭제연산만 수행한다
- 다른 한쪽 끝은 Rear로 정하여 삽입연산만 수행한다
- FIFO(First In First Out)의 특징을 가지고 있다
- 큐는 컴퓨터과학에서 많은 문제를 해결하기 위해서 자주 사용한다
- Underflow와 Overflow상황이 발생한다
Queue를 지원해주진 않기 때문에 배열이나 LinkedList로 구현할 수 있습니다.
큐를 사용할 때는 push, pull, isEmpty 등 여러 함수를 발생시킬 수 있습니다.
시간 복잡도 : O(1)
2. 원형 큐 (Circular Queue)
원형 큐는 일반 큐의 단점을 보완해줍니다.
일반 큐에서 삽입한 뒤에 삭제하는 경우에 front부분에 값이 없기 때문에 한칸씩 값을 옮겨야합니다.
이 문제 때문에 시간 복잡도가 복잡해져서 시간 초과가 되는 경우가 많습니다.
원형 큐는 아래와 같은 모양을 가지고 있다고 생각하면 됩니다.
위에 Front와 Rear 두가지가 있습니다. 일반적인 큐라면 Front는 값이 나가는 부분, Rear은 들어가는 부분 즉 먼저 나갈 값과 마지막에 들어간 값. 이렇게 임의로 정해줄 수 있습니다. 일반 적인 큐에서는 그냥 값이 비어지는 경우라 비효율적입니다. 하지만, 원형 큐는 다릅니다.
Front와 Rear 값을 계속 따라갑니다. Front는 큐의 시작, Rear은 큐의 끝점입니다.
값이 Enqueue, Dequeue 될 때마다 Front와 Rear의 점이 달라진다는 것입니다. 즉 포인터와 같다고 볼 수 있죠.
값이 추가, 삭제 되어도 유동적으로 포인터값이 바뀌어서 작업을 수행할 수 있습니다.
- Enqueue : Rear 부분에 추가된 값이 추가, Rear 포인터도 +1
- Dequeue : Front 부분의 값 삭제, front 포인터 +1
로 확인할 수 있습니다.
isEmpty, isFull 등 다양한 함수도 추가할 수 있겠죠!
이런 경우에는 Front와 Rear의 포인터 값을 보고 판단할 수 있습니다.
isEmpty인경우는 Front와 Rear의 포인터값이 같으면 true
isFull인 경우는 Rear+1이 Front의 포인터 값이 같은면 true
입니다!
원형 메모리 큐는 메모리를 더 효율적으로 활용할 수 있다는 큰 장점이 있습니다!
시간 복잡도 : O(1)
3.우선순위 큐 (Priority Queue)
우선순위 큐는 말그대로 우선순위가 있는 큐입니다.
기본적인 큐와 마찬가지로 삽입과 삭제가 있는 큐입니다. 대신 값을 꺼낼 때 우선순위가 높은 게 먼저 꺼내진다는 점이 다른 점입니다!
우선순위 큐에서는 삽입될 때 우선순위를 파악한 뒤에 정렬이 됩니다.
비교 기준은 구현하는 사람의 마음이겠죠
예를 들어 갑이 큰값이 우선순위가 크거나 반대로 작은 값이 우선순위가 크거나 개발자의 비교 기준이 정해주겠죵
우선순위 큐는 삽입과 삭제 함수? 기능의 이름이 다릅니다
Inser와 Delete (or pop)이 있습니다. 그리고 새로운 함수및 기능으로는 우선순위가 높거나 낮은 값을 조회할 수 있는 데, 이를 Peek or Pop이 있습니다.
- Insert : 값 삽입
- Delete (or Pop) : 삭제
- Reek or Pop : 우선순위가 크거나 작은 값을 조회
우선순위 큐는 일반적으로 힙(Heap)으로 구현됩니다.
우선순위 큐는 알고리즘 방식으로 많이 사용되는 데 Dijkstra 알고리즘이나 탐색 알고리즘 등에서 최단 경로 문제 해결에 사용되며, 작업 스케쥴링 등에서도 활용됩니다.
오른쪽에 있는 배열이 힙 영역입니다.
해당 배열에 값을 넣을 때 비교하면서 넣는 다는 특징을 가지고 있습니다.
(이 알고리즘을 코드로 구현하는데에는 좀 공부를 하고 알고리즘을 더 공부해야할 것 같습니다..)
시간 복잡도 : O(log n)
4.덱( Deque; Double Ended Queue)
덱이란 양쪽에서 삽입, 삭제가 가능한 구조이며, 스택과 큐의 연산을 모두 지원합니다.
덱은 동적 배열이나, 이중 연결 리스트 등을 사용할 수 있습니다.
- PushFront: 덱의 앞부분에 요소를 추가합니다.
- PushBack: 덱의 뒷부분에 요소를 추가합니다.
- PopFront: 덱의 앞부분에서 요소를 제거하고 반환합니다.
- PopBack: 덱의 뒷부분에서 요소를 제거하고 반환합니다.
- Front/Back: 각각 덱의 앞부분과 마지막 부분에 있는 요소를 조회(peek)하는 연산입니다.
덱은 스택과 큐 역할을 동시에 가능합니다.
그래서 다양한 상황에서 사용될 수 있다는 장점이 있습니다.
시간 복잡도 : O(1)
5.블로킹큐(Blocking Queue)
블로킹 큐는 특정한 상황에서 쓰레드를 대기하도록 하는 큐입니다.
쓰레드는 한 프로세스 내에서 동작되는 여러 실행의 흐름입니다.
프로세스 내에서 주소 공간이나 작업들을 같은 프로세스 내에 쓰레드끼리 공유하면서 실행됩니다.
대기 상태, 실행 상태, 준비 상태 이 세가지 상태가 있습니다. 작업을 수행할 때 준비 -> 실행 -> 대기로 수행할 수 있는데 만약 쓰레드가 수행 완료 되면 완료 상태가 되는 것도 있습니다.
즉 완료가 안되면 대기 상태인것이죠(잘못 알고 있을 수도 있습니다..)
블로킹 큐는 프로세스 내에서 수행되는 쓰레드를 관리하는 큐입니다. 그래서 시간복잡도를 보여주기 힘듭니다..
블로킹 큐는 멀티 스레딩 환경에서 매우 유용하며, 특히 프로듀서-컨슈머 패턴에서 자주 사용됩니다.
프로듀서-컨슈머 패턴
- 프로듀서 : 데이터를 생성하고 버퍼에 추가(Enqueue)하는 역할
- 컨슈머 : 버퍼에서 삭제(Dequeue)하는 역할
프로듀서와 컨슈머는 쓰레드인데 추가, 삭제 역할을 가지고 있다고 판단하면 됩니다.
프로듀서는 새로운 데이터가 생성될 때마다 이것을 큐에 추가합니다.
컨슈머는 필요한 데이터가 있다면 큐에서 꺼내어 사용합니다.
(이부분은 멀티 스레딩 환경을 공부한 뒤에 다시 공부해야할 것 같고 이런 디자인 패턴도 공부해야할 것 같습니다..)
멀티 스레딩 환경이기 때문에 시간복잡도를 구하긴 어렵습니다.
6. 워크스틸링(Workstealing Queue)
워크스틸링은 병렬 컴퓨팅에서 사용되는 스케쥴링 방법 중 하나입니다.
일부 스레드가 다른 스레드보다 일찍 작업을 마치고 난 후, 아직 작업이 남아 있는 다른 스레드들의 작업을 '도와주는' 것입니다.
워크스틸링 알고리즘은 각각의 워커풀에 자신만의 로컬 워크큐를 가지게 됩니다.
어떤 워커풀이 모든 작업을 완료하면 다른 워커풀의 로컬 워크큐에서 작업을 가지고 와서 수행합니다.
즉, 작업이 모두 끝난 상태라면 다른 작업 가지고와서 수행합니다.
모든 스레드들이 계속하여 작업을 할 수 있도록 하면서 병렬 컴퓨팅 환경에서 리소스를 효율적으로 활용할 수 있게 됩니다.
Java의 ForkJoinPool이 대표적인 워크 스틸링 알고리즘을 사용한 예입니다.
워크 스틸링도 마찬가지로 시간복잡도를 구하긴 어렵겠네요
(멀티 스레딩 작업과 관련된 내용은 공부해서 다시 포스팅 해보겠습니다..)
참고
https://suyeon96.tistory.com/31
https://velog.io/@16fekim/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90