큐

큐(Queue)

큐는 프린터 작업 처리, 운영 체제의 프로세스 스케줄링, 네트워크 패킷 처리 등 다양한 분야에서 활용되는 자료구조입니다.

 

FIFO

Queue는 FIFO라는 특성을 가지는 데이터 구조 입니다.
FIFO는 선입선출(First In First Out)의 원칙을 말하는데, 먼저들어온 데이터가 먼저 처리된다는 의미입니다.

 

Queue의 구조와 구현

(이미지 출처 : geeksforgeeks.org)

삽입과 삭제

큐에 데이터를 추가하는 작업을 `enqueue` 삭제하는 작업을 `dequeue`라고 합니다.

 

Front와 Rear포인터

Queue자료구조에서 Front와 Rear 포인터는 큐의 시작과 끝을 나태는 두 가지 포인터입니다.

Front는 큐의 맨 앞 요소를 가리키고, Queue에서 요소를 제거할 때 사용됩니다.

Rear는 큐의 맨 뒤 요소를 가리키고, Queue에서 요소를 추가할 때 사용합니다.

(Front와 Rear 포인터가 같은 위치를 가리키는 경우 Queue가 비어있거나 모든 요소가 제거된 상태를 나타낸다는 것)

 

구현

public class Main {
    public class Queue<T> {
        private static final int DEFAULT_CAPACITY = 10; // 기본 용량 설정
        private Object[] array; // 큐 배열
        private int front; // 큐의 앞부분
        private int rear; // 큐의 뒷부분
        private int size; // 큐의 현재 크기

		// 기본 생성자
        public Queue() {
        	this(DEFAULT_CAPACITY);
        }
        
        // 용량을 설정하는 생성자
        public Queue(int capacity) {
            this.array = new Object[capacity];
            this.front = 0;
            this.rear = -1;
            this.size = 0;
        }
        
        // 큐에 값 추가
        public void enqueue(T item) {
            if(isFull()) {
                throw new IllegalStateException("큐가 가득 찼습니다.");
            }
            rear = (rear + 1) % array.length; // 큐의 뒷부분 변경
            array[rear] = item; // 데이터 삽입
            size++; // 사이즈 늘림
        }

        // 큐에서 값 제거
        public T dequeue() {
                if (isEmpty()) {
                    throw new IllegalStateException("큐가 비어있습니다.");
                }
                T item = (T) array[front]; // 값 꺼냄
                array[front] = null; // 참조 해제
                front = (front + 1) % array.length; // 큐의 앞부분 변경
                size--; // 사이즈 줄임
                return item; // 값 리턴
        }
		
		// 큐의 앞부분 값 확인
        public T peek() {
            if (isEmpty()) {
                throw new IllegalStateException("큐가 비어있습니다.");
            }
            return (T) array[front]; // 값 리턴
        }
        
        // 큐가 비어있는지 확인
        public boolean isEmpty() {
            return size == 0;
        }

        // 큐가 꽉 찼는지 확인
        public boolean isFull() {
            return size == array.length;
        }

        // 큐의 크기 확인
        public int size() {
            return size;
        }
    }

    public static void main(String[] args) {
        // 큐 생성
        Queue<Integer> queue = new Queue<>();

        // 큐에 데이터 추가
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);

        // 큐의 사이즈 출력
        System.out.println("큐의 사이즈: " + queue.size());

        // 큐의 데이터 출력
        System.out.println("맨 앞 요소: " + queue.peek());

        // 큐에서 데이터 제거
        System.out.println("삭제된 요소: " + queue.dequeue());

        // 데이터 제거 후 사이즈 출력
        System.out.println("삭제 후 사이즈: " + queue.size());
    }
}