[자료구조 Java] 큐(Queue) 개념 정리 + 자바로 구현하기

 

 

Queue(큐)는 Stack(스택)과 반대로 선입선출(First In First Out, FIFO)의 특징을 가지고 있다. 먼저 들어온 것이 먼저 나간다는 FIFO는 일상생활에서의 줄서기, 마트 재고관리부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) 알고리즘까지 다양한 곳에서 이용되고 있다. 이번 글에서는 큐에 대해 간단히 알아보고 이를 직접 자바로 구현해 본다.

 

FIFO

 

Queue는 Stack과 마찬가지로 배열과 리스트 두 가지 방법으로 구현할 수 있다.

 

배열로 구현한 Queue

 

전체 구조

배열을 이용하여 큐를 만드는 경우 다음과 같은 원형 큐 형태로 구현해야 한다. 원형 큐 형태를 구현함으로서 배열의 첫 데이터의 index가 0이 아닐 수도 있게 된다. 이를 통해 배열의 마지막 index에 데이터가 있어도 앞서 들어온 데이터를 꺼내 앞쪽 index의 배열은 비어있는 경우 앞 index의 요소들에도 데이터를 넣을 수 있어 FIFO 구현이 간단해진다.

 

원형 큐는 나머지 연산(%)를 통해 구현한다.

front = front % queue.length()를 하면 해당 큐의 길이보다 크거나 같은 index가 들어오면 나머지 연산자를 통해 항상 큐의 길이보다 작도록 index를 유지한다.

 

front는 queue에서 가장 먼저 나가야 하는 데이터(가장 최근 들어온 데이터)의 index를 저장한다.

rear는 queue로 다음 데이터가 들어올 index를 저장한다.

 

public class StackQueue {
    int length;
    int front = 0;
    int rear = 0;
    Object[] queue;
    
    ...
    
    }

 

구현할 함수는 다음과 같다.

enqueue(Object data) : 데이터를 넣는 함수

dequeue() : 데이터를 꺼내는 함수

peek() : 앞으로 꺼낼 데이터가 무엇인지 확인하는 함수

isEmpty() : 큐가 비었는지 확인하는 함수

isFull() : 큐가 꽉 찼는지 확인하는 함수

 

구현시 주의할 점은 데이터를 넣거나 데이터를 꺼낼 때 큐가 비었거나 꽉 찼는지 미리 확인하는 것이 필요하다는 것이다.

 

isFull(): 큐가 꽉 찼는지 확인하는 함수

 

큐가 꽈 찼는지 확인하는 것은 front와 rear가 같은지 + 같다면 해당 index의 배열 위치에 null 값이 있는지 체크하면 된다. null값이라면 큐가 비어있는 것이고 null값이 아니라면 꽉 찬 것이다.

    public boolean isFull(){
        return front == rear && queue[front] != null;
    }

 

isEmpty(): 큐가 비었는지 확인하는 함수

1. front와 rear에 저장된 index값이 동일한지 확인

2. 동일하다면 해당 index의 배열 위치에 null값이 있는지 확인

    public boolean isEmpty(){
        return front == rear && queue[front] == null;
    }

 

enqueue(): 큐에 데이터를 넣는 함수

1. 큐가 꽉 찼는지 확인( isFull함수 사용)
2. rear가 가리키는 index로 접근, 데이터를 삽입
3. rear값 1 증가
4. rear값이 배열의 크기 넘지 못하도록 나머지 연산(%)

    public void enqueue(Object data){
        if(isFull()) {
            System.out.println("큐에 더 이상 데이터를 저장할 공간이 없습니다.");
            return;
        }
        queue[rear++] = data;
        rear = rear % queue.length;
    }

 

dequeue(): 큐에서 데이터를 꺼내는 함수

1. 큐가 비어있는지 확인 (isEmpty함수 사용)
2. front가 가리키는 index로 접근하여 데이터를 임시저장
3. 다시 해당 index로 접근하여 null값 삽입
4. front값 1증가
5. front 값이 배열의 크기가 넘지 못하도록 나머지 연산(%)

 

peek함수의 경우 단순히 front가 가리키는 index로 배열에 접근하여 그 값을 리턴하면 된다.

 

public Object dequeue(){
        if(isEmpty()){
            System.out.println("큐가 비어있습니다");
            throw new ArrayIndexOutOfBoundsException();
        }

        Object dequeuedData = queue[front];
        queue[front++] = null;
        front = front % queue.length;

        return dequeuedData;
    }

 

 

 

리스트를 이용한 Queue 구현

 

전체구조

front와 rear 변수는 배열로 구현한 queue와는 조금 다른데 front는 가장 먼저 들어온 노드를, rear는 가장 나중에 들어온 노드를 가리키는 참조 변수이다. 데이터를 꺼내는 경우 front가 가리키는 노드를, 데이터를 넣는 경우 rear가 가리키는 노드의 다음 노드로 연결한다.

리스트는 배열처럼 고정되어 있지 않기에 별도로 리스트가 꽉 찼는지 확인할 필요는 없고 단지 리스트가 비어있는 경우만 고려하면 된다.

 

public class Node<T> {
    Node<T> next = null;
    T data = null;
}

public class ListQueue<T> {
    Node<T> front = null;
    Node<T> rear = null;
    ...
    }

 

구현할 함수는 다음과 같다.

enqueue(Object data) : 데이터를 넣는 함수

dequeue() : 데이터를 꺼내는 함수

peek() : 앞으로 꺼낼 데이터가 무엇인지 확인하는 함수

isEmpty() : 큐가 비었는지 확인하는 함수

 

isEmpty: 큐가 비었는지 확인하는 함수

 

 

그림은 큐가 비어있는 경우이다. 노드가 존재하지 않기에 front, rear 참조변수 모두 null을 가리키고 있음을 알 수 있다. 단순히 front 참조 변수만 null인지 확인하여도 무방하다.

 

    public boolean isEmpty() {
        return front == null;
    }

 

enqueue: 큐에 데이터를 넣는 함수

 

경우1. 큐가 비어있는 경우

 

 

 

1. 새로운 노드를 생성
2. front와 rear 변수에 새로운 노드의 주소를 저장한다.

 

경우2. 큐가 비어있지 않은 경우

1. 새로운 노드를 생성한다.
2. rear가 가리키는 노드의 next 변수에 새로운 노드의 주소를 저장한다.
3. rear에 새로운 노드의 주소를 저장한다.

    public void enqueue(T data) {
        Node<T> newNode = new Node<T>();
        newNode.data = data;

        if (isEmpty())
            front = newNode;
        else
            rear.next = newNode;
        rear = newNode;
    }

 

dequeue: 큐에 데이터를 빼는 함수

 

 

경우1. 큐에 노드가 2개 이상인 경우

1. 큐가 비어있는지 확인
2. front를 front가 가리키던 노드의 다음 노드 주소로 변경한다.

기존 front가 가리키던 노드는 더 이상 자신을 참조하는 곳이 없기에 Garbage Collecor에 의해 메모리가 해제된다.

 

 

경우2. 큐에 노드가 1개인 경우

1. 큐가 비어있는지 확인
2. front와 rear 참조변수 모두에 null값을 저장한다. 마찬가지로 Garbage Collector에 의해 참조되지 않는 객체 노드는 자동으로 메모리가 해제된다.

    public T dequeue(){
        if(isEmpty()){
            System.out.println("큐가 비었습니다");
            return null;
        }

        T data = front.data;

        if (front == rear) {
            //큐에 노드가 1개인 경우
            front = null;
            rear = null;
        } else {
            //큐에 노드가 2개 이상인 경우
            front = front.next;
        }

        return data;
    }

 

코드 실행

public class Main {
    public static void main(String[] args) {
        System.out.println("------Stack으로 구현한 Queue------");
        StackQueue stackQueue = new StackQueue(100);
        int numberOfData = 5;

        for (int i = 0; i < numberOfData; i++) {
            stackQueue.enqueue(i);
            System.out.printf("%d를 Queue에 enqueue\n", i);
        }

        System.out.println("peek연산 결과: " + stackQueue.peek());

        for (int i = 0; i < numberOfData; i++) {
            System.out.print(stackQueue.dequeue() + " ");
        }

        //ArrayIndexOutOfBoundsException예외 발생
//        System.out.println(stackQueue.dequeue());


        System.out.println("\n------List로 구현한 Queue------");
        ListQueue<Integer> listQueue = new ListQueue();

        for (int i = 0; i < numberOfData; i++) {
            listQueue.enqueue(i);
            System.out.printf("%d를 Queue에 enqueue\n", i);
        }
        System.out.println("peek연산 결과: " + listQueue.peek());

        for (int i = 0; i < numberOfData; i++) {
            System.out.print(listQueue.dequeue() + " ");
        }

        //큐가 비어있는데 dequeue하려는 경우 오류 발생
//        System.out.println();
//        System.out.println(listQueue.dequeue());
    }
}

 

- 실행 결과 -

전체 코드

https://github.com/you88311/data-structure/tree/main/queue

GitHub - you88311/data-structure

 

---

참고

 

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼

 

C언어로 쉽게 풀어쓴 자료구조 - 천인국 공용해 하상호 지음