데크 (Deque)

데크란?

양쪽에서 삽입과 삭제가 모두 가능한 자료구조를 뜻한다.

 

- Deque  : Doubly-ended Queue

- Stack + Queue 의 형태

 

 

기본 구조

출처 : 제로베이스

- addFirst(), removeLast() 등 first,last로 메소드가 구분되어 진다.

 

 

Deque 종류 

기본적으로 양쪽 입출력 가능한 Deque에서 부분적으로 제한해 가면서 쓸 수 있다.

입력 제한 데크 ( Scroll )

한 쪽의 입력을 제한한 데크, 출력은 양쪽으로 가능하다.

 

출력 제한 데크 ( Shelf )

한 쪽의 출력을 제한한 데크, 입력은 양쪽으로 가능하다.

 

예시

import java.util.*;

class Main {
    public static void main(String[] args) {

        Deque deque = new ArrayDeque();

        // Front 쪽으로 입력
        deque.addFirst(1);
        deque.addFirst(2);
        System.out.println(deque); // 2 1

        // Rear 쪽으로 입력
        deque.addLast(3);
        deque.addLast(4);
        System.out.println(deque);  // 2 1 3 4

        // Front 출력
        deque.removeFirst();
        System.out.println(deque);  // 1 3 4

        // Rear 출력
        deque.removeLast();
        System.out.println(deque); // 1 3
    }
}

 

메소드 종류

- 입력

addFirst()

덱의 앞쪽(Front)에 삽입한다. 크기가 제한된 덱의 경우, 크기를 초과하면 예외가 발생한다

offerFirst()

덱의 앞쪽에 삽입한다. 정상적으로 삽입된 경우 true가 리턴되며, 크기 제한에 걸리는 경우 false를 리턴한다. 

addLast() , add()

덱의 마지막 쪽(Rear)에 삽입한다. 크기가 제한된 덱의 경우, 크기를 초과하면 예외가 발생한다

offerLast() , offer()

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

 

- 출력

removeFirst() , remove() , element()

덱의 앞쪽에서 하나를 꺼낸다(= 맨 앞의 요소를 리턴 후 삭제). 덱이 비어있으면 예외가 발생한다. 

pollFirst() , poll()

덱의 앞쪽에서 하나를 꺼낸다. 덱이 비어있으면 null 이 리턴된다. 

removeLast()

덱의 마지막 쪽에서 하나를 꺼낸다. 덱이 비어있으면 예외가 발생한다. 

pollLast() 

덱의 마지막 쪽에서 하나를 꺼낸다.. 덱이 비어있으면 null 이 리턴된다. 

getFirst()

덱의 앞쪽 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다

peekFirst() , peek()

덱의 앞쪽 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 null이 리턴된다. 

getLast()

덱의 마지막쪽 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다. 

peekLast()

덱의 마지막 하나를 제거하지 않은 채 리턴한다. 덱이 비어있으면 null이 리턴된다. 

removeFirstOccurrence(Object o)

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

removeLastOccurrence(Object o)

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

addAll(Collection <? extends E c)

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

push()

addFirst()와 동일. 덱을 스택으로 사용할 때 쓰임

pop()

removeFirst()와 동일. 덱을 스택으로 사용할 때 쓰임

remove(Object o)

removeFirstOccurrence(Object o)와 동일

contain(Object o)

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

size()

덱의 크기 

iterator()

덱의 앞쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴

descendingIterator()

덱의 뒤쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴