[Java] 자바 큐(Queue) 인터페이스 정리

 

FIFO (First In First Out)

큐(Queue)는 먼저 넣은 객체가 먼저 빠져나가는 선입선출(FIFO : First In First Out) 자료구조이다.

자바의 컬렉션 프레임워크에는 후입선출(LIFO : Last In First Out) 자료구조를 제공하는 스택(Stack) 클래스와 FIFO 자료구조를 제공하는 큐(Queue) 인터페이스를 제공하고 있다.

 

큐(Queue)를 응용한 대표적인 예시로 BFS(너비 우선 탐색) 알고리즘과 스레드풀(ExceutorService)의 작업 큐이다. 작업 큐는 먼저 들어온 작업부터 처리하는 구조로 되어있다.

 

 

큐 (Queue)

Queue 인터페이스는 FIFO 자료구조에서 사용되는 메서드를 정의하고 있다. 이를 구현한 대표적인 클래스는 LinkedList이다.

LinkedList는 List 인터페이스를 구현하여 List 컬렉션이기도 하다. 따라서, Queue는 LinkedList 객체를 Queue 인터페이스 타입으로 변환하여 사용할 수 있다.

Queue<E> queue = new LinkedList<E>();

 

Queue 인터페이스 메서드

offer(E e)

주어진 객체를 넣는다. 반환 타입은 boolean이다.

Queue<Integer> queue = new LinkedList<>();

queue.offer(1);
queue.offer(2);
queue.offer(3);

System.out.println(queue); // [1]

 

peek()

객체 하나를 가져온다. 가져온 객체는 큐에서 제거하지 않는다.

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);

System.out.println(queue.peek()); // 1
System.out.println(queue.isEmpty()); // false

 

poll()

객체 하나를 가져온다. 가져온 객체는 큐에서 제거한다.

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);

System.out.println(queue.peek()); // 1
System.out.println(queue.isEmpty()); // true

 

Queue 인터페이스의 구현체

자바에서 제공하는 큐 인터페이스의 구현체는 연결 리스트 LinkedList<E>, 우선순위 큐 PriorityQueue<E>, 덱, 데크, 디큐 등으로 불리는 ArrayDeque<E>가 대표적이다. 이 외에도 AbstractQueue<E>, ConcurrentLinkedQueue<E> 등 다양한 구현체가 존재한다.

해당 구현 클래스에 대한 정보는 큐 인터페이스 공식 문서에서 확인이 가능하다.

 

 

PriorityQueue (우선순위 큐)

우선순위 큐는 저장한 순서와는 관계 없이 우선순위에 따라 꺼내는 순서가 정해진 큐이다.

각 요소들을 힙(heap) 자료구조에 저장하며, null 값은 저장할 수 없다.

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(2);
pq.offer(1);
pq.offer(3);
pq.offer(4);

while (!pq.isEmpty())
    System.out.println(pq.poll());

// 출력
1
2
3
4
5

5, 2, 1, 3, 4 순으로 큐에 저장하였으나, 이를 하나씩 출력하면 1, 2, 3, 4, 5로 출력된다. 따라서 기본적으로 우선순위의 값이 낮은 것부터 오름차순으로 출력하는 것을 알 수 있다.

 

만약, 우선순위의 값이 높은 것부터 내림차순으로 꺼내고 싶다면 다음과 같이 선언해야 한다.

Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

 

Deque

Deque는 양쪽 끝에 값을 추가 또는 삭제할 수 있는 특별한 자료구조이다.

즉, 스택과 큐를 하나로 합쳐놓은 것과 같은 기능을 한다.

 

Deque는 Queue 인터페이스를 상속받은 인터페이스이다. 따라서 Deque를 구현한 구현 클래스는 ArrayDeque와 LinkedList 등이 있다.

 

Deque 인터페이스의 메서드

Deque 인터페이스의 메서드는 Stack과 Queue에서 제공하는 메서드와 함께 확장된 기능을 제공한다.

 

추가 : offerFirst(), offerLast(), addFirst(), addLast()

 

꺼내기(큐에서 제거됨) : pollFirst(), pollLast()

 

삭제 : removeFirst(), removeLast()

 

가져오기(큐에서 제거되지 않음) : getFirst(), getLast(), peekFirst(), peekLast()

 

Deque 선언

Deque<E> deque1 = new ArrayDeque<E>();
Deque<E> deque2 = new LinkedList<E>();

 

Deque 사용

Deque<Integer> deque = new ArrayDeque<>();

// 값 추가
deque.addFirst(2);
deque.addLast(3);
deque.addFirst(1);

System.out.println(deque);

System.out.println(deque.peekFirst());
System.out.println(deque.peekLast());

System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());