큐

큐

@24.03.21

큐(First In, First Out → FIFO)

💡

추상 데이터 타입 중 하나로, 처음에 들어온 요소가 가장 먼저 나가는 구조 → 선입선출

• 데이터를 일시적으로 보관해야 할 때 유용

• 예시
  • 프린터의 인쇄 작업 관리
  • 운영 체제에서의 작업 스케줄링
  • 네트워크 요청의 처리 순서 관리
  • 은행, 카페, 테마파크 진행 순서

• 주요 연산
  • Enqueue : 큐의 뒤쪽에 새로운 요소 추가
  • Dequeue : 큐의 앞쪽에서 요소를 제거하고 그 값을 반환
  • Peek/Front : 큐의 맨 앞에 있는 요소를 반환(제거는 하지 않는다.)
  • IsEmpty : 큐가 비어있는지 확인

• 기본적인 기능을 가진 스택 구현 ⇒ 원형 큐

class Queue {
    private int[] queueArray; // 큐를 저장할 배열
    private int maxSize; // 큐의 최대 크기
    private int front; // 큐의 맨 앞 요소를 가리키는 인덱스
    private int rear; // 큐의 맨 뒤 요소를 가리키는 인덱스

    // 큐 생성자
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        queueArray = new int[maxSize];
        front = -1; // 큐가 비어있는 상태를 나타내는 초기 값
        rear = -1; // 큐가 비어있는 상태를 나타내는 초기 값
    }

    // 큐의 뒤쪽에 새로운 요소 추가
    public void enqueue(int x) {
        if (isFull()) { // 큐가 가득 찼는지 확인
            System.out.println("큐가 가득 찼습니다.");
            return;
        }
        if (isEmpty()) { // 큐가 비어있는지 확인하여 front와 rear 초기화
            front = 0;
        }
        // 현재 rear의 위치에서 한칸 두위 위치 -> 새로운 요소가 추가될 위치
        // %maxSize한 이유는 큐의 최대 크기를 넘어가면 처음으로 돌아가는 것을 생각 
        rear = (rear + 1) % maxSize;  
        queueArray[rear] = x; // rear 위치에 새로운 요소 추가
     
    }

    // 큐의 앞쪽에서 요소를 제거하고 그 값을 반환
    public int dequeue() {
        if (isEmpty()) { // 큐가 비어있는지 확인
            System.out.println("큐가 비어있습니다.");
            return -1;
        }
        int temp = queueArray[front]; // front 위치의 요소를 임시 변수에 저장
        queueArray[front] = 0; // front 위치의 요소 제거 (0으로 초기화)
        if (front == rear) { // 큐에 요소가 하나만 남았을 때 front와 rear 초기화
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % maxSize; // front를 순환하며 위치 지정
        }
        return temp; // 제거한 요소 반환
    }

    // 큐의 맨 앞에 있는 요소를 반환
    public int peek() {
        if (isEmpty()) { // 큐가 비어있는지 확인
            System.out.println("큐가 비어있습니다.");
            return -1;
        }
        return queueArray[front]; // front 위치의 요소 반환
    }

    // 큐가 비어있는지 확인
    public boolean isEmpty() {
        return front == -1; // front가 -1이면 큐가 비어있는 상태
    }

    // 큐가 가득 찼는지 확인
    public boolean isFull() {
        return (rear + 1) % maxSize == front; // rear 다음 위치가 front이면 큐가 가득 찬 상태
    }
}