이 글에서는 선형 자료구조 중 하나인 큐(queue)에 대한 방대한 설명과 자바에서 큐를 사용하여 직접 구현한 예제 코드를 제공해 드리겠습니다. 큐의 개념과 원리를 살펴본 뒤, 자바에서 큐를 사용하는 방법과 기본 연산에 대해 알아보겠습니다. 이어서 배열 기반 큐 구현과 연결리스트 기반 큐 구현의 예시를 들겠습니다.
1. 큐의 개념 및 원리
큐(queue)는 "First In, First Out" (FIFO) 원칙에 따라 동작하는 선형 자료구조입니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지고 있습니다. 큐는 데이터의 삽입이 한쪽 끝(rear)에서 이루어지고, 삭제가 반대쪽 끝(front)에서 이루어지므로, 데이터 처리 순서가 중요한 경우 사용하기 적합합니다. 큐는 운영 체제에서의 작업 스케줄링, 너비 우선 탐색(BFS) 알고리즘, 인쇄 대기열 등에서 활용됩니다.
- 큐 장점
- 구현이 비교적 간단함
- 순차 처리에 적합한 자료구조
- 큐 기반 알고리즘에서 활용가 높음
- 큐의 단점
- 데이터 저장 용량이 제한적일 수 있음 (배열 기반 큐의 경우)
- 데이터 삽입과 삭제 위치 제한
2. 자바에서의 큐 사용법 및 주요 기능
자바에서 큐를 구현하려면 java.util.Queue 인터페이스를 사용할 수 있습니다. Queue 인터페이스는 다양한 자료형을 저장할 수 있도록 제네릭 형태로 제공됩니다.
- 큐 생성 및 초기화
Queue<Integer> queue = new LinkedList<>();
- 큐에 요소 추가 (enqueue 연산)
queue.add(1);
queue.add(2);
queue.add(3);
- 큐에서 요소 제거 및 반환 (dequeue 연산)
int dequeuedElement = queue.poll(); // 1 반환
- 큐의 가장 앞쪽 요소 반환 (peek 연산)
int frontElement = queue.peek(); // 2 반환
- 큐가 비어있는지 확인
isEmpty = queue.isEmpty(); // false 반환
- 큐의 크기 확인
int size = queue.size(); // 큐 크기 반환3. 자바 배열 기반 큐 구현 예시
다음제는 배열을 이용하여 큐를 구현한 코드입니다.
public class ArrayQueue {
private int maxSize;
private int front;
private int rear;
private int[] queueArray;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.queueArray = new int[maxSize];
this.front = 0;
this.rear = -1;
}
public void enqueue(int value) {
if (rear < maxSize - 1) {
queueArray[++rear] = value;
} else {
System.out.println("Queue is full. Cannot enqueue.");
}
}
public int dequeue() {
if (front <= rear) {
return queueArray[front++];
} else {
System.out.println("Queue is empty. Cannot dequeue.");
return -1;
}
}
public int peek() {
if (front <= rear) {
return queueArray[front];
} else {
System.out.println("Queue is empty. Cannot peek.");
return -1;
}
}
public boolean isEmpty() {
return front > rear;
}
public int size() {
return rear - front + 1;
}
}4. 자바 연결리스트 기반 큐 구현 예시
다음 예제는 연결리스트를 이용하여 큐를 구현한 코드입니다.
public class LinkedListQueue<T> {
private static class QueueNode<T> {
private T data;
private QueueNode<T> next;
public QueueNode(T data) {
this.data = data;
}
}
private QueueNode<T> front;
private QueueNode<T> rear;
public void enqueue(T value) {
QueueNode<T> newNode = new QueueNode<>(value);
if (rear != null) {
rear.next = newNode;
}
rear = newNode;
if (front == null) {
front = newNode;
}
}
public T dequeue() {
if (front == null) {
System.out.println("Queue is empty. Cannot dequeue.");
return null;
}
T value = front.data;
front = front.next;
if (front == null) {
rear = null;
}
return value;
}
public T peek() {
if (front == null) {
System.out.println("Queue is empty. Cannot peek.");
return null;
}
return front.data;
}
public boolean isEmpty() {
return front == null;
}
public int size() {
int count = 0;
QueueNode<T> current = front;
while (current != null) {
count++;
current = current.next;
}
return count;
}
}5. 결론
이 글에서는 선형 자료구조 중 하나인 큐에 대해 자세히 설명하였습니다. FIFO 원칙에 따른 처리 순서 때문에 큐는 순차 처리에 적합한 자료조로 널리 사용됩니다. 자바의 기본 Queue 인터페이스를 사용하는 방법 외에도, 배열 기반 큐와 연결리스트 기반 큐를 구현하는 방법을 소개하였습니다. 이런 다양한 구현 방식을 숙지하여 문제 상황에 맞게 적절한 자료구조를 선택하고 활용하는 능력을 기르셔야 합니다.
'자료구조-알고리즘 > 선형 자료구조' 카테고리의 다른 글
| 선형 자료구조: 해시 테이블(Hash table) (0) | 2023.08.24 |
|---|---|
| 선형 자료구조: 데크(Deque) (0) | 2023.08.23 |
| 선형 자료구조: 스택(Stack) (0) | 2023.08.21 |
| 선형 자료구조: 연결리스트(Linked list) (0) | 2023.08.20 |
| 선형 자료구조: 배열(Array) (0) | 2023.08.19 |
