[Java] Deque 알아보기

Deque 이란?

Deque 는 Double Ended Queue 의 약자로, 기존의 Queue나 Stack과는 다르게 양 방향에서 접근할 수 있는 자료구조이다. Deque의 구현체는 대부분 용량에 제한이 없지만, 용량 제한이 있는 구현체 또한 존재한다. 삽입, 제거, 조사 기능을 하는 메소드들을 제공하고, 각 메소드들은 실패 시 예외처리를 하는 형태와 null 이나 false를 리턴하는 형태가 존재한다.

구현 클래스

ArrayDeque

• Deque 인터페이스를 동적배열로 구현한 것으로, 용량 제한이 없고 필요에 따라 용량이 늘어난다.
• 스레드로부터 안전하지 않다.
• 대부분의 연산은 상수 시간 내에 가능하다. (remove, contains 등 제외)
• Stack이나 Queue를 구현할 시, Stack 과 LinkedList로 구현된 메소드를 사용하는 것 보다 빠르다.
• null을 받을 수 없다.

LinkedList

• Queue와 마찬가지로, Deque 구현도 가능하다.
• null을 받을 수 있다.

주요 메소드

Deque 메소드 요약
	First Element (Head)		Last Element (Tail)
	Thorws Exception	Special Value	Thorws Exception	Special Value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

Queue 메소드와 비교
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

Stack 메소드와 비교
push(e)	addFirst()
pop()	removeFirst()
peek()	peekFirst()

그 외 메소드들은 여기 참고

예시

Deque<Integer> dq = new LinkedList<>();

dq.add(1);
dq.add(2);
dq.add(3);
System.out.println("dq = " + dq); // dq = [1, 2, 3]

// add
dq.addFirst(4);
System.out.println("dq = " + dq); // dq = [4, 1, 2, 3]

dq.addLast(5);
System.out.println("dq = " + dq); // dq = [4, 1, 2, 3, 5]

dq.push(6);
System.out.println("dq = " + dq); // dq = [6, 4, 1, 2, 3, 5]

dq.offer(7);
System.out.println("dq = " + dq); // dq = [6, 4, 1, 2, 3, 5, 7]

// peek == element() == getFirst()
System.out.println("dq.element() = " + dq.element()); // dq.element() = 6
System.out.println("dq.peek() = " + dq.peek()); // dq.peek() = 6
System.out.println("dq.peekFirst() = " + dq.peekFirst()); // dq.peekFirst() = 6
System.out.println("dq.peekLast() = " + dq.peekLast()); // dq.peekLast() = 7


System.out.println("dq.poll() = " + dq.poll()); // dq.poll() = 6
System.out.println("dq = " + dq);   // dq = [4, 1, 2, 3, 5, 7]
System.out.println("dq.pollFirst() = " + dq.pollFirst());   // dq.pollFirst() = 4
System.out.println("dq = " + dq);   // dq = [1, 2, 3, 5, 7]
System.out.println("dq.pollLast() = " + dq.pollLast()); // dq.poll() = 7
System.out.println("dq = " + dq);   // dq = [1, 2, 3, 5]

System.out.println("dq.pop() = " + dq.pop());   // dq.pop() = 1
System.out.println("dq = " + dq);   // dq = [2, 3, 5]

 

참고: 자바 공식문서