[바미] 자료구조 - 큐(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");
}

그 후 비어있는 지 확인하기 위해 출력해줍니다.