스택을 사용하는 우선 순위 대기열

Question

하나는 스택을 사용하여 우선 순위 대기열을 빌드 할 수 있으므로 각 조작에 대해 동일한 복잡성이있는 경우가 있습니다. 그럴 수 있을까요?그렇다면 어떻게?수행 할 수있는 최상의 솔루션이 아닌 경우?

배열을 사용하는 스택의 각 작동은 $ o (1) $ 이지만 우선 순위 대기열의 거의 모든 작동은 $ o (logn) $ . 구현은 $ 2D $ 스택을 사용하여 수행 할 수 있습니다. 스택의 각 요소는 다시 스택입니다. 주 스택의 첫 번째 요소가 다른 스택의 첫 번째 요소 인 경우. 덱스 작동은 $ o (n) $ 이 LIFO이고 우선 순위 큐가 FIFO입니다.

Answer 1

그것에 대해 생각해보십시오.모든 항목을 우선 순위 대기열에 추가 한 다음 정렬 된 순서로 항목을 제거하여 배열을 정렬 할 수 있습니다.

일정한 시간에 우선 순위 대기열을 실행할 수 있으면 선형 시간을 정렬 할 수 있습니다.그러나 당신은 할 수 없습니다.