[자료구조] Deque란? from Java

Deque란?

---

- Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 넣고 뺄 수 있는 형태의 자료구조를 의미한다

- 다시 말해 기존의 Queue는 한쪽에서 데이터를 넣고 다른 한쪽에서 데이터를 빼는 형태인데 Deque는 둘다 데이터를 넣고 뺄 수 있다는 것이다

- Queue와 Stack 을 합쳐 놓은 자료구조라고 생각 하면 된다

 

Deque 모양

 

- Deque를 이해하려면 일단 Queue를 알아야 한다 

- 아래는 Queue를 정리한 포스팅이다 

 

https://hyeonni.tistory.com/24

Queue란? from java

 

사용법

 

Deque 생성

---

Deque 인터페이스

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class test {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        Deque<Integer> deque1 = new LinkedList<>();
        Deque<Integer> deque2 = new ConcurrentLinkedDeque<>();
        Deque<Integer> deque3 = new LinkedBlockingDeque<>();
    }
}

 

- Deque는 Queue에 extends 하고 있는 형태이다

- java.util.Deque 클래스로 부터 제공하고 있다

- Deque는 인터페이스로 이를 구현한 구현체로는 ArrayDeque, LinkedList, ConcurrentLinkedDeque, LinkedBlockingDeque가 있다

 

 

Deque 값 추가

---

- 일단 Queue를 알면 add(), offer()는 알거라고 생각하고 이야기 해보겠다

- add(), addLast(), offer(), offerLast()는 데이터를 뒤에서 넣는다

- addFirst(), offerFirst()는 메서드 명 그대로 데이터를 앞에서 넣는다

deque 값 추가 메서드 java docs

 

- add(), addFirst(), addLast()는 데이터를 추가 할때 용량 초과시 IllegalstateException를 던진다

- offer(), offerFirst(), offerLast() 는 데이터를 추가 할때 용량 초과시 false를 반환한다

 

deque를 스택으로 사용할때 값 추가 메서드 java docs

 

- 위에 메서드는 Deque를 스택으로 쓰일때 값을 추가할때 쓰이는 메서드 이다 

- push()는 addFirst()와 동일하게 값을 넣고 만약 용량이 초과시 IllegalStateException을 던진다

 

 

 

Deque 값 제거

---

 

 

- remove(), removeFirst(), poll(), pollFirst()는 데이터를 앞에서 뺀다

- removeLast(), pollLast()는 메서드 명 그대로 데이터를 뒤에서 뺀다

 

deque 값 제거 메서드 java docs

 

- remove(), removeFirst(), removeLast() 는 데이터 삭제할때 deque가 비어 있으면 NoSuchElementException을 던진다

- poll(), pollFirst(), pollLast() 는 데이터 삭제할때 deque가 비어 있으면 null를 반환한다

 

deque를 스택으로 사용할때 값 삭제 메서드 java docs

 

- 위에 메서드는 Deque를 스택으로 쓰일때 값을 삭제할때 쓰이는 메서드 이다

- pop()은 removeFirst()와 동일하게 값을 삭제하고 만약 비어있으면 NoSuchElementException을 던진다

 

 

 

Deque값 확인

---

 

- getFirst(), peek(), peekFirst() 앞에 있는 데이터를 확인한다

- getLast(), peekLast()는 메서드 명 그대로 뒤에 있는 데이터를 확인한다

deque 값 확인 메서드 java docs

 

- element(), getFirst(), getLast() 는 데이터를 확인 할때 deque가 비어 있으면 NoSuchElementException을 던진다

- peek(), peekFirst(), peekLast() 는 데이터를 확인 할때 deque가 비어 있으면 null를 반환한다

 

이외의 확인 메서드 java docs

 

- 이외에도 위 그림과 같이 Object 인자와 동일한 엘리먼트가 포함되어 있는지 확인하는 contains()가 있다 

이 메서드는 Object의 타입과 이 큐의 타입이 동일하지 않을때 ClassCastException을 던지고

지정된 요소가 null이고 deque가 null 요소를 허용하지 않을때 NullPointerException을 던진다

 

- 큐의 사이즈를 확인하는 size() 메서드가 있다

 

 

Deque 순회

 

---

- for문과 iterator를 이용해서 Deque에 저장되어 있는 값들을 순회할 수 있다

	// for 문을 이용한 순회
        for (int element : deque) {
            System.out.println(element);
        }

        //Iterator를 이용한 순회
        Iterator<Integer> integerIterator = deque.iterator();
        while (integerIterator.hasNext()) {
            System.out.println(integerIterator.next());
        }

 

- 위 사진처럼 Deque 클래스에 iterator() 메서드가 있다

- iterator() 메서드는 Iterator로 만들수 있고 descendingIterator()는 역순으로 순회하기 위한 Iterator를 만들수 있는 메서드이다

 

 

 

정리를 하자면..

 

- 데큐(Deque)는 스택과 큐의 기능을 합쳐놓았다

-Deque를 이용해서 스택기능과 큐 기능을 동시에 사용할 수 있다