[알고리즘 개념] Deque

Deque란?

deque는 덱이라고 불리고, 스택과 큐를 합쳐놓은 자료구조이다.

스택, 큐와 달리 양 끝에서 삽입과 삭제가 모두 가능하다. 시간복잡도는 모두 O(1)이다!

위와 같이 양쪽에서 push와 pop이 가능하니, 각 명령어 앞에 앞에서 빼는지, 뒤에서 빼는지를 적어두어야한다.

 

Deque 사용법

변수선언

import java.util.Deque;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<>();
    }
}

선언은 이런식으로 Deque<타입>으로 하면 된다.

 

값 넣고 빼기

addFirst(E)

맨 앞에 데이터 E를 추가합니다.

 

addLast(E)

맨 뒤에 데이터 E를 추가합니다.

 

pollFirst()

맨 앞에 있는 데이터를 반환합니다. 동시에 그 데이터를 deque에서 뺍니다.

 

pollLast()

맨 뒤에 있는 데이터를 반환합니다. 동시에 그 데이터를 deque에서 뺍니다.

 

size()

현재 deque에 들어있는 데이터의 수를 반환합니다.

 

isEmpty()

현재 deque가 비어있다면 true, 아니라면 false를 반환합니다.

 

peekFirst()

deque의 맨 앞에 있는 데이터를 반환합니다.

 

peekLast()

deque의 맨 뒤에 있는 데이터를 반환합니다.

 

출처 : 코드트리

https://www.codetree.ai/trails/complete/curated-cards/challenge-sequence-manipulation/description

Code Tree | Learning to Code with Confidence