큐(Queue)는 기본적인 자료구조로 먼저 삽입된 자료가 먼저 나오는 FIFO(First In First Out) 구조다. 

입력이 들어온 순서대로 처리하고 싶은 작업이 있을때 사용한다.

Enqueue는 데이터를 PUT 하는 것, Dequeue는 데이터를 GET 하는 것을 의미하며 각각 Back(Rear)과 Front에서 이루어진다.

선형 큐 (Linear Queue)

class LinearQueue {
	constructor(_size) {
		/**
		 * 배열의 크기
		 */
		this.size = _size;

		/**
		 * 데이터를 담는 배열
		 * Size보다 하나 더 큰 배열을 생성함으로써 큐가 가득 찼는지 아닌지 알 수 있게 하는
		 * 빈 칸을 하나 마련한다 (원형 큐의 핵심)
		 * @type {Array}
		 */
		this.data = new Array(this.size);
		this.front = -1;
		this.rear = -1;
	}

	/**
	 * 큐에 원소를 삽입
	 * @param item
	 */
	enqueue(item) {
		if (!this.isFull()) {
			this.rear++;
			this.data[this.rear] = item;
		} else {
			console.log('Queue is full.');
		}
	}

	/**
	 * 큐에서 원소를 삭제
	 */
	dequeue() {
		if (!this.isEmpty()) {
			this.front++;
			this.data[this.front] = undefined;
			this.reArrange();
		} else {
			console.log('Queue is empty.');
		}
	}

	/**
	 * 큐에 잉여 공간이 없도록 다시 정렬
	 */
	reArrange() {
		const tempData =  new Array(this.size);
		let k = 0;
		for (let i = this.front; i < this.rear; i++) {
			tempData[k] = this.data[i + 1];
			k++;
		}
		this.front = -1;
		this.rear = k - 1;
		this.data = tempData;
	}

	/**
	 * 큐가 비어있는지 검사
	 * @returns {boolean}
	 */
	isEmpty() {
		return this.rear === this.front;
	}

	/**
	 * 큐가 가득 차 있는지 검사
	 * @returns {boolean}
	 */
	isFull() {
		return this.rear + 1 === this.size;
	}

	/**
	 * 큐의 프론트 반환
	 * @returns {*}
	 */
	peek() {
		return this.data[this.front];
	}

	/**
	 * 큐 초기화
	 */
	clear() {
		this.data = new Array(this.size);
	}

	/**
	 * 큐 출력
	 */
	print() {
		console.log(this.data);
	}
}

원형 큐 (Circular Queue)

class CircularQueue {
	constructor(_size) {
		/**
		 * 배열의 크기
		 */
		this.size = _size;

		/**
		 * 데이터를 담는 배열
		 * Size보다 하나 더 큰 배열을 생성함으로써 큐가 가득 찼는지 아닌지 알 수 있게 하는
		 * 빈 칸을 하나 마련한다 (원형 큐의 핵심)
		 * @type {Array}
		 */
		this.data = new Array(this.size + 1);

		/**
		 * Rear는 개념적으로 데이터가 들어오는 부분이다.
		 * 데이터가 삽입될 때 마다 1씩 증가하며, Size보다 커질 수 없다.
		 * @type {number}
		 */
		this.rear = 0;

		/**
		 * Front는 개념적으로 데이터가 삭제되는 부분이다.
		 * 데이터가 삭제될 때 마다 1씩 증가하며, Size보다 커질 수 없다.
		 * @type {number}
		 */
		this.front = 0;
	}

	/**
	 * 큐에 원소를 삽입
	 * @param item
	 */
	enqueue(item) {
		if (!this.isFull()) {
			// 리어에 아이템을 삽입한다.
			this.data[this.rear] = item;
			// 아이템을 삽입했으므로 리어를 다음칸으로 지정한다.
			this.rear = (this.rear + 1) % (this.size + 1);
		} else {
			console.log('Queue is full.');
		}
	};

	/**
	 * 큐에서 원소를 삭제
	 */
	dequeue() {
		if (!this.isEmpty()) {
			// 프론트 다음칸의 아이템을 삭제한다.
			this.data[this.front] = undefined;

			// 아이템을 삭제했으므로 프론트를 다음칸으로 지정한다.
			this.front = (this.front + 1) % (this.size + 1);
		} else {
			console.log('Queue is empty.');
		}
	}

	/**
	 * 큐가 비어있는지 검사
	 * @returns {boolean}
	 */
	isEmpty() {
		return this.front === this.rear;
	}

	/**
	 * 큐가 가득 차 있는지 검사
	 * @returns {boolean}
	 */
	isFull() {
		return (this.rear + 1) % (this.size + 1) === this.front % (this.size + 1);
	}

	/**
	 * 큐의 프론트 반환
	 * @returns {*}
	 */
	peek() {
		return this.data[this.front];
	}

	/**
	 * 큐 초기화
	 */
	clear() {
		this.data = new Array(this.size + 1);
	}

	/**
	 * 큐 출력
	 */
	print() {
		console.log(this.data);
	}
}