Deque (덱/데크)

백준 5430 AC 문제를 풀며 Deque를 사용해서 정리를 해보았다 ! 😁

 

🔹 Deque

• Double-Ended Queue의 줄임말
• 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다.

 

• 덱은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다.
• 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라 하며,
• 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다.

 

🔹 자바에서의 Deque

• 자바에서의 덱은 인터페이스로 구현되어 있다.
• 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고,
  • 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.

 

🔹 Deque 인터페이스의 메서드

◽ addFirst()

• 덱의 앞쪽에 엘리먼트를 삽입한다.
• 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다.

◽ offerFirst()

• 덱의 앞쪽에 엘리먼트를 삽입한다.
• 정상적으로 엘리먼트가 삽입된 경우 true가 반환되며, 용량 제한에 걸리는 경우 false를 반환한다.

◽ addLast()

• 덱의 마지막 쪽에 엘리먼트를 삽입한다.
• 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다.

◽ add()

• addLast()와 동일한다.

◽ offerLast()

• 덱의 마지막 쪽에 엘리먼트를 삽입한다.
• 정상적으로 엘리먼트가 삽입된 경우 true가 반환되며, 용량 제한에 걸리는 경우 false를 반환한다.

 

 

 

◽ removeFirst()

• 덱의 앞쪽에서 엘리먼트를 하나 뽑아 제거한 다음 해당 엘리먼트를 반환한다.
• 덱이 비어있으면 예외(Exception)가 발생한다.

◽ pollFirst()

• 덱의 앞쪽에서 엘리먼트를 하나 뽑아 제거한 다음 해당 엘리먼트를 반환한다.
• 덱이 비어있으면 null을 반환한다.

◽ removeLast()

• 덱의 마지막 쪽에서 엘리먼트를 하나 뽑아 제거한 다음 해당 엘리먼트를 반환한다.
• 덱이 비어있으면 예외(Exception)가 발생한다.

◽ pollLast()

• 덱의 마지막 쪽에서 엘리먼트를 하나 뽑아 제거한 다음 해당 엘리먼트를 반환한다.
• 덱이 비어있으면 null을 반환한다.

◽ remove()

• removeFirst()와 동일한다.

◽ poll()

• pollFirst()와 동일하다.

 

 

 

◽ getFirst()

• 덱의 앞쪽에서 엘리먼트 하나를 제거하지 않은 채 반환한다.
• 덱이 비어있으면 예외(Exception)가 발생한다.

◽ peekFirst()

• 덱의 앞쪽에서 엘리먼트 하나를 제거하지 않은 채 반환한다.
• 덱이 비어있으면 null을 반환한다.

◽ getLast()

• 덱의 마지막 쪽에서 엘리먼트 하나를 제거하지 않은 채 반환한다.
• 덱이 비어있으면 예외(Exception)가 발생한다.

◽ peekLast()

• 덱의 마지막 쪽에서 엘리먼트 하나를 제거하지 않은 채 반환한다.
• 덱이 비어있으면 null을 반환한다.

◽ peek()

• peekFirst()와 동일하다.

 

🔹 그 외

◽ removeFirstOccurrence(Object o)

• 덱의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다.
• Object o와 같은 엘리먼트가 없다면 덱에 변경이 발생하지 않는다.

◽ removeLastOccurrence(Object o)

• 덱의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다.
• Object o와 같은 엘리먼트가 없다면 덱에 변경이 발생하지 않는다.

◽ element()

• removeFirst()와 동일하다.

◽ addAll(Collection<? extends Integer> c)

• 입력받은 Collection의 모든 데이터를 덱의 뒤쪽에 삽입한다.

◽ push()

• addFirst()와 동일하다.
• 덱을 스택으로 사용할 때 쓰인다.

◽ pop()

• removeFirst()와 동일하다.
• 덱을 스택으로 사용할 때 쓰인다.

◽ remove(Object o)

• removeFirstOccurrence(Object o)와 동일하다.

◽ contain(Object o)

• 덱에 Object o와 동일한 엘리먼트가 포함되어 있는지 확인한다.

◽ size()

• 덱의 크기를 확인한다.

◽ iterator()

• 덱의 앞쪽부터 순차적으로 실행되는 iterator를 얻어온다.

◽ descendingIterator()

• 덱의 뒤쪽부터 순차적으로 실행되는 iterator를 얻어온다.

 

🔹 자바에서 Deque 사용법

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class Main {
    public static void main(String[] args) throws IOException {
        // Deque 생성
        Deque<String> deque1 = new ArrayDeque<>();
        Deque<String> deque2 = new LinkedList<>();
        Deque<String> deque3 = new LinkedBlockingDeque<>();
        Deque<String> deque4 = new ConcurrentLinkedDeque<>();
        
        // Deque 순회
        for (String element : deque1) {
            System.out.println(element);
        }

        // Iterator 순회
        Iterator<String> iterator = deque1.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
        }
        
        // Iterator 역순 순회
        Iterator<String> reverseIterator = deque1.descendingIterator();
        while (reverseIterator.hasNext()) {
            String element = reverseIterator.next();
            System.out.println(element);
        }
    }
}

 

 

 

📍 함께 풀어보면 좋은 백준 문제

• 1464 뒤집기 3