[바미] 자료구조 - 큐(Queue)
큐(Queue)
큐(Queue)는 자료 구조의 하나로, 데이터가 FIFO(First In, First Out) 방식으로 관리되는 구조입니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 제거됩니다.
그리고 큐는 주로 운영 체제의 작업 스케줄링, 프린터 작업 관리, 데이터 스트리밍 등 다양한 분야에서 사용됩니다.
큐는 용도에 따라 종류가 다양하니 큐의 종류에 대해 추가로 살펴보시는 것을 추천드립니다.
큐의 주요 연산
큐는 선형 자료 구조로 불리고, 두 개의 주요 연산을 제공합니다.
- Enqueue: 큐의 끝에 데이터를 삽입하는 연산.
- Dequeue: 큐의 앞에서 데이터를 제거하고 반환하는 연산.
코드(Java)
// 큐 클래스 정의
class Queue {
private int[] arr; // 큐의 요소를 저장할 배열
private int front; // 큐의 앞쪽 인덱스
private int rear; // 큐의 뒤쪽 인덱스
private int capacity; // 큐의 최대 크기
private int count; // 현재 큐에 저장된 요소의 수
// 큐 생성자
public Queue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}
// 큐에 요소를 추가
public void enqueue(int item) {
if (isFull()) {
System.out.println("Queue is full");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}
// 큐에서 요소를 제거
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int item = arr[front];
front = (front + 1) % capacity;
count--;
return item;
}
// 큐가 비어있는지 확인
public boolean isEmpty() {
return count == 0;
}
// 큐가 꽉 찼는지 확인
public boolean isFull() {
return count == capacity;
}
// 큐의 크기 반환
public int size() {
return count;
}
// 큐의 첫 번째 요소 반환
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
return arr[front];
}
}
public class QueueExample {
public static void main(String[] args) {
// 크기가 5인 새로운 큐 생성
Queue queue = new Queue(5);
// 큐에 요소를 추가
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
// 큐의 첫 번째 요소 출력
System.out.println("Front element is: " + queue.peek());
// 큐에서 요소 제거
queue.dequeue();
// 큐의 첫 번째 요소 출력
System.out.println("Front element is: " + queue.peek());
// 큐의 크기 출력
System.out.println("Queue size is " + queue.size());
// 큐에서 모든 요소 제거
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();
// 큐가 비어있는지 확인하고 출력
if (queue.isEmpty()) {
System.out.println("Queue is empty");
}
}
}코드 설명
Queue 클래스와 Main이 되는 QueueExample 클래스로 나뉘어 있습니다.
Queue 클래스
필드
private int[] arr; // 큐의 요소를 저장할 배열
private int front; // 큐의 앞쪽 인덱스
private int rear; // 큐의 뒤쪽 인덱스
private int capacity; // 큐의 최대 크기
private int count; // 현재 큐에 저장된 요소의 수먼저 필드에 위 변수들을 선언시켜 주었습니다.
생성자
// 큐 생성자
public Queue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
count = 0;
}큐의 생성자 부분입니다. 먼저 큐의 크기를 설정하고, 배열을 초기화 해주고, front는 0으로, rear는 -1로 초기화하여 큐가 비어 있음을 나타내줍니다.
요소 추가 메소드
public void enqueue(int item) {
if (isFull()) {
System.out.println("Queue is full");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = item;
count++;
}큐에 요소를 추가해주는 메소드입니다. 큐가 가득 찬 경우 "Queue is full" 메시지를 출력하고, 그렇지 않으면 rear를 증가시키고 해당 위치에 요소를 추가해주죠.
요소 제거 메소드
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int item = arr[front];
front = (front + 1) % capacity;
count--;
return item;
}큐에서 첫 번째 요소를 제거하고 반환하는 메소드입니다. 먼저 큐가 비어 있는 경우 "Queue is empty" 메시지를 출력하고 -1을 반환하고, 그렇지 않으면 front를 증가시키고 해당 요소를 반환합니다.
체크 메소드
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == capacity;
}각 요소 삽입, 삭제 시 쓰이는 메소드입니다.
isEmpty 메소드에선 count가 0이면 큐가 비어 있음을 나타내고 true를 반환하고, isFull 메소드에선 count가 capacity와 같으면 큐가 가득 찼음을 나타내고 true를 반환합니다.
크기 조회 메소드
public int size() {
return count;
}큐의 현재 크기를 반환합니다.
큐의 첫 번째 요소 조회 메소드
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
return arr[front];
}큐의 첫 번째 요소를 반환해주는 메소드입니다.
큐가 비어 있는 경우 "Queue is empty" 메시지를 출력하고 -1을 반환하고, 그렇지 않으면 front 위치의 요소를 반환하죠.
QueueExample 클래스
Queue queue = new Queue(5);크키가 5인 새로운 큐를 생성하는 부분입니다.
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);그 후 각 요소들을 큐에 추가해주는 부분입니다.
System.out.println("Front element is: " + queue.peek());큐의 첫 번째 요소를 출력합니다. 현재 첫 번째 요소는 1이 됩니다.
queue.dequeue();큐에서 첫 번째 요소를 제거합니다. 그래서 첫 번째 요소 1이 제거되죠.
System.out.println("Front element is: " + queue.peek());
System.out.println("Queue size is " + queue.size());첫 번째 요소와 큐 크기를 출력하는 부분입니다.
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();모든 요소를 제거해줍니다.
if (queue.isEmpty()) {
System.out.println("Queue is empty");
}그 후 비어있는 지 확인하기 위해 출력해줍니다.