Data Structures & Algorithms with Javascript : Queues

[이전 글]2024.07.19 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Stacks

Data Structures & Algorithms with Javascript : Stacks

👩🏻‍💻 저번 포스팅에서 스택 자료 구조에 대해 살펴봤다.
데이터를 순서대로 삽입하는 push연산, 가장 최근의 데이터를 리스트에서 꺼내서 제거하는 pop연산,
그리고 가장 최근의 데이터를 보기만 하는 peek 연산을 class로 구현해 보고,
스택을 활용해 팰린드롬, 재귀 동작 흉내내기, 진수 변경 알고리즘을 만들어봤다.

이번 시간에는 LIFO 방식과는 반대인 FIFO (first-in-first-out) 방식으로 데이터를 관리하는 queue가 무엇인지,  큐를 활용한 데이터 정렬(radix sort), 우선순위 큐에 대해 알아보자.

👫 Queue 연산

큐는 영어로 줄, 대기하다를 뜻한다

 

큐 자료 구조는 대기줄과 같은 형태다. 줄을 서려면 맨 뒤에 서 있고,

입장 및 순번이 되면 맨 앞에서부터 줄을 섰던 사람들이 빠지는 것처럼큐도 같은 방식으로 동작한다.

큐의 주요 연산에는 새로운 데이터를 삽입하는 "enqueue"와 데이터를 삭제하는 "dequeue"가 있다.

"enqueue"는 새 데이터를 queue의 맨 끝에 추가하는 연산이고, "dequeue"는 맨 앞의 데이터를 제거하는 것이다.

 

 

이전 stack에서 "peek" 연산은 맨 마지막 데이터를 확인하는 연산이라고 했다.

큐에서 peek 연산은 맨 앞의 데이터를 확인하는 연산이다.

👩🏻‍💻 array 기반 클래스  큐 구현

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

class Queue{
	constructor(){
    	this.dataStore = [];
    }
    // 큐에 데이터 삽입
    enqueue(element){
    	this.dataStore.push(element);
    }
    // 큐의 맨 첫 아이템 제거
    dequeue(){
		return this.dataStore.shift();
	}
    
    // 맨 앞 요소 확인 (peek연산)
    front(){
    	return this.dataStore[0];
    }
    
    // 맨 뒤 요소 확인
    back(){
    	return this.dataStore[this.dataStore.length - 1];
    }
    
    // 큐 아이템 문자열로 반환
    toString(){
    	let stringifiedQueue = '';
        for(let i=0; i< this.dataStore.length; i++){
        	stringifiedQueue+=this.dataStore[i] +'\n';
        }
        return stringifiedQueue;
    }
    
    // 큐가 비었는 지 확인
    empty(){
    	return this.dataStore.length===0
    }

}

// 콘솔로 출력해주는 유틸함수
const print = (item) => console.log(item);

const queue = new Queue();
queue.enqueue('a'); // 큐 상태 : ['a']
queue.enqueue('b'); // 큐 상태 : ['a','b']
queue.enqueue('c'); // 큐 상태 : ['a','b','c']

print(queue.toString()); 
/**
a
b
c
*/
print(queue.dequeue()); // b  큐 상태 : ['b','c']
print(queue.toString());
/**
b
c
*/
print(queue.front()); // b
print(queue.back()); // c

 

👩🏻‍💻 큐로 데이터 정렬 : radix sort

IBM 카드 펀치카드를 radix sort로 정렬하는 장면

과거 컴퓨터의 역사를 살펴보자면, 프로그램은 mainframe 프로그램을 펀치카드로 입력했었다.

각각의 카드가 하나의 프로그램 명령을 지니고 있었다. 이 카드들은 bin같은 구조물이 정렬해 주는 기계를 통해 정렬되었다.

이 정렬 동작을 큐를 활용해 모방할 수 있다. 이 정렬 방식을 radix sort라고 한다. 

 

radix sort의 예를 살펴보자. 

다음과 같이 0 ~ 99 사이의 숫자 세트가 있다고 하자.

91, 46, 85, 15, 92, 35, 31, 22

 

먼저 1의 자리를 기준으로 정렬을 해주면 다음과 같다.

Bin 0 : 
Bin 1 : 91, 31
Bin 2 : 92, 22
Bin 3 : 
Bin 4 : 
Bin 5 : 85, 15, 35
Bin 6 : 46
Bin 7 : 
Bin 8 : 
Bin 9 : 

 

첫번째 정렬을 통해 숫자 세트는 다음과 같이 정렬된다.

91, 31, 92, 22, 85, 15, 35, 46

 

이제 10의 자리를 기준으로 정렬을 해주자.

Bin 0 : 
Bin 1 : 15
Bin 2 : 22
Bin 3 : 31, 35
Bin 4 : 46
Bin 5 : 
Bin 6 : 
Bin 7 : 
Bin 8 : 85
Bin 9 : 91, 92

 

두 번째 정렬을 통해 숫자 세트는 다음과 같이 정렬된다.

15, 22, 31, 35, 46, 85, 91, 92

 

이 알고리즘을 큐로 구현해 보자.

논리 흐름

1. 각각의 bin을 큐로 나타내기 위해서는 9개의 큐가 필요하다.

2. modulus와 정수 나눗셈을 통해 1과 10의 자릿수를 정할 수 있다.

3. 자릿수에 따라서 해당 큐에 숫자를 추가해 준다.

4. 1과 10으로 정렬해 준 큐들을 순서대로 빼서 하나의 문자열로 이어준다.'

구현

‼ 예제는 책의 구현을 참고하여  변경사항이 있습니다!!

const TEN = 10;
const TEST_CASE_COUNT = 3;

// digit은 1 또는 10의 자릿수로 분배
function distribute(nums, queues, digit){
	for(let i= 0; i < TEN; ++i){
		digit === 1? queues[nums[i] % TEN].enqueue(nums[i]) : queues[Math.floor(nums[i] / TEN)].enqueue(nums[i]) 
	}
}

// 0-9까지의 큐에서 숫자 가져오기
function collect(queues, nums){
	let i = 0;
    for(let digit = 0; digit < TEN; ++digit){
    	while(!queues[digit].empty()){
        	nums[i++] = queues[digit].dequeue();
        }
    }
}

// 공백으로 이어준 정렬된 큐들
function displayArray(arr){
	return arr.join(' ');
}

// 사용

// 자릿수 별 0 - 9의 큐 bin
const queues = [];
for(let i = 0; i < TEN; ++i){
	queues[i] = new Queue();
}

// 정렬해줄 숫자 테스트 케이스
let testCase = Array.from({length: TEST_CASE_COUNT}, ()=>{
    let nums = [];
    for(let i = 0; i < TEN; ++i){
    	nums[i] = Math.floor(Math.floor(Math.random()*101));
    }
    return nums;
});

for(let i = 0; i < TEST_CASE_COUNT; i++){
    print(`test case ${i+1} 정렬 전: ${displayArray(testCase[i])}`);
    distribute(testCase[i], queues, 1); // 1의 자릿수를 기준으로 정렬
    collect(queues, testCase[i]); 
    distribute(testCase[i], queues, 10) // 10의 자릿수를 기준으로 정렬
    collect(queues, testCase[i]); 
    print(`test case ${i+1} 정렬 후: ${displayArray(testCase[i])}`);
    print('\n');
}
/**
VM1137:40 test case 1 정렬 전: 20 92 26 13 3 66 24 27 81 30
VM1137:40 test case 1 정렬 후: 3 13 20 24 26 27 30 66 81 92

VM1137:40 test case 2 정렬 전: 28 86 46 14 52 97 98 55 72 35
VM1137:40 test case 2 정렬 후: 14 28 35 46 52 55 72 86 97 98

VM1137:40 test case 3 정렬 전: 16 96 44 37 5 36 32 17 62 11
VM1137:40 test case 3 정렬 후: 5 11 16 17 32 36 37 44 62 96
*/

👩🏻‍💻 우선순위 큐 (priority queue)

일반적인 큐 연산에서는 dequeue연산은 무조건 맨 처음 큐에 추가된 엘리먼트가 제거된다.

하지만 때에 따라 FIFO방식이 아닌 다른 기준으로 요소를 dequeue 하고 싶을 수가 있다.

이때 사용할 수 있는 자료 구조가 우선순위 큐다.

 

우선순위 큐는 말 그대로 특정 우선 순위에 따라 요소를 제거하는 것이다.

우선 순위 큐의 동작은 응급실에서 응급처치가 이루어지는 순서와 비슷하다.

응급실에서 환자가 처치되는 순서는 먼저 오는 환자 순이 아니라, 긴급도가 높은 순으로 이루어지는 것처럼 동작한다.

 

환자의 상태에 따라 우선순위를 부여하는 예제를 구현해 보자.

환자의 응급 코드를 나타내기 위해 이전 queue의 코드를 수정해 보자.

class Patient{
	constructor(name, code){
    	this.name = name; // 환자의 이름
        this.code = code; // 환자의 응급 상태, 숫자가 클수록 우선 순위, 응급도가 높다.
    }
}

class PriorityQueue extends Queue{ // queue를 상속하는 priorityQueue
	constructor(){
    	super(); // 부모의 속성 상속받음
    }
	// 우선 순위에 따라 데이터 제거
    dequeue(){
		let priority = this.dataStore[0].code;
        for(let i=1; i< this.dataStore.length; ++i){
        	if(this.dataStore[i].code < priority){
            	priority = i;
            }
        }
        return this.dataStore.splice(priority,1);
	}

    toString(){
    	let stringifiedQueue = '';
        for(let i=0; i< this.dataStore.length; i++){
        	stringifiedQueue+=this.dataStore[i].name +' code' + this.dataStore[i].code + "\n";
        }
        return stringifiedQueue;
    }
    

}


// 환자를 우선 순위 큐에 추가
const patient1 = new Patient("Smith", 5);
priorityQueue.enqueue(patient1);

const patient2 = new Patient("Jones", 4);
priorityQueue.enqueue(patient2);

const patient3 = new Patient("Brown", 1);
priorityQueue.enqueue(patient3);

const patient4 = new Patient("Ingram", 1);
priorityQueue.enqueue(patient4);

print(priorityQueue.toString());
let treatedPatient = priorityQueue.dequeue();
print(`treated patient: ${treatedPatient[0].name}`);
print(`need treatment: ${priorityQueue.toString()}`);
treatedPatient = priorityQueue.dequeue();
print(`treated patient: ${treatedPatient[0].name}`);
print(`need treatment: ${priorityQueue.toString()}`);

/**
    Smith code5
    Jones code4
    Brown code1
    Ingram code1

    VM1184:40 treated patient: Jones
    VM1184:40 need treatment: Smith code5
    Brown code1
    Ingram code1

    VM1184:40 treated patient: Brown
    VM1184:40 need treatment: Smith code5
    Ingram code1
*/

 

🍀 마치면서

☺️ 오늘은 큐가 무엇인지, 어떤 주요 연산이 있고, 큐를 사용해서 정렬하는 예시와 우선순위 큐에 대해서 살펴봤다.
이 책이 쓰이던 2014에는 클래스 문법이 공식 규정에 없었던 때라 function으로 쓰이고 있다. 물론 그냥 function으로 써도 되지만 클래스를 쓸 경우가 별롤 없어서 환기 차원에서 쓰니까 낫배드.
이전 묵혀뒀던 클래스 문법을 다시 사용해 봐서 좋았다.

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9

https://en.wikipedia.org/wiki/Radix_sort

Radix sort - Wikipedia