[자바] 큐(Queue) - 선입선출(FIFO : First In First Out)의 자료구조

큐

Queue(대기줄)

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다.

하지만, 스택과 다른 점은 선입선출(FIFO : First In First Out)의 자료구조로 되어있습니다.

Queue(대기줄)이라고 불리는 이유는 선입선출의 구조가 은행에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열과 비슷하기 때문입니다.

큐는 선형 큐 또는 원형 큐를 구현할 수 있습니다.

선형 큐는 데이터가 디큐 되었을 때 데이터를 하나씩 앞쪽으로 옮겨야 하는 구조이고

원형큐는 첫 번째 요소와 마지막 요소를 식별하기 위한 변수 프런트(front)와 리어(rear)를 사용하여 데이터를 앞쪽으로 옮기지 않고 사용하는 자료구조입니다. 

 

이번 포스팅에선 원형 큐를 구현해보도록 하겠습니다.

 

Queue 생성자

package queue;

public class IntQueue {
	private int max; // 큐의 최대 용량
	private int front; // 첫번째 요소
	private int rear; // 마지막 요소
	private int num; // 현재 데이터 수
	private int[] que; // 본체

	// 실행시 예외 : 큐 비어있음
	public class EmptyIntQueueException extends RuntimeException {
		public EmptyIntQueueException() {
		}
	}

	// 실행시 예외 : 큐가 가득 차있음
	public class OverflowIntQueueException extends RuntimeException {
		public OverflowIntQueueException() {
		}
	}
	
	public IntQueue(int capacity) {
		num = 0;
		front = 0;
		rear = 0;
		max = capacity;
		
		que = new int[max];
	}
}

생성시 큐는 비어있기 때문에 num, front, rear를 0으로 초기화하고, 입력받은 매개변수 capacity를 max에 복사하고 배열을 생성합니다.

 

큐 인큐(enque)

public int enque(int x) {
		if(num >= max) {
			throw new OverflowIntQueueException();
		}

		que[rear++] = x; // rear의 위치에 데이터를 넣고 1을 증가시킨다.
		num++; // 현재 데이터수 1증가
		if(rear == max) { // rear가 max와 같아지게 되면 ArrayIndexOutOfBoundsException가 발생하기 때문에 rear를 0으로 이동
			rear = 0; 
		}
		
		return x;
	}

큐가 가득 차서 데이터를 넣을 수 없으면 OverflowIntQueueException을 발생시킵니다.

만약 rear의 값이 max와 같아지면 더 이상 데이터를 넣을 수 없을 뿐만 아니라 ArrayIndexOutOfBoundsException가 발생하기 때문에 rear의 값을 0으로 이동시켜줍니다.

 

큐 디큐(deque)

	public int deque() {
		if (num <= 0) {
			throw new EmptyIntQueueException();
		}

		int x = que[front++]; // front의 위치에 데이터를 꺼내고 1을 증가시킨다.
		num--; // 현재 데이터수 1감소
		if (front == max) { // front가 max와 같아지게 되면 ArrayIndexOutOfBoundsException가 발생하기 때문에 front를 0으로 이동
			front = 0;
		}

		return x;
	}

큐가 비어있어 데이터를 꺼낼 수 없으면 EmptyIntQueueException을 발생시킵니다.

인큐와 마찬가지로 front가 max와 같아지게 되면 front를 0으로 이동시킵니다.

 

큐 피크(peek)

피크는 front에 위치한 데이터를 확인하는 메서드입니다.

	public int peek() {
		if (num <= 0) {
			throw new EmptyIntQueueException();
		}
		
		return que[front];		
	}

 

큐 요소검색(indexOf)

indexOf는 큐 안에 데이터가 존재하는지 확인하여 존재하면 인덱스를 반환하고 존재하지 않으면 -1을 반환합니다.

	public int indexOf(int x) {
		for(int i = 0 ; i < num ; i++) {
			int idx = (i + front) % max; // front부터 검색하여 max를 넘으면 나머지 값으로 검색
			if(que[idx] == x) {
				return idx;
			}
		}
		
		return -1;
	}

 

전체 코드

package queue;

public class IntQueue {
	private int max; // 큐의 최대 용량
	private int front; // 첫번째 요소
	private int rear; // 마지막 요소
	private int num; // 현재 데이터 수
	private int[] que; // 본체

	// 실행시 예외 : 큐 비어있음
	public class EmptyIntQueueException extends RuntimeException {
		public EmptyIntQueueException() {
		}
	}

	// 실행시 예외 : 큐가 가득 차있음
	public class OverflowIntQueueException extends RuntimeException {
		public OverflowIntQueueException() {
		}
	}

	public IntQueue(int capacity) {
		num = 0;
		front = 0;
		rear = 0;
		max = capacity;

		que = new int[max];
	}

	public int enque(int x) {
		if (num >= max) {
			throw new OverflowIntQueueException();
		}

		que[rear++] = x; // rear의 위치에 데이터를 넣고 1을 증가시킨다.
		num++; // 현재 데이터수 1증가
		if (rear == max) { // rear가 max와 같아지게 되면 ArrayIndexOutOfBoundsException가 발생하기 때문에 rear를 0으로 이동
			rear = 0;
		}

		return x;
	}

	public int deque() {
		if (num <= 0) {
			throw new EmptyIntQueueException();
		}

		int x = que[front++]; // front의 위치에 데이터를 꺼내고 1을 증가시킨다.
		num--; // 현재 데이터수 1감소
		if (front == max) { // front가 max와 같아지게 되면 ArrayIndexOutOfBoundsException가 발생하기 때문에 front를 0으로 이동
			front = 0;
		}

		return x;
	}

	public int peek() {
		if (num <= 0) {
			throw new EmptyIntQueueException();
		}

		return que[front];
	}

	public int indexOf(int x) {
		for (int i = 0; i < num; i++) {
			int idx = (i + front) % max; // front부터 검색하여 max를 넘으면 나머지 값으로 검색
			if (que[idx] == x) {
				return idx;
			}
		}

		return -1;
	}

	// 큐를 비움
	public void clear() {
		num = 0;
		front = 0;
		rear = 0;
	}

	// 큐의 최대용량 반환
	public int capacity() {
		return max;
	}

	// 큐의 데이터 수 반환
	public int size() {
		return num;
	}

	// 큐가 비어있는지 여부
	public boolean isEmpty() {
		return num <= 0;
	}

	// 큐가 가득찼는지 여부
	public boolean isFull() {
		return num >= max;
	}

	// 큐안의 데이터를 출력
	public void dump() {
		if (num <= 0) {
			System.out.println("데이터가 존재하지 않습니다.");
		} else {
			for (int i = 0; i < num; i++) {
				System.out.println(que[(i + front) % max]);
			}
		}
	}
}