큐
큐(Queue)는 데이터를 일렬로 나열한 자료구조로, 데이터의 삽입은 한쪽 끝(rear 또는 tail)에서 이루어지고, 삭제는 반대쪽 끝(front 또는 head)에서 이루어지는 구조를 가지고 있습니다.
큐의 특징
- FIFO(First In First Out) : 가장 먼저 삽입된 요소가 가장 먼저 삭제된다.
- 데이터의 삽입은 큐의 뒤(rear)에서 삭제는 큐의 앞(front)에서 이루어진다.
큐의 종류
1. 선형 큐(Linear Queue)
- 배열을 기반으로 한 일반적인 큐 구현
- 배열의 처음과 끝을 각각 front와 rear로 가리키며, 요소를 추가하거나 삭제할 때 front와 rear가 이동한다.
- 한계점
배열 기반이기 때문에 큐의 크기가 고정되어 있어, 큐가 가득 찬 경우에는 더이상 요소를 추가할 수 없다.
이로 인해 큐의 상태가 가득 찼음에도 불구하고 비어있다고 인식하는 경우가 발생할 수 있다. - 이를 해결하기 위해 원형(환형)큐가 도입되었다.
2. 원형 큐(Circle Queue)
- 큐의 끝 부분이 시작 부분과 연결된 원형 구조를 가지고 있습니다. 배열 기반이나 연결 리스트 기반으로 구현됩니다.
3. 우선순위 큐(Priority Queue)
- 각 요소에 우선순위를 부여하고, 우선순위가 높은 요소가 먼저 나가는 큐입니다. 힙(Heap) 자료구조를 기반으로 우선순위 큐를 구현하는 경우가 많습니다.
4. 데크 (Deque-Double-Ended Queue)
- 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다. 스택과 큐의 기능을 모두 제공하는 자료구조입니다.
큐의 구현
자바에서는 java.util.Queue 인터페이스를 제공한다.
대표적으로 LinkedList와 ArrayDeque가 있다.
1. 배열 기반 선형 큐 구현
public class LinearQueue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
public LinearQueue(int size) {
maxSize = size + 1; // 한 칸은 비워두어야 하므로 크기를 1 증가시킴
queueArray = new int[maxSize];
front = rear = 0; // 초기에 front와 rear는 같은 위치에 있음
}
public void enqueue(int item) {
if (!isFull()) {
queueArray[rear] = item;
rear = (rear + 1) % maxSize;
System.out.println("Enqueued: " + item);
} else {
System.out.println("Queue is full. Cannot enqueue " + item);
}
}
public int dequeue() {
if (!isEmpty()) {
int dequeuedValue = queueArray[front];
front = (front + 1) % maxSize;
System.out.println("Dequeued: " + dequeuedValue);
return dequeuedValue;
} else {
System.out.println("Queue is empty. Cannot dequeue.");
return -1; // 큐가 비어있을 때는 임의의 값(-1) 반환
}
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
public static void main(String[] args) {
// 선형 큐 생성 (최대 크기: 5)
LinearQueue queue = new LinearQueue(5);
// 큐에 요소 추가
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// 큐의 현재 맨 앞 요소 확인
System.out.println("Front element: " + queue.queueArray[queue.front]);
// 큐에서 요소 제거
queue.dequeue();
queue.dequeue();
// 큐이 비어있는지 여부 확인
System.out.println("Is queue empty? " + queue.isEmpty());
// 큐에 요소 추가
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6); // 큐가 가득 차서 추가되지 않음
}
}
2. 배열 기반 원형 큐 구현
public class CircularQueue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
public CircularQueue(int size) {
maxSize = size + 1; // 한 칸은 비워두어야 하므로 크기를 1 증가시킴
queueArray = new int[maxSize];
front = rear = 0; // 초기에 front와 rear는 같은 위치에 있음
}
public void enqueue(int item) {
if (!isFull()) {
queueArray[rear] = item;
rear = (rear + 1) % maxSize;
System.out.println("Enqueued: " + item);
} else {
System.out.println("Queue is full. Cannot enqueue " + item);
}
}
public int dequeue() {
if (!isEmpty()) {
int dequeuedValue = queueArray[front];
front = (front + 1) % maxSize;
System.out.println("Dequeued: " + dequeuedValue);
return dequeuedValue;
} else {
System.out.println("Queue is empty. Cannot dequeue.");
return -1; // 큐가 비어있을 때는 임의의 값(-1) 반환
}
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
public static void main(String[] args) {
// 원형 큐 생성 (최대 크기: 5)
CircularQueue queue = new CircularQueue(5);
// 큐에 요소 추가
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// 큐의 현재 맨 앞 요소 확인
System.out.println("Front element: " + queue.queueArray[queue.front]);
// 큐에서 요소 제거
queue.dequeue();
queue.dequeue();
// 큐이 비어있는지 여부 확인
System.out.println("Is queue empty? " + queue.isEmpty());
// 큐에 요소 추가
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6); // 큐가 가득 차서 추가되지 않음
}
}
3. 연결 리스트 기반 원형 큐 구현
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularQueueLinkedList {
private Node front;
private Node rear;
public CircularQueueLinkedList() {
this.front = null;
this.rear = null;
}
public void enqueue(int item) {
Node newNode = new Node(item);
if (isEmpty()) {
front = rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
rear.next = front; // 연결 리스트를 원형으로 만듦
System.out.println("Enqueued: " + item);
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1; // 큐가 비어있을 때는 임의의 값(-1) 반환
}
int dequeuedValue = front.data;
if (front == rear) {
front = rear = null; // 큐에 마지막 요소가 있었다면 큐를 비움
} else {
front = front.next;
rear.next = front; // 연결 리스트를 원형으로 유지
}
System.out.println("Dequeued: " + dequeuedValue);
return dequeuedValue;
}
public boolean isEmpty() {
return front == null && rear == null;
}
public static void main(String[] args) {
// 연결 리스트를 기반으로 한 원형 큐 생성
CircularQueueLinkedList queue = new CircularQueueLinkedList();
// 큐에 요소 추가
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// 큐에서 요소 제거
queue.dequeue();
queue.dequeue();
// 큐이 비어있는지 여부 확인
System.out.println("Is queue empty? " + queue.isEmpty());
// 큐에 요소 추가
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
}
}큐의 활용 예시
1. 작업 대기열
여러 작업이 동시에 발생할 때, 작업이 큐에 삽입되고 가장 먼저 들어온 작업니 가장 먼저 처리됩니다.
2. BFS(너비 우선 탐색) 알고리즘
그래프에서 너비 우선 탐색을 수행할 때 큐를 사용하여 레벨 단위로 탐색합니다.
3. 프린터 대기열
여러 문서가 프린터에 출력되기를 기다리는 경우, 가장 먼저 들어온 문서가 가장 먼저 출력됩니다.
Reference
develop