[자료구조] 데크(Deque)

  데크(Double-ended Queue; Deque)란 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조입니다. 스택과 큐 자료구조를 혼합한 자료구조라고 할 수 있습니다.

  예를 들어 스크롤, 문서 편집기 등의 undo 연산, 웹 브라우저의 방문 기록 등에 사용됩니다. 웹 브라우저 방문 기록의 경우, 최근 방문한 웹 페이지 주소는 앞에 삽입하고 일정 수의 새 주소들이 앞쪽에서 삽입되면 뒤에서 삭제가 수행됩니다.

  데크를 배열이나 이중 연결 리스트로 구현한 경우, 스택과 큐의 연산 수행 시간과 같습니다. 하지만 양 끝에서 삽입과 삭제를 할 수 있으므로 프로그램이 복잡해집니다. 자바는 java.util 패키지에서 Deque 인터페이스를 제공하며 이는 Queue에서 상속됩니다.

 

  주요 메소드

• 삽입
  • addFirst(): front에 요소를 추가, 용량 초과시 예외 발생
  • offFirst(): front에 요소를 추가, 용량 초과시 false 반환
  • addLast(): rear에 요소를 추가, 용량 초과시 예외 발생
    • add()와 동일
  • offerLast(): rear에 요소를 추가, 용량 초과시 false 반환
    • offer()와 동일

 

front(→)	…	rear(←)
addFirst offFirst		addLast offerLast add

 

• 삭제
  • removeFirst(): front에 있는 요소를 제거하고 반환, 데크가 비어 있을 시 예외 발생 
    • remove()와 동일
  • pollFirst(): front에 있는 요소를 제거하고 반환, 데크가 비어 있을 시 null 반환
    • poll()과 동일
  • removeLast(): rear에 있는 요소를 제거하고 반환, 데크가 비어 있을 시 예외 발생
  • pollLast(): rear에 있는 요소를 제거하고 반환, 데크가 비어 있을 시 null 반환

 

front(←)	…	rear(→)
removeFirst pollFirst		removeLast pollLast

 

• 반환
  • getFirst(): front 원소 반환, 제거는 하지 않고 데크가 비어 있을 시 예외 발생
  • peekFirst(): front 원소 반환, 제거는 하지 않고 데크가 비어 있을 시 null 반환
    • peek()와 동일
  • getLast(): rear 원소 반환, 제거는 하지 않고 데크가 비어 있을 시 예외 발생
  • peekLast(): rear 원소 반환, 제거는 하지 않고 데크가 비어 있을 시 null 반환

 

front(←)	…	rear(→)
getFirst peekFirst		getLast peekLast

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.