요약

• 스택의 원소들이 오름차순, 혹은 내림차순 상태를 유지하도록 하여 시간 복잡도를 O(n)으로 감소시키는 방법
• 사실상 스택 사용이 유의미한 유일한 알고리즘

동작 구조

1. 스택이 비어있거나, 새로운 값이 top의 값보다 큰 경우 push
2. 스택에 넣을 새로운 값이 top의 값보다 작은 경우, top이 새로운 값보다 작아질 때 까지 pop → 오름차순 정렬일 때

ex) 스택에 2, 7, 8, 5, 4, 6을 넣을 때

Stack [2] ← 7 삽입

Stack [2, 7] ← 8 삽입

Stack [2, 7, 8] ← 5 삽입

Stack [2, 5] ← 4 삽입

Stack [2, 4] ← 6 삽입

Stack [2, 4, 6]

특징/강점

• 스택이 오름차순/내림차순으로 유지되도록 하는 방법
• n^2 이상의 완전탐색이 필요한 연산을 한번의 탐색으로 해결 가능
• 시간 복잡도: O(1)

한계

• 주어진 값 전체를 오름차순/내림차순으로 정렬하는 것이 아님