[JAVA] 덱(Deque) 정리

덱(Deque)

Deque : Double-Ended Queue
이름 그대로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조

[ FRONT ] <--> <--> <--> <--> [ REAR ]
  ↑              ↑
넣을 수 있음         넣을 수 있음
뺄 수도 있음         뺄 수도 있음

✔ 특징

• 양쪽에서 삽입/삭제 가능
• 스택처럼 사용 가능
• 큐처럼 사용 가능
• 빠르고 유연함

메소드

front에 넣기

addFirst(E e) offerFirst(E e)

Type	Method	설명
void	addFirst(E e)	덱 앞에 요소를 삽입
boolean	offerFirst(E e)	덱 앞에 요소를 삽입, 성공시 true 반환, 용량 제한이 걸리는 경우 false 반환

rear에 넣기

addLast(E e) offerLast(E e)

Type	Method	설명
void	addLast(E e)	덱 끝에 요소를 삽입
boolean	offerLast(E e)	덱 끝에 요소를 삽입, 성공시 true 반환, 용량 제한이 걸리는 경우 false 반환

front부터 삭제

removeFirst() pollFirst()

Type	Method	설명
E	removeFirst()	덱의 첫 번째 요소를 삭제한 후 해당 값을 반환
E	pollFirst()	덱의 첫 번째 요소를 삭제한 후 해당 값을 반환, 덱이 비어있다면 null을 반환

rear부터 삭제

removeLast() pollLast()

Type	Method	설명
E	removeLast()	덱의 마지막 요소를 삭제한 후 해당 값을 반환
E	pollLast()	덱의 마지막 요소를 삭제한 후 해당 값을 반환, 덱이 비어있다면 null을 반환

front부터 조회

getFirst() peekFirst()

Type	Method	설명
E	getFirst()	덱의 front를 검색한 후 반환하지만, 삭제는 하지 않음
E	peekFirst()	덱의 front를 검색한 후 반환하지만, 삭제는 하지 않음. 덱이 비어있다면 null 반환

rear부터 조회

getLast() peekLast()

Type	Method	설명
E	getLast()	덱의 rear를 검색한 후 반환하지만, 삭제는 하지 않음
E	peekLast()	덱의 rear를 검색한 후 반환하지만, 삭제는 하지 않음. 덱이 비어있다면 null을 반환

Deque<Integer> queue = new ArrayDeque<>();

// 뒤에 넣기
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);

System.out.println(queue.removeFirst());  // 1
System.out.println(queue.peekFirst());   // 2

그 외

int size() : 덱의 요소 수를 반환
boolean contains(Object o) : 덱에 해당 요소가 포함되어 있으면 true, 아니면 false
Boolean isEmpty() : 덱이 비었으면 true, 아니면 false

스택과 같은 메소드, 그러나 다른 작동방식

push(E e) (= addFirst)
pop() (= removeFirst)

💡Deque와 Stack의 동작 방식 차이

Stack.push()는 스택에서 LIFO(Last In First Out) 방식으로 가장 상단에 데이터를 넣고, 맨 위에서부터 꺼내는 방식

Deque.push()는 큐(Queue)의 앞에 요소를 추가하는 방식. 즉, Deque의 addFirst()와 같은 역할이므로 맨 앞에 데이터를 넣는 것.

Deque<Integer> deque = new ArrayDeque<>();

deque.push(10); // addFirst(10) → [10]
deque.push(20); // addFirst(20) → [20, 10]
deque.push(30); // addFirst(20) → [30, 20, 10]
System.out.println(deque); // 출력: [30, 20, 10]

int removed = deque.pop(); // removeFirst() → 30
System.out.println("removed: " + removed); // 출력: removed: 30
System.out.println(deque.peek()); // 출력 : 20

System.out.println(deque); // 출력: [20, 10]

----결과-----
[30, 20, 10]
removed: 30
20
[20, 10]