[ 자료구조 ] 큐 ( Queue ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.
가장 기본적인 구조로 선입선출 ( FIFO, First In First Out ) 방식을 가진다.
먼저 온 사람이 나가는 흔히 매장에 줄 서는 과정이라 볼 수 있다.
( Queue 단어 자체가 표 같은 것을 구매하기 위해 줄 서는 것을 의미 )

 

큐 ( Queue )

• 선입 선출 ( FIFO, First In First Out )
• 데이터가 들어오는 위치는 가장 뒤 Rear or Back 에서 이루어지고, 데이터가 나가는 위치인 가장 앞 Front, 양쪽에서 삽입 삭제가 이루어진다.
• BFS ( 너비 우선 탐색 ), 프로세서 핸들링 ( CPU 헤드링 ) 등에 사용.

class Queue{
    private LinkedList<Integer> queue;

    public Queue(){
        queue = new LinkedList<>();
    }
    ....
}

큐의 기본 연산

1. Enqueue(value): 데이터 삽입

• 큐의 맨 뒤(back)에 데이터를 추가하는 연산

    public void enQueue(int x){
        queue.addLast(x);
    }

 

2. Dequeue(): 데이터 제거

• 큐의 맨 앞(front)에 있는 데이터를 제거하고 반환하는 연산

    public int depQueue(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.removeFirst();
    }

3. peek() : 최상단 데이터 확인

• 큐의 맨 앞(front)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.getFirst();
    }

4. isEmpty(): 큐이 비어 있는지 확인

• 큐가 비어 있으면 true, 아니면 false 반환

    public boolean isEmpty(){
        return queue.isEmpty() ? true : false;
    }

로직 예시)

1. 빈 큐다

2. Enqueue ( 2 ) 를 통해 가장 앞 부터 채워 넣는다.

3. Enqueue ( 4 ) 를 통해 2 다음에(뒤에서부터) 채워 넣는다.

4. Dequeue 릍 통해 가장 앞에 있는 2를 꺼내고 4를 앞으로 옮긴다.

추가 - JAVA의 큐 관련 클래스

자바에서 큐는 Interface로 구현되어 ArrayDeque, LinkedList, PriorityQueue로 직접 구현할 수 있다.

그 밖에도 Blocking 즉 고정된 크기의 배열을 사용하는 큐도 존재한다.

이는 자바에서 원형 큐의 고정된 크기를 구현하기 위함으로 보인다.

이 글에서는 LinkedList로 정의된 큐와 달리 양쪽에서 삽입과 삭제가 이루어질 수 있는 양방향 큐이며, 메모리 동적인 요소를 가지고 있다.

 

ArrayDeque도 비슷하나 LinkedList와는 다르다. 배열로 사용되며 동적으로 변하긴 하지만, 배열을 다시 늘려야하는 번거로움이 있다. 추후 ArrayList와 LinkedList의 차이에 대해 포스팅할 예정이다.

DeQueue

 양방향에서 삽입/삭제가 이루어 질 수 있는 양방향 큐를 의미한다.

원형 큐

blocking으로 정의된 큐는 원형 큐라고 할 수 있으며 다음과 같은 형태을 가진다.

데이터가 삽입/삭제 됨에 따라 front와 back(rear)를 가리키는 위치가 계속 변하지만, 크기는 고정된 상태로 이루어진다.

다음과 같이 예시를 볼 수 있다.

PriorityQueue

우선순위 큐로 우선순위 비교는 Comparable interface를 활용하여 구현하거나 Comparator를 사용하여 설정할 수 있다.

중복 요소를 허용하고, 정렬된 순서로 요소를 처리하기 때문에 성능에 영향이 줄 수 있는 큐다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);

System.out.println(queue.poll());  // 1 (가장 작은 값이 먼저 출력됨)

PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
queue.add(1);
queue.add(3);
queue.add(2);

System.out.println(queue.poll());  // 3 (가장 큰 값이 먼저 출력됨)

이미 많고 다양한 큐가 만들어져 있기 때문에
편한 방법과 편한 클래스가 자바처럼 다양하게 존재하지만,
기본 자료구조를 이해하지 못한다면 활용하기가 어렵다.
때문에 그걸 사용하기 이전에 기본에 대한 이해를 점검하고 사용하도록 하자.
( ctrl + 클릭 을 통해 자바 클래스 내부를 확인 할 수 있다. )