[BaekJoon][자료 구조][Queue][Java] 큐 구현하기

<문제>

Queue는 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.

주어진 N(2<= N <=100)개의 수를 순서대로 Queue에 넣은 후 하나씩 꺼내 화면에 출력하시오.

 

<입력>

2 // 테스트 케이스 수
5 // 데이터 크기
1 2 3 4 5
5 4 2 3 1

 

<출력>

#1 1 2 3 4 5
#2 5 4 2 3 1

 

<주의점>

 

front와 back으로 구성된 큐에 값을 집어넣는 enqueue를 구현할 때

배열 큐는 고정된 크기이기 때문에 단순히 queue[back++] = value 를 해버리면

배열의 뒤쪽에는 더 이상 요소를 추가할 공간이 없으나 배열의 앞쪽에는 빈 공간이 남아있게 됨.

 

따라서 순환 큐 개념을 사용해야 함.

 

순환 큐는 모듈로 연산을 사용해 구현 가능.

다만, 순환 큐는 모든 인덱스를 다 사용하지는 않고 back 과 front 사이에 하나의 인덱스는 남겨 놓는다.

 

 

<풀이>

package BOJ;

import java.io.*;

public class MyQueue{
	private static int[] queue;
	private static int front, back;
	/*
	 * front
	 * 	: 큐에서 가장 먼저 들어온 요소. 즉, 다음에 제거될(반환될) 요소의 위치.
	 *  back
	 *  : 큐에서 마지막에 들어온 요소의 바로 다음 위치. 즉, 새로운 요소가 추가될 위치.
	 */
	
	// 큐 초기화
	public static void init(int n) {
		queue = new int[n];
		front = 0;
		back = 0;
	}
	
	// 큐가 비어 있는지 확인
	public static boolean queueIsEmpty() {
		return front == back;
	}
	
	// 큐가 가득 차있는지 확인
	public static boolean queueIsFull() {
		// back 포인터가 front 포인터의 바로 앞에 도달했으면 큐가 가득 차있는 상태
		return (back + 1) % queue.length == front;
		// back 과 front 포인터가 같을 경우를 가득 창 상태로 규정하게 되면 큐가 비어 있는 상태와 구별할 방법이 없기 때문에
		// 배열 1크기는 비워 놓는 경우를 포화 큐로 규정함
	}
	
	// 큐에 원소를 집어 넣는 메소드
	public static boolean queueEnqueue(int value) {
		// 큐가 가득 차있을 경우 false
		if((queueIsFull())) return false;
		queue[back] = value;
		// 순환 큐
		back = (back + 1) % queue.length;
		return true;
	}
	
	public static Integer queueDequeue() {
		// 큐가 비어 있을 경우 null
		if(queueIsEmpty()) return null;
		int value = queue[front];
		// 순환 큐
		front = (front + 1) % queue.length;
		return value;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		
		int size = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for(int testcase = 1; testcase <= n; testcase++) {
			String[] info = br.readLine().split(" ");
			
			init(size + 1); // 큐가 가득 찬 상태와 비어 있는 상태를 구분하기 위해 크기를 N+1로 설정
			
			sb.append("#").append(testcase).append(" ");
			
			for(int i = 0; i < size; i++) {
				int value = Integer.parseInt(info[i]);
				queueEnqueue(value);
			}
			while(!queueIsEmpty()) {
				int value = queueDequeue();
				sb.append(value).append(" ");
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}