[염준영]

과제 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) 을 뜻하는 건가요?

[shkim]

네, 이해하신게 맞습니다.
"리스트를 뒤집어서 넣는" 작업에 O(n) 시간이 걸리지만, 그 뒤 n번의 dequeue가 각각 O(1) 시간이 걸리므로 amortized O(1) 시간이 소모됩니다.