자료구조 - Queue

큐와 더불어 추상자료형(Abstract Data Type)의 한 종류이다. 먼저 들어온 데이터가 먼저 나가는 구조로 선입선출(FIFO: First In First Out)의 특성을 가지고 있다. 예를 들어 은행이나 영화관에서 줄을 기다리는 고객들의 순서를 처리하는 방식과 유사하다고 할 수 있다.

큐의 구현 방법에는 다양하지만 가장 대표적이면서 간단한 방식으로 선형큐를 꼽을 수 있다. 선형큐는 1차원 배열을 만들어서 데이터의 삽입,삭제를 진행한다.

새로운 데이터가 뒷단에서 추가되고 앞단에서는 데이터가 삭제되기 때문에 삽입, 삭제가 모두 한 쪽에서 일어나지 않는다. 데이터 추가를 Enqueue, 삭제를 Dequeue라고 정의한다. back(rear)은 큐의 마지막 데이터 front는 첫 번째 데이터를 가리킨다. 큐를 사용하는 이유는 컴퓨터 내의 cpu와 주변기기 사이에 속도 차이가 발생하기 때문에 cpu자원의 할당을 효율적으로 만들기 위해서이다.

자바스크립트의 선형 큐 구현은 다음과 같다.

class Queue{ 
	constructor(){
	  this.linearQueue = [];
	}
	toString(){
	  let result = "";
	  for(value of this.linearQueue){
		result = result + value + "\n";
	  }
	  return result;
	}
	enqueue(element){
	  this.linearQueue.push(element);
	}
	dequeue(){
	  return this.linearQueue.shift();
	}
	front(){
	  return this.linearQueue[0];
	}
	back(){
	  return this.linearQueue[this.linearQueue.length-1];
	}
	empty(){
	  if(this.linearQueue.length === 0){
		return true;
	  }
	  else{
		return false;
	  }
	}
  }

참고
1) https://www.javascripttutorial.net/javascript-queue/
2) https://jeong-pro.tistory.com/125
3) C언어로 쉽게 풀어 쓴 자료구조 - 천인국