Algorithm

[JAVA] Deque 덱

Yunny52 2023. 4. 6. 14:43

백준 9376번 : 탈옥 문제를 풀다가 처음 접한 Deque 구조!

Stack이나 Queue와는 어떤 점이 다를까?

 

📌 Deque (Double Ended Queue)란?

Deque는 Queue 인터페이스를 상속받은 인터페이스이다.

큐의 양쪽에서 원소의 삽입과 삭제가 가능한 자료구조이기에 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있다.

그 중에서도 한쪽으로만 입력이 가능하도록 설정한 Deque를 스크롤(입력제한덱)이라고 하고, 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(출력제한덱)이라고 한다.

 

 

📌 Deque 선언

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

 

다음과 같이 LinkedList나 ArrayDeque로 구현될 수 있다.

 

 

📌 Deque 메소드

✨ Deque 원소 삽입

deque.addFirst()
deque.offerFirst()

deque.add()
deque.addLast()
deque.offer()
deque.offerLast()

 

  •  addFirst()
    • 맨 앞에 원소 삽입
    • 용량 초과 시 예외 발생
  • offerFirst()
    • 맨 앞에 원소 삽입
    • 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환
  • add()
    • 마지막에 원소 삽입
    • 용량 초과 시 예외 발생
  • addLast()
    • 마지막에 원소 삽입
    • 용량 초과시 예외 발생
  • offer()
    • 마지막에 원소 삽입
    • 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환
  • offerLast()
    • 마지막에 원소 삽입
    • 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

 

 

✨ Deque 원소 삭제

deque.remove()
deque.removeFirst()
deque.poll()
deque.pollFirst()

deque.removeLast()
deque.pollLast()

 

  •  remove()
    • 맨 앞의 원소 제거 후 해당 원소를 리턴
    • 덱이 비어 있는 경우 예외 발생
  • removeFirst()
    • 맨 앞의 원소 제거 후 해당 원소를 리턴
    • 덱이 비어 있는 경우 예외 발생
  • poll()
    • 맨 앞의 원소 제거 후 해당 원소를 리턴
    • 덱이 비어 있는 경우 null 리턴
  • pollFirst()
    • 맨 앞의 원소 제거 후 해당 원소를 리턴
    • 덱이 비어 있는 경우 null 리턴
  • removeLast()
    • 마지막 원소를 제거 후 해당 원소를 리턴
    • 덱이 비어 있는 경우 예외 발생
  • pollLast()
    • 마지막 원소를 제거 후 해당 원소를 리턴
    • 덱이 비어 있는 경우 null 리턴

 

 

✨ Deque 원소 확인

deque.getFirst()
deque.peek()
deque.peekFirst()

deque.getLast()
deque.peekLast()

 

  •  getFirst()
    • 맨 앞의 원소를 리턴
    • 덱이 비어 있는 경우 예외 발생
  • peek()
    • 맨 앞의 원소를 리턴
    • 덱이 비어 있는 경우 null 리턴
  • peekFirst()
    • 맨 앞의 원소를 리턴
    • 덱이 비어 있는 경우 null 리턴
  • getLast()
    • 마지막 원소를 리턴
    • 덱이 비어 있는 경우 예외 발생
  • peekLast()
    • 마지막 원소를 리턴
    • 덱이 비어 있는 경우 null 리턴

 

 

✨ 기타

  • removeFirstOccurrence(x)
    • 덱의 맨 앞부터 탐색하여 x와 동일한 첫 원소를 제거
    • 동일한 원소가 없을 시 덱이 변경되지 않음
  • removeLastOccurence(x)
    • 덱의 마지막부터 탐색하여 x와 동일한 첫 원소를 제거
    • 동일한 원소가 없을 시 덱이 변경되지 않음
  • element() == removeFirst() == pop()
  • addFirst() == push()
  • remove(x) == removeFirstOccurence(x)
  • contains(x)
    • 덱에 x와 동일한 원소가 있는지 true 혹은 false 반환
  • size()
    • 덱의 원소 개수 리턴
  • iterator()
    • 덱의 반복자(iterator) 반환
  • isEmpty()
    • 덱이 비어 있는지 true 혹은 false 반환

 

 

✨ Deque 순회 방법

 

import java.util.*;

public class Main {
	
    public static void main(String[] args) {
    	
        Deque<Integer> deque = new LinkedList<>();
        
        deque.add(3);
        deque.add(5);
        deque.add(7);
        
        for(int de : deque) {
        	System.out.print(de + " ");
        }
        System.out.println();
        
        for(Iterator<Integer> it = deque.iterator(); it.hasNext();) {
        	System.out.print(it.next() + " ");
        }
        System.out.println();
        
        Iterator<Integer> it = deque.iterator();
        while(it.hasNext()) {
        	System.out.print(it.next() + " ");
        }
        
    }
    
}

 

- 실행 결과

3 7 5
3 7 5
3 7 5