1️⃣ Deque(덱, Double Ended Queue)

Deque(덱, Double Ended Queue)는 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조입니다.

Java에서는 java.util 패키지에서 제공하는 Deque 인터페이스와 이를 구현한 클래스인 ArrayDeque 와 LinkedList 를 통해 사용할 수 있습니다.

Deque 는 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있습니다.

1️⃣ 데크 기본 구조

데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조
일부 기능을 제한하여 용도에 맞게 변형 가능

add나 remove 계열은 예외를 발생시킵니다.
- 때문에 예외 처리가 가능합니다.
offer이나 poll 계열은 null이나 false를 반환합니다.
- 때문에 return값 (반환값)을 받아서 처리할 수 있습니다.

2️⃣ Deque의 주요 메서드.

1️⃣ 삽입 연산.

addFirst(E e) : 지정된 요소를 덱의 앞쪽에 추가합니다.
addLast(E e) : 지정된 요소를 덱의 뒤쪽에 추가합니다.
offerFirst(E e) : 지정된 요소를 덱의 앞쪽에 추가합니다.
offerLast(E e) : 지정된 요소를 덱의 뒤쪽에 추가합니다.

2️⃣ 삭제 연산.

removeFirst() : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
removeLast() : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
pollFirst() : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
pollLast() : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.

3️⃣ 조회 연산.

getFirst() : 덱의 앞쪽에 있는 요소를 반환합니다.
getLast() : 덱의 뒤쪽에 있는 요소를 반환합니다.
peekFirst() : 덱의 앞쪽에 있는 요소를 반환합니다.
peekLast() : 덱의 뒤쪽에 있는 요소를 반환합니다.

4️⃣ 기타 연산.

size() : 덱에 있는 요소의 수를 반환합니다.
isEmpty() : 덱이 비어 있는지 여부를 확인합니다.

3️⃣ 시간 복잡도.

Deque 인터페이스의 시간 복잡도는 이를 구현한 클래스에 따라 달라집니다.

Java에서는 주로 ArrayDeque 와 LinkedList 를 사용하여 Deque 를 구현합니다.

1️⃣ ArrayDeque

삽입과 삭제 연산 (앞과 뒤 모두): 평균적으로 O(1)
조회 연산 (앞과 뒤 모두): O(1)
ArrayDeque 는 배열을 기반으로 구현되기 때문에, 배열이 꽉 차면 자동으로 크기를 늘리지만, 이 과정은 amortized O(1)로 간주됩니다.

2️⃣ LinkedList

삽입과 삭제 연산 (앞과 뒤 모두): O(1)
조회 연산 (앞과 뒤 모두): O(1)
LinkedList 는 이중 연결 리스트로 구현되어 있어 각 노드가 이전과 다음 노드에 대한 참조를 가지고 있습니다.

LinkedList는 각 노드가 이전 노드와 다음 노드의 참조를 가지고 있어 삽입과 삭제가 O(1)의 시간 복잡도를 가집니다.
하지만 탐색에는 O(n)의 시간이 소요됩니다.

ArrayDeque는 배열을 사용하여 내부적으로 구현되기 때문에 삽입과 삭제 시에도 평균적으로 O(1)의 시간 복잡도를 가지며,
특히 큐의 끝에서의 연산이 빠릅니다.

다만, 내부적으로 배열이 가득 차면 크기를 조정해야 하므로 최악의 경우 O(n)의 시간 복잡도가 발생할 수 있습니다.

Deque 는 다양한 상황에서 유연하게 사용될 수 있는 유용한 자료구조입니다.
특히 양쪽 끝에서의 빠른 삽입과 삭제가 필요한 경우 유용합니다.

3️⃣ 직접 Deque 인터페이스 구현.

간단한 배열을 사용하여 Deque 를 구현해보겠습니다.

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SimpleArrayDeque<E> {
  private static final int DEFALT_CAPACITY = 10;
  private E[] elements;
  private int head;
  private int tail;
  private int size;

  public SimpleArrayDeque() {
    elements = (E[]) new Object[DEFALT_CAPACITY];
    head = 0;
    tail = 0;
    size = 0;
  }

  public void addFirst(E e) {
    if (size == elements.length) {
      resize();
    }
    head = (head - 1 + elements.length) % elements.length;
    elements[head] = e;
    size++;
  }

  public void addLast(E e) {
    if (size == elements.length) {
      resize();
    }
    elements[tail] = e;
    tail = (tail + 1) % elements.length;
    size++;
  }

  public E removeFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    E element = elements[head];
    elements[head] = null; // for garbege collection
    head = (head + 1);
    size--;
    return element;
  }

  public E removeLast() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    tail = (tail - 1 + elements.length) % elements.length;
    E element = elements[tail];
    elements[tail] = null; // for garbage collection
    size--;
    return element;
  }

  public E getFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    return elements[head];
  }

  public E getLast() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    return elements[(tail - 1 + elements.length) % elements.length];
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  private void resize() {
    int newCapacity = elements.length * 2;
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
      newElements[i] = elements[(head + i) % elements.length];
    }
    elements = newElements;
    head = 0;
    tail = size;
  }

  public ArrayList<E> toArrayList() {
    return IntStream.range(0, size)
                    .mapToObj(i -> elements[(head + i) % elements.length])
                    .collect(Collectors.toCollection(ArrayList::new));
  }
}

// Main
import java.util.ArrayList;

public class Main {

  public static void main(String[] args) {
    SimpleArrayDeque<Integer> deque = new SimpleArrayDeque<>();
    deque.addFirst(1);
    deque.addLast(2);
    deque.addFirst(0);
    deque.addLast(3);

    ArrayList<Integer> dequeList = deque.toArrayList();
    System.out.println("=== dequeList === ");
    System.out.println(dequeList);


    System.out.println("First element: " + deque.getFirst());
    System.out.println("Last element: " + deque.getLast());
    System.out.println("=== dequeList === ");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);

    System.out.println("Removed first element: " + deque.removeFirst());
    System.out.println("Remove last element: " + deque.removeLast());
    System.out.println("=== dequeList === ");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);

    System.out.println("Deque size: " + deque.size());
    System.out.println("Is deque empty? " + deque.isEmpty());
    System.out.println("=== dequeList === ");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);
  }
}

/*
=== 출력 ===
=== dequeList === 
[0, 1, 2, 3]
First element: 0
Last element: 3
=== dequeList === 
[0, 1, 2, 3]
Removed first element: 0
Remove last element: 3
=== dequeList === 
[1, 2]
Deque size: 2
Is deque empty? false
=== dequeList === 
[1, 2]
*/

4️⃣ 입력 제한 Deque(Input-Restricted Deque).

입력 제한 Deque(Input-Restricted Deque)은 덱의 한쪽 끝에서만 삽입이 가능하고, 양쪽 끝에서 삭제가 가능한 자료구조입니다.

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class InputRestrictedDeque<E> {
  private static final int DEFAULT_CAPACITY = 10;
  private E[] elements;
  private int head;
  private int tail;
  private int size;

  @SuppressWarnings("unchecked")
  public InputRestrictedDeque() {
    elements = (E[]) new Object[DEFAULT_CAPACITY];
    head = 0;
    tail = 0;
    size = 0;
  }

  public void addLast(E e) {
    if (size == elements.length) {
      resize();
    }
    elements[tail] = e;
    tail = (tail + 1) % elements.length;
    size++;
  }

  public E removeFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    E element = elements[head];
    elements[head] = null; // for garbage collection
    head = (head + 1) % elements.length;
    size--;
    return element;
  }

  public E removeLast() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    tail = (tail - 1 + elements.length) % elements.length;
    E element = elements[tail];
    elements[tail] = null; // for gatbage collection
    size--;
    return element;
  }

  public E getFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    return elements[head];
  }

  public E getLast() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    return elements[(tail - 1 + elements.length) % elements.length];
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  private void resize() {
    int newCapacity = elements.length * 2;
    @SuppressWarnings("unchecked")
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
      newElements[i] = elements[(head + i) % elements.length];
    }
    elements = newElements;
    head = 0;
    tail = size;
  }

  public ArrayList<E> toArrayList() {
    return IntStream.range(0, size)
                    .mapToObj(i -> elements[(head + i) % elements.length])
                    .collect(Collectors.toCollection(ArrayList::new));
  }
}

// Main
import java.util.ArrayList;

public class Main {

  public static void main(String[] args) {
    InputRestrictedDeque<Integer> deque = new InputRestrictedDeque<>();
    deque.addLast(1);
    deque.addLast(2);
    deque.addLast(3);

    ArrayList<Integer> dequeList = deque.toArrayList();
    System.out.println("=== dequeList ===");
    System.out.println(dequeList);

    System.out.println("First element: " + deque.getFirst());
    System.out.println("Last element: " + deque.getLast());
    System.out.println("=== dequeList ===");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);

    System.out.println("Remove first element: " + deque.removeFirst());
    System.out.println("Remove last elment: " + deque.removeLast());
    System.out.println("=== dequeList ===");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);

    System.out.println("Deque size: " + deque.size());
    System.out.println("Is deque empty? " + deque.isEmpty());
  }
}
/*
=== 출력 ===
=== dequeList ===
[1, 2, 3]
First element: 1
Last element: 3
=== dequeList ===
[1, 2, 3]
Remove first element: 1
Remove last elment: 3
=== dequeList ===
[2]
Deque size: 1
Is deque empty? false
*/

1️⃣ 코드 설명.

배열 초기화 : DEFAULT_CAPACITY 크기의 배열을 초기화하고, head, tail, size 변수를 초기화합니다.
삽입 연산(addLast) : 요소를 덱의 마지막 에 추가합니다. 배열이 가득 차면 크기를 두 배로 늘립니다.
삭제 연산(removeFirst, removeLaste) : 첫 번째 요소와 마지막 요소를 각각 제거합니다.
조회 연산(getFirst, getLast) : 첫 번째 요소와 마지막 요소를 반환합니다.
기타 메서드 : size 와 isEmpty 메서드는 덱의 크기와 덱이 비어 있는지 여부를 반환합니다.
배열 크기 조정 (resize) : 배열이 가득 찰 때 호출되며, 배열의 크기를 두 배로 늘리고 요소를 새 배열로 복사합니다.

이 예제에서는 요소를 덱의 끝에만 삽입할 수 있는 입력 제한 덱을 구현했습니다.
필요에 따라 이 구현을 확장하거나 수정하여 요구사항에 맞게 사용할 수 있습니다.

5️⃣ 출력 제한 Deque(Output-Restricted Deque).

출력 제한 Deque(Output-Restricted Deque)은 양쪽 끝에서 삽입이 가능하지만, 한쪽 끝에서만 삭제가 가능한 자료 구조입니다.

이 구조는 양쪽 끝에서 요소를 추가할 수 있지만, 삭제는 한쪽 끝에서만 할 수 있습니다.

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class OutputRestrictedDeque<E> {
  private static final int DEFAULT_CAPACITY = 10;
  private E[] elements;
  private int head;
  private int tail;
  private int size;

  @SuppressWarnings("unchecked")
  public OutputRestrictedDeque() {
    elements = (E[]) new Object[DEFAULT_CAPACITY];
    head = 0;
    tail = 0;
    size = 0;
  }

  public void addFirst(E e) {
    if (size == elements.length) {
      resize();
    }
    head = (head - 1 + elements.length) % elements.length;
    elements[head] = e;
    size++;
  }

  public void addLast(E e) {
    if (size == elements.length) {
      resize();
    }
    elements[tail] = e;
    tail = (tail + 1) % elements.length;
    size++;
  }

  public E removeFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    E element = elements[head];;
    elements[head] = null; // for garbage collection
    head = (head + 1) % elements.length;
    size--;
    return element;
  }

  public E getFirst() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    return elements[head];
  }

  public E getLast() {
    if (size == 0) {
      throw new NoSuchElementException();
    }
    return elements[(tail - 1 + elements.length) % elements.length];
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  private void resize() {
    int newCapacity = elements.length * 2;
    @SuppressWarnings("unchecked")
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
      newElements[i] = elements[(head + 1) % elements.length];
    }
    elements = newElements;
    head = 0;
    tail = size;
  }

  public ArrayList<E> toArrayList() {
    return IntStream.range(0, size)
                    .mapToObj(i -> elements[(head + i) % elements.length])
                    .collect(Collectors.toCollection(ArrayList::new));
  }
}

// Main
import java.util.ArrayList;

public class Main {

  public static void main(String[] args) {
    OutputRestrictedDeque<Integer> deque = new OutputRestrictedDeque<>();
    deque.addFirst(1);
    deque.addLast(2);
    deque.addFirst(0);
    deque.addLast(3);

    ArrayList<Integer> dequeList = deque.toArrayList();
    System.out.println("=== dequeList === ");
    System.out.println(dequeList);

    System.out.println("First element: " + deque.getFirst());
    System.out.println("Last element: " + deque.getLast());
    System.out.println("=== dequeList === ");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);

    System.out.println("Remove first element: " + deque.removeFirst());
    System.out.println("=== dequeList === ");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);

    System.out.println("Deque size: " + deque.size());
    System.out.println("Is deque empty? " + deque.isEmpty());
    System.out.println("=== dequeList === ");
    dequeList = deque.toArrayList();
    System.out.println(dequeList);
  }
}

/*
=== 출력 ===
=== dequeList ===
[0, 1, 2, 3]
First element: 0
Last element: 3
=== dequeList ===
[0, 1, 2, 3]
Remove first element: 0
=== dequeList ===
[1, 2, 3]
Deque size: 3
Is deque empty? false
=== dequeList ===
[1, 2, 3]
*/

1️⃣ 코드 설명.

배열 초기화 : DEFAULT_CAPACITY 크기의 배열을 초기화하고, head, tail, size 변수를 초기화 합니다.
삽입 연산(addFirst, addLast) : 요소를 덱의 첫 번째 또는 마지막에 추가합니다. 배열이 가득 차면 크기를 두 배로 늘립니다.
삭제 연산(removeFirst) : 첫 번째 요소를 제거합니다. 출력 제한 덱에서는 첫 번째 요소만 제거할 수 있습니다.
조회 연산(getFirst, getLast) : 첫 번째 요소와 마지막 요소를 반환합니다.
기타 메서드 : size 와 isEmpty 메서드는 덱의 크기와 덱이 비어 있는지 여부를 반환합니다.
배열 크기 조정(resize) : 배열이 가득 찰 때 호출되며, 배열의 크기를 두 배로 늘리고 요소를 새 배열로 복사합니다.

이 예제에서는 요소를 덱의 양쪽 끝에서 삽입할 수 있고, 첫 번째 요소만 제거할 수 있는 출력 제한 덱을 구현했습니다.
필요에 따라 이 구현을 확장하거나 수정하여 요구사항에 맞게 사용할 수 있습니다.

devkobe24.com

Contact

1️⃣ Deque(덱, Double Ended Queue)

1️⃣ 데크 기본 구조

2️⃣ Deque의 주요 메서드.

1️⃣ 삽입 연산.

2️⃣ 삭제 연산.

3️⃣ 조회 연산.

4️⃣ 기타 연산.

3️⃣ 시간 복잡도.

1️⃣ ArrayDeque

2️⃣ LinkedList

3️⃣ 직접 Deque 인터페이스 구현.

4️⃣ 입력 제한 Deque(Input-Restricted Deque).

1️⃣ 코드 설명.

5️⃣ 출력 제한 Deque(Output-Restricted Deque).

1️⃣ 코드 설명.