염준영
가입: 2021년 3월 14일 올린 글: 23
|
올려짐: 2021년3월16일 15:24 주제: HW2 4번 질문드립니다. |
|
|
과제 2 4번에 보면 두 개의 스택으로 큐를 구현하라고 되어 있는데, 그 밑 문단에는 L과 R을 리스트라고 언급하시는데, 이는 리스트를 스택처럼 사용(리스트의 헤드를 스택의 맨 위로 해석)하라는 뜻인가요?
그리고 큐에 넣고 빼는 작업이 거의 한 스텝에 이루어진다고 되어 있는데,
밑 설명에서 "리스트를 뒤집는어서 넣는" 작업은 O(n)의 시간이 걸리고,
찾아본 결과 스택을 가지고 Worst-case constant time의 큐를 구현하는 방법은
6개의 스택을 사용하거나, 3개의 스택과 lazy evaluation을 사용한 알고리즘(https://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks)이 알려져 있다고 하는데, 4번 문제에서 말씀하신 "거의 한 스텝"은 amortized O(1) 을 뜻하는 건가요? |
|