[Java] 큐(Queue)의 개념과 구현

Queue란?

 

큐는 선형 자료구조 중 하나로 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO, First-In-First-Out) 형태의 자료구조이다.

큐에서 가장 먼저 들어온 데이터를 Front라고 하며 가장 먼저 나가게(삭제)된다.  Front가 나가고 나면 그 다음 데이터가 새로운 Front가 된다.

큐에서 가장 마지막에 입력된 데이터를 Rear라고 한다. 새로운 데이터는 기존 Rear 다음에 삽입되고 그 데이터가 새로운 Rear가 된다.

 

Queue Interface

 

Java에서 큐는 인터페이스(Interface)로 제공되며 주로 큐 인터페이스(Queue Interface)를 구현(Implement)한 연결리스트(LinkedList) (Queue Interface 를 상속받은 Deque Interface를 구현한 LinkedList) 등을 활용하여 큐를 구현하고 활용한다.

 

또한, Queue Interface를 상속받은  Deque Interface는 한 쪽 방향으로만 데이터의 삽입, 삭제가 가능한 Queue와는 달리, Dequeue(Double-ended Queue)라는 말 처럼 양 방향으로 데이터를 삽입, 삭제 할 수 있다.

 

Queue Interface에 정의된 메서드

 

	Throws exception	Returns special value
삽입	add(e)	offer(e)
삭제	remove()	poll()
검색	element()	peek()

 

큐 인터페이스에서 데이터의 삽입, 삭제, 검색(Front 반환)하는 메서드는 예를 들어 큐가 비어있는데 삭제를 하는 등 에러가 발생했을때 Exception을 발생시키는 메서드와 false나 null 등을 반환하는 메서드로 나눠져 있다.

 

자세한 내용은 아래의 공식 문서에서 확인이 가능하다.

Queue (Java Platform SE 8 )

 

Queue 구현

 

Java에서 큐 인터페이스는 `java.util`패키지에 속해 있고 , Collection Interface에서 상속받은 size, isEmpty, contains 메서드 등을 통해 큐의 사이즈, 비어 있는지 여부, 요소를 포함하고 있는지 여부 등을 확인 할 수 있다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

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

        System.out.println(queue); // 1 2 3 4 5

        System.out.println(queue.poll()); // 1
        System.out.println(queue); // 2 3 4 5

        System.out.println(queue.peek()); // 2
        System.out.println(queue); // 2 3 4 5

        System.out.println(queue.contains(5)); // true
        System.out.println(queue.size()); // 4
        System.out.println(queue.isEmpty()); // false

        queue.clear();
        System.out.println(queue); // []
        System.out.println(queue.poll()); // null

    }
}