배열을 이용한 큐 구현하기

06 Nov 2023

javascript

큐는 데이터를 선입선출(FIFO - First-In-First-Out) 순서로 처리하기 위한 자료구조입니다. 이번에는 배열을 이용하여 큐를 구현하는 방법에 대해서 알아보겠습니다.

1. 배열과 변수 선언하기

우선 큐의 요소들을 저장하기 위한 배열과 큐의 시작과 끝 위치를 나타내는 변수를 선언합니다.

int[] queue;
int front;
int rear;

2. 큐 초기화하기

큐를 초기화하기 위해 배열의 크기를 설정하고 front와 rear 변수를 초기값으로 설정합니다.

public void initializeQueue(int size) {
    queue = new int[size];
    front = -1;
    rear = -1;
}

3. 큐에 데이터 추가하기 (Enqueue)

Enqueue 작업은 큐의 끝(rear)에 새로운 데이터를 추가하는 것입니다.

public void enqueue(int data) {
    // 큐가 비어있을 경우
    if (front == -1) {
        front = 0;
        rear = 0;
    } 
    // 큐가 가득 차있을 경우
    else if (rear == queue.length - 1) {
        System.out.println("Queue is full");
        return;
    } 
    // 일반적인 경우
    else {
        rear++;
    }
    
    queue[rear] = data;
}

4. 큐에서 데이터 삭제하기 (Dequeue)

Dequeue 작업은 큐의 시작(front)에서 데이터를 제거하는 것입니다.

public int dequeue() {
    // 큐가 비어있을 경우
    if (front == -1) {
        System.out.println("Queue is empty");
        return -1; // 예외 처리를 위해 -1 반환
    }

    int data = queue[front];
    
    // 큐에 데이터가 하나만 남아있을 경우
    if (front == rear) {
        front = -1;
        rear = -1;
    } 
    // 일반적인 경우
    else {
        front++;
    }
    
    return data;
}

5. 큐의 상태 확인하기

큐는 비어있는지 (Empty) 혹은 가득 차있는지 (Full) 여부를 확인할 수 있습니다.

public boolean isEmpty() {
    return front == -1;
}

public boolean isFull() {
    return rear == queue.length - 1;
}

6. 큐의 데이터 출력하기

큐의 모든 데이터를 출력하는 작업입니다.

public void printQueue() {
    // 큐가 비어있을 경우
    if (front == -1) {
        System.out.println("Queue is empty");
        return;
    }

    System.out.print("Queue: ");
    for (int i = front; i <= rear; i++) {
        System.out.print(queue[i] + " ");
    }
    System.out.println();
}

7. 큐 구현 테스트하기

public static void main(String[] args) {
    QueueArray queue = new QueueArray();
    queue.initializeQueue(5);

    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(5);

    queue.printQueue(); // 출력: Queue: 1 2 3 4 5

    queue.dequeue();
    queue.dequeue();
    
    queue.printQueue(); // 출력: Queue: 3 4 5
}

위의 코드를 실행하면, 배열을 이용한 큐가 제대로 동작하는지 확인할 수 있습니다.

이렇게 배열을 이용하여 큐를 구현할 수 있습니다. 다음에는 연결 리스트를 이용한 큐 구현 방법에 대해서 알아보겠습니다.

참고 자료

해시태그

#자료구조 #배열 #큐