[Java] 원형 큐(Queue) 구현하기

안녕하세요 이번에는 선형 큐를 원처럼 이은 원형 큐(Queue)에 대해 알아보겠습니다.

원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 선형 큐의 문제점은배열의 가장 앞에 있는 데이터를 꺼내오기 때문에 그 다음 인덱스의 데이터들을 한 칸씩 밀어야 하는 단점이 있습니다. 이 과정은 자료 하나를 꺼낼 때마다 반복문으로 수행되며, O(n)만큼의 시간 복잡도를 요구하므로 상당히 비효율적입니다.

1. 원형 Queue 분석

원형 Queue도 선형 Queue와 마찬가지로 1차원 배열을 사용하여 구현합니다. 하지만 선형 Queue와는 다르게 Shift를 해서 앞으로 밀지 않습니다. 배열을 선형으로 사용하여 삽입을 계속해야 하는 선형 Queue의 데이터를 넣을 때마다 번거로움이 있다는 단점을 해결합니다. 또한 인덱스는 감소하지 않고 증가만 하면서 사용하는 방식이기에, 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없기 때문에 비효율적인 부분이 있습니다.

Front와 Rear가 큐 사이즈 내에서 회전합니다.

 

Front = (Front + 1) % queue.length;
Rear = (Rear + 1) % queue.length;

원형 큐를 구현하기 위해 다음과 같은 공식을 사용합니다.

 

2. 코드 구현

① 필드

package circularqueue;

import java.util.Scanner;

import queue.Queue;

public class CircularQueue {
	int[] queue; // queue배열
	int front; // queue의 맨 앞
	int rear; // queue의 맨 뒤
	Scanner sc; // 스캐너

원형 큐(Queue) 역시 패키지를 따로 만들고, Scanner를 import합니다. 필드에는 Queue 배열과, Queue 배열의 맨 앞인 front, 맨 뒤인 rear, Scanner를 정의합니다.

② isFull 메서드

// 큐가 꽉 찼는지 확인
public boolean isFull() {
	return front == (rear + 1) % queue.length;
}

isFull 메서드는 Queue가 꽉 차있는지 확인합니다. return 문에서는 큐가 꽉 차면 반환합니다. 예를 들어, front가 0이고 rear가 4이면 (4+1)%5 = 0 이므로 front와 값이 같기 때문에 큐가 꽉 찼다는 것이 확인됩니다.

③ enqueue 메서드

// 큐에 데이터를 넣음
public void enqueue() {

	if (isFull()) {
		System.out.println("큐가 꽉찼습니다.");
		return;
	}

	// 데이터 입력
	System.out.println("Input your data");
	int data = sc.nextInt();

	queue[rear] = data;
	rear++;
	rear %= queue.length;

}

enqueue 메서드는 큐에 데이터를 넣는 메서드입니다. 만약 큐에 데이터가 가득 차 있으면 isFull 메서드를 조건에 넣어주괴고, 하나라도 비어 있으면 데이터를 입력받아 큐에 넣어줍니다. 위의 공식을 코드로 구현하였습니다.

④ dequeue 메서드

public boolean dequeue() {

	queue[front] = 0;
	front++;
	front %= queue.length;
	return true;

}

dequeue 메서드는 큐에서 데이터를 빼는 메서드입니다. 위의 공식을 사용하여 코드로 구현하였습니다.

⑤ print 메서드

// 화면 출력 및 선택
public void print() {
	while (true) {
		System.out.println("=======원형 Queue=======");
		System.out.println("1. Enqueue  ||  2. Dequeue  ||  3. Exit");
		System.out.print("Select : ");
		int num = sc.nextInt();

		// 선택 1. Enqueue
		if (num == 1) {
			enqueue();
			for (int i = 0; i < queue.length; i++) {
				System.out.print(queue[i] + " ");
			}
			System.out.println("Enqueue 성공");
			System.out.println();
		}

		else if (num == 2) {
			boolean check = false;
			check = dequeue();

			if (check == true) {
				System.out.println("Dequeue 성공");
			}

			for (int i = 0; i < queue.length; i++) {
				System.out.print(queue[i] + " ");
			}
			System.out.println();
		}

		else if (num == 3) {
			System.out.println("Finish");
			break;
		}
	}
}

print 메서드는 화면에 출력을 해줍니다. 사용자로부터 Enqueue 인지 Dequeue 인지 입력을 받아 메서드를 불러옵니다. 데이터 0을 넣으면 화면에서 볼 수 없기 때문에 Enqueue와 Dequeue가 성공했다고 출력해 줬습니다.

⑥ 생성자

// 생성자에서 초기화
public CircularQueue() {
	queue = new int[5];
	front = 0;
	rear = 0;

	sc = new Scanner(System.in);
}

필드 값들을 생성자에서 초기화했습니다. 필드에서 직접 초기화 하지 않고, 생성자에서 따로 초기화했습니다.

⑦ main 함수

public static void main(String[] args) {
	CircularQueue q = new CircularQueue();

	q.print();
   }
}

main 함수에서는 Queue 생성자 q를 만들고, q.print();로 print 메서드를 호출했습니다. main 함수는 최대한 간결하게 작성하였습니다.

3. 실행 결과

정상적으로 출력되는 것을 확인할 수 있습니다. 6과 7이 원형으로 성공적으로 구현했습니다.