[JAVA] 큐(Queue), 덱(Deque) 구현체, 메서드 정리

큐(Queue)

• 대기 줄처럼 삽입하는 곳과 제거하는 곳이 각각 하나씩인 자료 구조
• 먼저 들어온 순서대로 나간다(= FIFO) cf. 스택은 LIFO

https://www.geeksforgeeks.org/difference-between-queue-and-deque-queue-vs-deque/

 

자바에서는 Queue 인터페이스를 제공하고 있고, 그에 따른 구현체는 다양하다. 대표적으로 LinkedList<>()를 사용한다.

(PriorityQueue - 정렬 가능, ArrayBlockingQueue, ConcurrentLinkedQueue ...) https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html

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

 

삽입 메서드

- 요소를 삽입할 때 사용한다. 

• add(): 삽입 성공 시 true를 반환하고, 큐에 자리가 없다면 IllegalStateException 예외를 터뜨린다.
• offer(): 가능하다면 요소를 삽입하고, 큐에 자리가 없다면 false를 반환한다, fixed-capacity(bounded) queue에서 주로 사용

제거 메서드 

- 두 메서드 모두, 큐의 맨 앞 값을 제거하고 반환한다. 두 메서드의 차이점은 큐가 비어있을 때 반응으로 구별된다.

• remove(): 예외(exception)를 터뜨린다.
• poll(): null을 반환한다.

조회 메서드

• peek(): 값을 조회할 때 사용하여 제거하지 않고 큐의 맨 앞 값을 반환한다, 큐가 비어있을 때는 null을 반환한다.
• element(): peek()와 동일

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.htm

https://cocoon1787.tistory.com/774

[JAVA] Queue(큐) 사용법 (add vs offer / remove vs poll / element vs peek)

큐에서는 넣고 빼는 방향이 정해져 있기 때문에 offer(), poll().. 이 복잡하게 느껴지진 않았는데 덱이 좀 힘들었다...

 

덱(Deque) 

• Deque = Double ended Queue
• 이름에서 나타나듯이, 선형 자료구조에서 삽입과 제거가 양쪽에서 가능한 자료 구조
• 큐와 마찬가지로 인터페이스로 구현되어 있는데, Queue<E>를 상속하여 만들어짐

https://www.geeksforgeeks.org/difference-between-queue-and-deque-queue-vs-deque/

구현체는 다음과 같다.

Deque<E> deque1 = new ArrayDeque<>();
Deque<E> deque2 = new ConcurrentLinkedDeque<>();
Deque<E> deque3 = new LinkedBlockingDeque<>();
Deque<E> deque4 = new LinkedList<>();

 

큐와 메서드 이름에서 크게 다를 건 없다. 하지만 앞뒤에서 모두 삽입, 삭제가 가능하기 때문에 가짓수가 확 늘었다...

마찬가지로 삽입, 삭제, 조회 메서드가 있는데 각각에 대해서, operation이 실패할 시 예외를 터뜨릴 것이냐, 특별 반환값을 갖느냐(null, false)로 나눠볼 수 있다. 아래를 보면 알겠지만, add()는 뒤에서, remove()는 앞에서.. poll()은 앞에서... 이렇게 되어 있긴 하지만 외울 건 아닌 것 같다.(to me) 헷갈린다 싶으면 확실하게 first, last 키워드를 잘 쓰는 게 머리를 잘 쓰는 법이라고 생각한다. 그리고 공식문서에 이거에 대한 언급이 있었는데, deque가 queue 인터페이스를 상속한 것이다보니 앞서  방향이 큐와 동일했던 것이다! 근데 나는 그냥 키워드를 쓸 것이야.. https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html

앞에서 넣고 빼는 push(), pop()은 LIFO 성질인 스택 메서드인데 마찬가지로 deque이 스택으로도 사용할 수 있기 때문에 사용 가능하다. 

 

삽입 메서드

- 요소를 삽입할 때 사용한다. 

• 앞 - addFirst() == push(): 자리가 없다면 IllegalStateException 예외를 터뜨린다.
• 앞 - offerFirst(): 성공하면 true, 자리가 없다면 false
• 뒤 - addLast() == add(): 자리가 없다면 IllegalStateException 예외를 터뜨린다.
• 뒤 - offerLast() == offer(): 성공하면 true, 자리가 없다면 false

제거 메서드 

- 요소를 삭제할 때 사용한다. 

• 앞 - removeFirst() == remove() == pop(): 덱이 비었다면 Exception 반환
• 앞 - pollFirst() == poll(): 덱이 비었다면 null 반환
• 뒤 - removeLast(): 덱이 비었다면 Exception 반환
• 뒤 - pollLast(): 덱이 비었다면 null 반환

조회 메서드

- 요소를  조회할 때 사용한다. 

• 앞 - getFirst() == element() == peek(): 덱이 비었다면 Exception 반환
• 앞 - peekFirst() == peek(): 덱이 비었다면 null 반환
• 뒤 - getLast(): 덱이 비었다면 Exception 반환
• 뒤 - peekLast(): 덱이 비었다면 null 반환

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html

https://hbase.tistory.com/128

[Java] Deque (덱/데크) 사용법 및 예제

 

https://www.acmicpc.net/problem/11003

이 문제는 덱의 특징과 메서드를 잘 알고 있으면 풀 수 있는 문제다.