큐?
- 큐(Queue)는 FIFO(선입선출의 약자)원리에 따라 정렬된 컬렉션
- 새 원소는 뒤로 들어가서 앞으로 빠져나가는 구조
- 마지막에 추가된 원소는 큐의 뒷부분에서 제일 오래기다려야 한다.
- 예 : 줄서기, 컴퓨터(출력물 인쇄대기 - 문서5개 출력시 프린터는 도착한 순서대로 인쇄 시작)
큐 만들기
//큐 클래스 작성
function Queue(){
this.items = [];
}
큐에서 사용할 메소드
- enqueue : 큐의 뒤쪽에 원소를 추가
- dequeue : 큐의 첫번쨰 원소 반환후 큐에서 삭제
- front : 큐의 첫번쨰 원소 반환만
- isEmpty : 큐 비어있으면 true, 그게 아니면 false
- size : 큐의 원소개수 반환 (length)
enqueue
Queue.prototype.enqueue = function(element){
this.items.push(element);
}
dequeue
Queue.prototype.dequeue = function(){
return this.items.shift();
}
front
Queue.prototype.front = function(){
return this.items[0];
}
isEmpty
Queue.prototype.isEmpty = function(){
return this.items.length == 0;
}
size
Queue.prototype.size = function(){
return this.items.length;
}
디버깅용도 print
Queue.prototype.print = function(){
console.log(this.items.toString());
}
완성된 Queue 클래스
첨부파일내 파일명 : js/queue.js
function Queue(){
this.items = [];
}
Queue.prototype.enqueue = function(element){
this.items.push(element);
}
Queue.prototype.dequeue = function(){
return this.items.shift();
}
Queue.prototype.front = function(){
return this.items[0];
}
Queue.prototype.isEmpty = function(){
return this.items.length == 0;
}
Queue.prototype.size = function(){
return this.items.length;
}
Queue.prototype.print = function(){
console.log(this.items.toString());
}
Queue 클래스 사용
첨부파일내 파일명 : 02_큐클래스사용.html
Queue클래스를 사용하여 대기자명단을 출력하고, 대기자명단 순서에 따라 입장
첨부파일내 파일명 : 02_큐클래스사용_form차이.html
태그를 form사용하여 button에 이벤트를 줬는데, 폼을 전송하여 문서가 리로드 된다.
submit을 사용하지 않았는데.-_-?
button태그를 쓰고 submit이라고 하지 않아도, type을 따로 써주지 않으면 디폴트로 submit!
button type="button" 으로 해결
우선순위 큐
- 큐는 일상생활에서도 널리 활용되는 개념 -> 기본 큐를 변형해 사용
- 대표적인 예 : 우선순위 큐 - 원소가 우선순위에 따라 추가되고 삭제
- 우선순위큐의 예 : 비행기 1등석, 비즈니스석, 코치석 / 병원 응급실
우선순위 큐의 종류
-
우선순위에 따라 원소를 정확한 위치에 추가하는 것
- 추가는 순서대로 하되, 삭제만 우선순위에 따라 삭제
우선순위 큐 구현 / 첨부파일내 파일명 : js/priorityQueue.js
function QueueElement(element, priority){
this.element = element;
this.priority = priority;
}
PriorityQueue.prototype.enqueue = function(element, priority){
var queueElement = new QueueElement(element,priority);
if(this.isEmpty()){ //비어있을경우 그냥추가
this.items.push(queueElement);
}else{
var added = false;
//기존에 추가된 원소들과 우선순위 비교후 자리찾아 넣기
for(var i=0; i < this.items.length; i++){
if(queueElement.priority < this.items[i].priority){
this.items.splice(i,0,queueElement);
added = true;
break;
}
}
//추가될 원소보다 우선순위높은게(숫자작은거) 없을경우 맨앞에 추가
if(!added){
items.push(queueElement);
}
}
}
다른 메소드들은 똑같지만, 원소 추가될때 우선순위를 비교
우선순위 큐를 사용하여 오류사항 리포트 구현 / 첨부파일내 파일명 : 03_우선순위큐.html
위와같은 로직으로 구현한 우선순위큐를 최소 우선순위 큐 라고 부른다.
cf)최대우선순위 큐
환형 큐(뜨거운 감자 게임)
- 기본큐의 변형
- 원을 그리고 서 있는 아이들이 뜨거운 감자를 옆사람에게 최대한 빨리 전달
- 일정한횟수만큼 전달하다가 멈췄을때 뜨거운 감자를 손에들고있는 아이를 퇴장
- 최후의 1인이 남을때까지 게임은 계속
뜨거운감자 console창에서 확인 / 첨부파일내 파일명 : 04_환형큐.html
function hotPotato(nameList, num){
var queue = new Queue();
for(var i = 0; i < nameList.length; i++){
queue.enqueue(nameList[i]);
}
var eliminated = '';
while(queue.size() > 1){
for(var i=0; i < num; i++){
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log(eliminated+'(을)를 뜨거운 감자게임에서 퇴장시킵니다.');
}
return queue.dequeue();
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('승자는 '+winner+'입니다');
뜨거운감자 응용 / 첨부파일내 파일명 : 04_환형큐.html
뜨거운 감자를 이용하여 술래찾기 -> 회사에서 이걸로 커피내기했었다. (근데 내가걸림 ㅠ)
function CustomHotPotato(area,num){
this.viewArea = null;
this.turnNum = null;
this.personList = null;
//this.gameAuto = null;
//this.gameTime = null;
this.gemeTurn = null;
this.init(area,num);
}
CustomHotPotato.prototype.init = function(area,num){
this.viewArea = $(area);
this.turnNum = num;
//this.gameTime = 1000;
this.gemeTurn = 0;
this.personList = new Queue();
}
CustomHotPotato.prototype.addList = function(){
for(var i =0; i < names.length; i++){
this.personList.enqueue(names[i]);
}
}
CustomHotPotato.prototype.viewList = function(){
var cont = ''
var listTemplate = '- {name}
'
for(var i = 0; i < this.personList.size(); i++){
cont += listTemplate.replace('{name}',this.personList.items[i]);
}
cont += '
';
this.viewArea.html(cont);
}
CustomHotPotato.prototype.gameStart = function(){
this.srchPerson();
//this.gameAuto = setTimeout(this.srchPerson(),this.gameTime);
}
CustomHotPotato.prototype.srchPerson = function(){
if(this.personList.size() > 1){
if(this.gemeTurn < this.turnNum){
this.personList.enqueue(this.personList.dequeue());
this.gemeTurn += 1;
this.srchPerson();
}else{
var eliminated = this.personList.front();
var myObj = this;
//그사람에 해당하는 거 삭제해줘야함
this.viewArea.find('ul li').each(function(){
var srchName = $(this).html();
if(srchName == eliminated){
$(this).addClass('del').animate({opacity:0},800,function(){
//alert(eliminated+'탈출');
myObj.viewArea.prev().append(''+eliminated+'탈출
');
myObj.personList.dequeue();
myObj.viewList();
myObj.gemeTurn = 0;
});
}
});
}
}else{
var win = this.personList.dequeue();
this.viewArea.find('ul li').eq(0).addClass('active');
alert('술래는 '+win+'입니다');
//if(this.gameAuto) clearTimeOut(this.gameAuto);
}
}
$(document).ready(function(){
var addname = prompt('사람 이름 입력(,)구분');
names = addname.split(',');
var num = Math.floor(Math.random()*20+1);
console.log('순회횟수 랜덤:'+num);
var game = new CustomHotPotato('.person_list',num);
game.addList();
game.viewList();
$('button').click(function(){
game.gameStart();
});
})
masonry2.2.zip
