큐(Queue)

04_큐.zip

큐?

큐(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();
			});
		})

저작자표시 비영리 변경금지 (새창열림)