이 글에서는 Java를 사용해 큐(Queue) 자료구조를 구현하는 방법을 알아봅니다. 큐는 연산이 수행되는 순서가 정해져 있는 선형(linear) 자료구조로, 가장 먼저 들어간 요소가 가장 먼저 나오는 FIFO(First In First Out, 선입선출) 방식을 따릅니다.
실제 동작 예시는 다음과 같습니다.
입력값 −
Input Queue: [150, 300, 450, 600]
기대 출력 결과 −
After removing an element, the elements of the queue are: [300, 450, 600]
즉, 맨 앞의 요소 150이 제거되고 나머지 요소들이 그대로 유지됩니다.
알고리즘 단계
Step 1 - 시작 Step 2 - 큐 선언 Step 3 - 'offer' 메서드를 사용해 요소 추가 Step 4 - 큐의 현재 내용 출력 Step 5 - 'poll' 메서드를 사용해 큐에서 요소 삭제 Step 6 - 'poll' 메서드 호출 후 큐의 요소 출력 Step 7 - 결과 출력 Step 8 - 종료
예제 1: 내장 라이브러리 활용
첫 번째 예제에서는 Java에서 기본 제공하는 Queue 인터페이스와 LinkedList 클래스를 활용해 모든 큐 연산을 수행합니다. 이 방식은 별도의 로직 구현 없이 간편하게 큐를 사용할 수 있다는 장점이 있습니다.
import java.util.Queue;
import java.util.LinkedList;
public class Demo {
public static void main(String[] args) {
System.out.println("필요한 패키지가 임포트되었습니다");
Queue<Integer> input_queue = new LinkedList<>();
input_queue.offer(150);
input_queue.offer(300);
input_queue.offer(450);
input_queue.offer(600);
System.out.println("정의된 큐: " + input_queue);
int removedNumber = input_queue.poll();
System.out.println("요소 제거 후 큐의 상태: " +input_queue);
}
}출력 결과
The required packages have been imported The queue is defined as: [150, 300, 450, 600] After removing an element, the elements of the queue are: [300, 450, 600]
여기서 offer() 메서드는 큐의 뒤쪽(rear)에 요소를 추가하고, poll() 메서드는 큐의 앞쪽(front)에 있는 요소를 제거하면서 반환합니다.
예제 2: 사용자 정의 클래스로 직접 구현
두 번째 예제에서는 라이브러리에 의존하지 않고, 배열과 인덱스(front, rear)를 직접 관리하는 사용자 정의 함수로 큐를 구현합니다. 이 방식은 큐의 내부 동작 원리를 깊이 이해하는 데 도움이 됩니다.
public class Queue {
int SIZE = 5;
int items[] = new int[SIZE];
int front, rear;
Queue() {
front = -1;
rear = -1;
}
boolean isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
return false;
}
boolean isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
System.out.println("
The queue is full");
}
else {
if (front == -1) {
front = 0;
}
rear++;
items[rear] = element;
System.out.println("
The element " + element + " is inserted");
}
}
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("
The queue is empty");
return (-1);
}
else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
}
else {
front++;
}
System.out.println("
The element " +element + " is deleted");
return (element);
}
}
void display() {
int i;
if (isEmpty()) {
System.out.println("The queue is empty ");
}
else {
System.out.println("
The elements of the queue are: ");
for (i = front; i <= rear; i++)
System.out.print(items[i] + " ");
}
}
public static void main(String[] args) {
Queue input_queue = new Queue();
for(int i = 1; i < 6; i ++) {
input_queue.enQueue(i * 100);
}
System.out.println("The queue is defined as: " + input_queue);
input_queue.enQueue(6);
input_queue.display();
input_queue.deQueue();
input_queue.display();
}
}출력 결과
The element 100 is inserted The element 200 is inserted The element 300 is inserted The element 400 is inserted The element 500 is inserted The queue is defined as: Queue@2a139a55 The queue is full The elements of the queue are: 100 200 300 400 500 The element 100 is deleted The elements of the queue are: 200 300 400 500
주요 메서드 설명
- enQueue(element): 큐가 가득 찼는지 확인한 후, 여유 공간이 있으면 뒤쪽(rear)에 새 요소를 삽입합니다.
- deQueue(): 큐가 비어 있는지 확인한 후, 비어 있지 않으면 앞쪽(front)의 요소를 제거하고 반환합니다. 마지막 남은 요소를 제거할 때는 front와 rear를 초기화(-1)하여 큐를 재사용 가능한 상태로 만듭니다.
- isFull() / isEmpty(): 큐의 포화 상태와 공백 상태를 판별하는 보조 메서드입니다.
- display(): front부터 rear까지의 모든 요소를 순서대로 출력합니다.
마무리
큐는 작업 스케줄링, 버퍼 처리, BFS(너비 우선 탐색) 등 다양한 분야에서 활용되는 핵심 자료구조입니다. Java의 내장 Queue 인터페이스를 사용하면 빠르게 개발할 수 있고, 직접 구현해 보면 내부 동작 원리를 확실히 익힐 수 있습니다. 두 가지 방식을 모두 이해하고 상황에 맞게 선택하는 것이 좋습니다.