Deque와 PriorityQueu의 시간복잡도

 

Deque

 - 양 끝에서의 삽입과 삭제 연산이 O(1)의 시간복잡도를 가진다.

• addFirst(e): O(1) - 맨 앞에 요소 추가
• addLast(e): O(1) - 맨 뒤에 요소 추가
• removeFirst(): O(1) - 맨 앞의 요소 제거
• removeLast(): O(1) - 맨 뒤의 요소 제거
• getFirst(): O(1) - 맨 앞의 요소 반환
• getLast(): O(1) - 맨 뒤의 요소 반환
• offerFirst(e): O(1) - 맨 앞에 요소 추가 (실패 시 false 반환)
• offerLast(e): O(1) - 맨 뒤에 요소 추가 (실패 시 false 반환)
• pollFirst(): O(1) - 맨 앞의 요소 제거 및 반환 (비어있으면 null 반환)
• pollLast(): O(1) - 맨 뒤의 요소 제거 및 반환 (비어있으면 null 반환)
• peekFirst(): O(1) - 맨 앞의 요소 반환 (비어있으면 null 반환)
• peekLast(): O(1) - 맨 뒤의 요소 반환 (비어있으면 null 반환)
• removeFirstOccurrence(o): O(n) - 특정 요소의 첫 번째 발생 제거
• removeLastOccurrence(o): O(n) - 특정 요소의 마지막 발생 제거
• size(): O(1) - 요소의 개수 반환

PriorityQueue

 

• add(e): O(log n) - 요소 추가
• offer(e): O(log n) - 요소 추가 (실패 시 false 반환)
• remove(): O(log n) - 첫 번째 요소 제거
• poll(): O(log n) - 첫 번째 요소 제거 및 반환 (비어있으면 null 반환)
• peek(): O(1) - 첫 번째 요소 반환 (비어있으면 null 반환)
• element(): O(1) - 첫 번째 요소 반환 (비어있으면 예외 발생)
• contains(o): O(n) - 특정 요소가 포함되어 있는지 확인
• size(): O(1) - 요소의 개수 반환
• clear(): O(n) - 모든 요소 제거