비 계속 감소하는 큐 구현

Question

모두 알고 있듯이 표준 큐는 insert 및 popout의 두 가지 기본 작업을 지원합니다. 그리고 insert은 큐의 끝에서 발생합니다. popout은 큐의 헤드에서 발생합니다. 여기서는이 대기열을이 두 작업에 기반하여 비 감소, 또는 그 목표를 달성하기위한 몇 가지 추가 도움말 기능과 함께 정렬 할 수 있는지 여부를 알지 못합니다.

Answer 1

insert 기능을 약간 변경하면됩니다. 때마다 insert 대기열에 당신은 다음과 같은 알고리즘을 달성 할 수있는 대기열에 새로운 요소 장소를 찾아야 만합니다 :

새로운 기능을 사용하고 매번 새로운 요소가 중간에있는 요소보다 큰지 확인하십시오 리스트의 왼쪽에 새로운 원소를 삽입하려고 시도한다. 그렇지 않으면 원소의 적절한 위치를 찾을 때까지 반복적으로 대기열의 오른쪽에 삽입을 시도한다.

삽입을위한가는 알고리즘은 O(lg(n))입니다.

popout의 경우 지금 수행 한 작업 만 수행하면됩니다. 마지막 요소가 나타납니다.