.png)
정의
큐는 FIFO(First In First Out) 원리에 따라 정렬된 데이터 컬렉션을 의미합니다. 큐는 back/tail이라고 하는 한쪽 끝에서 요소를 삽입하고 front/head이라고 하는 다른 쪽 끝에서 요소를 삭제할 수 있는 간단한 데이터 구조 입니다. 공평한 자료 구조입니다.
작성 순서에 따라 도착하는 데이터를 도착한 순서대로 처리할 때 가장 대표적으로 사용됩니다. 중요한 개념은 가장 먼저 추가한 요소를 우선적으로 제거한다는 것입니다.
ES6 class 문법으로 구현하여보면 해당 코드로 구현할 수 있습니다. 클래스의 인스턴스를 생성하여 적용하여 보면 해당 데이터가 변경되는 것을 볼 수 있습니다. 큐와 스택은 원소를 추가/삭제하는 원리만 다를 뿐 나머지는 동일합니다.
하지만, 선형 큐의 경우 제한점이 있습니다. 데이터가 삽입되는 rear point, 빠져나가는 front point가 제한된 데이터 공간을 가지므로, 할당된 공간 끝까지 rear point가 도달하면(rear = N) 더 이상 자료를 삽입할 수 없는 상태가 되며 오버플로우가 발생합니다.
이러한 오버플로우를 해결하기 위해 이동 큐와 원형 큐 방식이 있습니다. 이동 큐 방식의 경우 큐내의 원소들을 이동시키는 방법으로 enqueue를 실행할 시 queue가 rear = N이면서 front의 위치 인덱스가 0이 아니라면
모든 데이터를 앞으로 당겨쓰는 큐입니다. 모든 시간 복잡도가 O(n)이 되므로 메모리 낭비의 문제로 잘 사용하지 않습니다. 원형 큐 방식의 경우 구조를 원형으로 연결하여 rear point 값을 변화시켜 가용 공간에 원소를 삽입하는 방식입니다.
class Queue {
constructor() {
this.queue = [];
}
enqueue(item) {
this.queue.push(item);
}
// 스택은 pop()
dequeue() {
return this.queue.shift();
}
// 스택은 peek()
front() {
return this.queue[0];
}
rear() {
return this.queue[this.queue.length-1];
}
isEmpty() {
return this.queue.length === 0;
}
size() {
return this.queue.length;
}
clear() {
this.queue=[];
}
print() {
console.log(this.queue.toString());
}
}
const newQueue = new Queue();
newQueue.enqueue("John"); // ["John"]
newQueue.enqueue("Jack"); // ["John", "Jack"]
newQueue.enqueue("Camila"); // ["John", "Jack", "Camila"]
newQueue.dequeue(); // ["Jack", "Camila"]
newQueue.dequeue(); // ["Camila"]우선순위 큐
일반적인 큐(Queue)는 First in-First Out 구조입니다. 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다. 하지만, 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다.
- 최소 우선순위 큐 : 우선순위 값이 낮으면 낮을수록 앞자리로 이동(1이 가장 높은 우선순위)
- 최대 우선순위 큐 : 우선순위 값이 높으면 높을수록 앞자리로 이동(1이 가장 낮은 우선순위)
우선순위 큐를 구현하는 방법은 다양합니다. 단순한 리스트를 통한 구현과 Heap 자료 구조를 통하여 구현할 수 있습니다. 데이터의 개수가 N개일 때, 구현 방식에 따라 알고리즘의 시간 복잡도는 다음과 같습니다.
배열의 경우 N개의 데이터에서 삽입 시 뒤 쪽에 연달아 넣으며, 삭제 시에는 가장 높은 우선 순위의 데이터 탐색을 위해 선형적인 N의 시간이 소요 됩니다. 힙의 경우 N개의 데이터를 넣는 것과 모두 빼는 과정에서 작업은 병합 정렬과 같은 여타 정렬 알고리즘과 동일합니다.
우선은 이번 정리에서는 배열 기반의 큐만을 다루고 트리에 대한 개념을 정리한 후에 Heap 자료구조를 통해 구현해보겠습니다.
우선순위를 설정하여 원소를 정확한 위치에 추가하는 방법
// 배열 기반 최소 우선순위 큐(min-queue)
// 큐 원소에 우선순위가 부가된, 새로운 형태의 원소
class QueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(element, priority) {
let queueElement = new QueueElement(element, priority);
if( this.isEmpty() ){
this.queue.push(queueElement);
// 비어있는 경우 원소를 넣음
} else {
let added = false;
// 비어있지 않은 경우 기존 원소들과 우선순위 비교
for(let i = 0 ; i < this.queue.length ; i++) {
if(queueElement.priority < this.queue[i].priority) {
// 만약 우선순위가 더 높은 기존 원소가 있다면
this.queue.splice(i, 0, queueElement);
// 한 칸 앞에 새 원초 추가 후 반복문 종료
added = true;
break;
}
}
if(!added) {
// 만약 새 원소의 우선 순위가 가장 낮다면
this.queue.push(queueElement);
// 큐의 맨 마지막에 추가
}
}
};
dequeue() {
return this.queue.shift();
}
front() {
return this.queue[0];
}
rear() {
return this.queue[this.queue.length-1];
}
isEmpty() {
return this.queue.length === 0;
}
size() {
return this.queue.length;
}
clear() {
this.queue=[];
}
print() {
console.log(this.queue.map(el => el.element));
}
}
let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jim", 1);
priorityQueue.enqueue("Sam", 5);
priorityQueue.dequeue(); // "Jim" dequeue
priorityQueue.print(); // [ 'John', 'Sam' ]추가는 순서대로 하고 삭제만 우선순위에 따르는 방법
// 배열 기반 최대 우선순위 큐(max-queue)
// 큐 원소에 우선순위가 부가된, 새로운 형태의 원소
class QueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(element, priority) {
let queueElement = new QueueElement(element, priority);
return this.queue.push(queueElement);
}
dequeue(){
let entry = 0;
for(let idx in this.queue) {
// 큐 내부 순회
if(this.queue[idx].priority > this.queue[entry].priority) {
// 큐 우선 순위 비교
entry = idx;
// 가장 높은 우선 순위 index 검색 및 할당;
}
}
return this.queue.splice(entry,1);
// 해당 요소 삭제
}
front() {
return this.queue[0];
}
back() {
return this.queue[this.queue.length-1];
}
isEmpty() {
return this.queue.length === 0;
}
size() {
return this.queue.length;
}
clear() {
this.queue=[];
}
print() {
console.log(this.queue.map(el => el.element));
}
}
let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jim", 1);
priorityQueue.enqueue("Sam", 5);
priorityQueue.dequeue(); // "Sam" dequeue
priorityQueue.print(); // [ 'John', 'Jim' ]원형 큐
원형 큐 방식이란 이동 큐(Moving Queue) 방식의 단점을 보완하기 위한 방법으로 크기 n인 1차원 배열 형태의 큐를 원형(Circular)으로 구성하여 배열의 처음과 끝을 연결하여 만든 것을 의미합니다. 원형 큐의 경우, queue의 공간에 아이템이 꽉 차지 않는 이상 언제든 enque와 deque를 할 수 있습니다. 그리고 모듈러 연산(나머지 연산)을 사용하게 됩니다.
원형 큐는 enqueue와 dequeue의 형태가 조금 다른데, max size 까지 가면 front와 rear가 0에서 다시 처음부터 시작해야 하기 때문입니다. 또한 front는 항상 item이 있는 곳 앞에 존재합니다.
포화이거나 공백 상태일 경우의 확인은 front와 rear 값의 비교로 수행합니다. 그 상태를 기반으로 분기처리하여 enqueue와 dequeue를 수행할 수 있도록 로직을 처리합니다.
class CircleQueue{
constructor(size){
this.maxQueueSize = size;
this.array = [];
this.front = 0;
this.rear = 0;
}
isEmpyt(){
return this.front == this.rear;
}
isFull(){
return (this.rear +1) % this.maxQueueSize == this.front;
}
enqueue(item){
if(this.isFull()){
console.log(new Error("큐가 포화상태입니다."))
}else{
this.rear = (this.rear + 1) % this.maxQueueSize;
this.array[this.rear] = item;
}
}
dequeue(){
if(this.isEmpyt()){
console.log(new Error("큐가 비었습니다."));
}else{
this.front = (this.front + 1) % this.maxQueueSize;
return this.array[this.front];
}
}
print(){
if(this.isEmpyt()) {
console.log(new Error("큐가 비었습니다."));
}
let string = "";
let i = this.front;
do {
i = (i+1) % this.maxQueueSize;
string += this.array[i] + "|";
if(i == this.rear){
console.log(string);
break;
}
} while(i != this.front);
}
}
let queue = new CircleQueue(4);
// 4개 요소의 원형 큐 자리 생성
queue.enqueue(1); // 1번 요소 추가
queue.enqueue(2); // 2번 요소 추가
queue.enqueue(3); // 3번 요소 추가
queue.dequeue(); // 1번 요소 제거
queue.enqueue(4); // 4번 요소 추가
queue.enqueue(5); // 5번 요소 추가
queue.enqueue(6); // 6번 요소 추가 실패
queue.print(); // 2|3|4|5뜨거운 감자 게임
// 기본 queue class 기반
function hotPotato (participantList, num) {
let queue = new Queue();
// 인스턴스 생성
for (let i = 0; i < participantList.length; i ++ ) {
// 참가자 큐에 추가
queue.enqueue(participantList[i]);
}
let eliminated = '';
while(queue.size() > 1) {
for(let i = 0; i < num; i++) {
// 원형 큐에서 en/dequeue를 실행하면서 맨 앞의 원소를 꺼내어 맨 끝에 다시 추가
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
// 지정된 횟수 만큼 만복했을 때 큐의 가장 앞에 있던 요소 dequeue
console.log(eliminated + '을(를) 게임에서 퇴장시킵니다.');
}
return queue.dequeue();
}
let participant = ['John', 'Jack','Camila','Ingrid','Carl'];
let winner = hotPotato(participant, 2)
// 'Camila을(를) 게임에서 퇴장시킵니다.'
// 'John을(를) 게임에서 퇴장시킵니다.'
// 'Carl을(를) 게임에서 퇴장시킵니다.'
// 'Jack을(를) 게임에서 퇴장시킵니다.'
console.log('승자는 '+winner+' 입니다.')
// '승자는 Ingrid 입니다.'