자료구조 큐

Queue 큐

• FIFO(First In First Out)의 구조를 갖춘 자료구조
• 먼저 들어온 것이 먼저 나가는 특징

스택의 연산

• 삽입: push
• 삭제: pop

배열을 이용한 큐

class Queue {
	items = [];
    front = 0;
    rear = 0;
    
    pop() {
    	return this.items[this.front++];
    }
    
    push(item) {
    	this.items.push(item)
        this.rear++;
    }
    
    isEmpty() {
    	return this.front === this.rear
    }
}

연산의 수행시간

• pop : O(1)(상수 시간)
• push : O(1)
• isEmpty : O(1)

큐 예제 1) 요세푸스 문제

(코딩테스트 합격자되기 도서 참고)

• N명의 사람이 원형으로 서 있다.
• 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앤다

1. 1번 번호표를 가진 사람을 기준으로 K번째 사람 제거
2. 제거된 사람 다음 사람을 기준으로 다시 K번째 사람 제거

N과 K가 주어질 때 마지막에 살아 남은 사람의 번호는?

class Queue {
	items = [];
    front = 0;
    rear = 0;
    
    size() {
    	return this.rear - this.front;
    }
    
    pop() {
		return this.items[this.front++];
    }
    
    push(item) {
    	this.items.push(item);
        this.rear++;
    }
}


function Josephus(n, k) {
	const queue = new Queue();
    
    //1부터 n까지 queue에 넣기
	for(let i = 1; i <= n; i++) {
    	queue.push(i);
    }
    // 한 사람이 남을 때까지 반복    
    while(queue.size() > 1) {
		// k-1번째 사람은 pop+ push
        for(let i = 0; i < k-1; i++) {
        	queue.push(queue.pop());
        }
        queue.pop();
    }
    
    return queue.pop();
    // 마지막에 남아있는 사람의 번호
}

• k-1번째까지의 사람은 pop한 뒤 다시 queue에 넣어야함! => for문
• K번째 사람은 pop
• 한 사람이 남을 때까지 반복