[2023-09-25] TIL - 자료구조 & 알고리즘 - 큐

큐

- First In First Out이라는 개념을 가진 선형 자료구조이다.

- Linear Queue(선형 큐)의 Circular Queue(환형 큐)가 존재한다.

 

 

Linear Queue

Array로 표현하기

-Linear Queue를 Array로 표현할 수 있다.

- EnQueue가 계속 되어 한정된 공간인 배열이  꽉 차게 된다면 더이상 큐에 값을 추가할 수가 없습니다.

- 자바스크립트에서는 배열의 크기가 자동적으로 증감되기 때문에 이러한 문제가 없지만 Front나 Rear의 인덱스 값이 무한정 커질 수 있다는 문재가 있다.

 -> 공간을 더 활용하기 위해 데이터를 앞당기는 작업이 필요하다.

 -> 이 작업을 수행하면 선형시간이 소요된다.

    -> 이런 문제를 해결하기위해 연결리스트로 큐를구현해야한다.

 

Array로 표현하기 코드

- 코딩테스트에서 큐를 사용할 때 유용하다.

- 앞서 말했듯이 Front와 Rear가 무한정 커질 수 있는 단점이 있다.

class Queue {
	constructor() {
    	this.queue =[];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(value){
    	this.queue[this.rear++] = value;
    }
    
    dequeue() {
    	const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front +=1;
        return value;
    }
    
    peek() {
    	return this.queue[this.front];
    }
    
    size() {
    	return this.rear - this.front;
    }
}

const queue = new Queue();
queue.enqueue(1);
queue.dequeue();

 

 

Linked List로 표현하기

- Linear Queue를 Linked List로 표현할 수 있다.

- Head는 Front, Tail은 Rear

- 연결리스트로 구현하면 배열과 다르게 인덱스에 대한 고민은 하지 않아도 된다.

 

Linked List로 표현하기 코드

- 배열로 구현하는 것보다는 어렵기 때문에 코딩테스트에서는 배열로 구현하는 것이 낫다.

class Node {
	constructor(element) {
		this.element = element;
        this.next = null;
    }
}
class Queue{
	constructor() {
    	this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    enqueue(newElement){
    	const newNode = new Node(newElement);
        if(this.haed === null){
        	this.head = this.tail = newNode;
        }
        else{
        	this.tail.next = newNode;
            this.tail =newNode;
        }
        this.size +=1;
    }
    
    
    dequeue() {
    	const value = this.head.element;
        this.head = this.head.next
        this.size -= 1;
        return value;
    }
    
    peek() {
    	return this.head.element
    }
    
    size() {
    	return this.size;
    }
}

const queue = new Queue();
queue.enqueue(1);
queue.dequeue();

 

 

 

 

shift 함수는 쓰지말자!

- 이유는 shift 함수는 선형시간이 걸리게된다.

 

 

 

Circular Queue

- Front와 Rear기 이어져있는 Queue

- Circular Queue는 Linked List로 구현했을 때 이점이 없다.

- 환형큐는 한정된 공간을 효율적으로 활용하기위해 사용하는 자료구조이므로 연결리스트로 구현해도 상관없지만 크게 이점은 없다.

 

 

Array로 표현하기 코드 

- 자바스크립트에서 환형큐를 사용해야하는 경우는 별로 없기때문에 외우지 않아도 된다.

class Queue {
	constructor() {
    	this.maxSize = maxSize;
        this.queue = [];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    enqueue(value){
    	if(this.isFull()) {
        	console.log("Queue is full");
            return;
        }
        this.queue[this.rear] = value;
        this.rear = (this.rear + 1) % this.maxSize;
        this.size += 1;
    }
    
    dequeue() {
    	const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front = (this.front + 1 ) % this.maxSize;
        this.size -= 1;
        return value;
    }
    isFull(){
    	return this.size === this.maxSize
    }
    peek() {
    	return this.queue[this.front];
    }
    
    size() {
    	return this.rear = this.front;
    }
}

const queue = new Queue();
queue.enqueue(1);
queue.dequeue();

 

 

프로그래머스 큐를 이용한 코딩테스트

https://school.programmers.co.kr/tryouts/101813/challenges

 

 

내 코드

class Queue {
    constructor(){
        this.queue = [];
        this.front = 0;
        this.rear = 0;
        this. max = 0;
    }
    enqueue(value){
        this.max=Math.max(this.max,Number(value));
        this.queue[this.rear++] = value;
    }
    maxRef(){
        this.max=0;
        for(let i=this.front;i<this.rear;i++){
            this.max=Math.max(this.max,this.queue[i]);
        }
        
        
    }
    
    dequeue() {
    	const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front +=1;
        return value;
    }
    
    peek() {
    	return this.queue[this.front];
    }
    
    size() {
    	return this.rear - this.front;
    }
}

function solution(priorities, location) {
    var answer = 0;
    let loc = location;
    const queue = new Queue();
    for(let v of priorities){
        queue.enqueue(Number(v));
    }
    let si = queue.size();
    while(si !== 0){
        let temp = queue.dequeue();
        if(temp>= queue.max){
            answer++;
            si--;
            queue.maxRef();
            if(loc === 0){
                return answer;
            }
        }
        else {
            queue.enqueue(temp);
            if(loc==0){
                loc += si;
            }
        }
        loc--;
    }
    return answer;
}

 

 

다른 풀이

class Node {
	constructor(element) {
		this.element = element;
        this.next = null;
    }
}
class Queue{
	constructor() {
    	this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    enqueue(newElement){
    	const newNode = new Node(newElement);
        if(this.haed === null){
        	this.hjead = this.tail = newNode;
        }
        else{
        	this.tail.next = newNode;
            this.tail =newNode;
        }
        this.size +=1;
    }
    
    
    dequeue() {
    	const value = this.head.element;
        this.head = this.head.next
        this.size += 1;
        return value;
    }
    
    peek() {
    	return this.head.element
    }
    
    size() {
    	return this.size;
    }
}


function solution(priorities, location){
	const queue = new Queue();
    for(let i=0;i<priorities.length; i+=1){
    	// 인덱스값을 넣어서 각각의 요소가 처음에 몇 번째에 위치했었는지 알 수 있음
		queue.enqueue([priorities[i],i]);
    }
    
    // 중요도를 내림차순으로 정렬
    priorities.sort((a,b) => b-a);
	
    // 내가 요청한 문서가 몇번쨰로 인쇄되는지를 위한 count 변수
    let count = 0;
    while(queue.size > 0) {
    	const currentValue = queue.peek();
        //만약 내림차순한 중요도의 첫번째 요소와 queue의 front값보다 크면 다시 뒤에 enqueue한다.
        if(currentValue[0] < priorities[count]){
        	queue.enqueue(queue.dequeue());
        }
        else{
        //만약 현재 front가 중요도보다 크거나 같다면 dequeue하고 프린트해준다.
        	const value = queue.dequeue();
            count +=1;
            // 이때 우리가 요청한 문서의 인덱스 갑과 현재 프린트된 문서의 인덱스값이 같을 경우
            if(location === value[1]){
            	return count;
            }
        }
        
            
    }
    
}