부산대학교자료구조
Scientific Inference Lab

First In, First Out

Queues and Deques

FIFO와 양 끝 연산을 추적하고 원형 큐와 시뮬레이션을 계산한다.

문제 1

큐 연산 추적

빈 큐에 다음 연산을 차례로 호출한다. 상태는 왼쪽이 앞쪽(front), 오른쪽이 뒤쪽(rear)이다.

enqueue(5) → enqueue(8) → dequeue() → enqueue(2) → enqueue(9) → dequeue() → size()
  1. 반환값이 있는 호출마다 반환값을 적는다.
  2. 모든 호출을 마친 뒤의 최종 큐 상태를 적는다.
  3. 같은 연산 순서를 스택(push, pop)으로 바꾸면 첫 pop()이 무엇을 반환하는지 적고 차이를 설명한다.
해설 펼치기
  1. 첫 dequeue()는 5, 둘째 dequeue()는 8, size()는 2다.
  2. [2, 9]다.
  3. 스택에서는 가장 나중에 넣은 8을 반환한다. 큐는 FIFO라 가장 먼저 넣은 5가 먼저 나온다.
문제 2

원형 큐의 인덱스

길이 m = 6인 배열로 만든 원형 큐에서 첫 원소 위치가 j = 4, 원소 수가 n = 3이다. i번째 값은 a[(j + i) mod m]에 있다. 2와 3은 이 상태에서 각각 따로 생각한다.

  1. 세 원소가 놓인 배열 인덱스를 논리 순서대로 적고, 논리 인덱스 2의 배열 인덱스를 적는다.
  2. enqueue(x)를 호출하면 x가 저장되는 배열 인덱스와 호출 뒤 n을 적는다.
  3. dequeue()를 호출하면 반환하는 칸과 호출 뒤 j, n을 적는다.
  4. n = m이 되어 배열을 길이 12로 늘릴 때 원소를 복사하는 규칙과 새 j를 적는다.
해설 펼치기
  1. 4, 5, 0이다. 논리 인덱스 2는 (4 + 2) mod 6 = 0이다.
  2. end = (4 + 3) mod 6 = 1이므로 인덱스 1이고 n = 4다.
  3. a[4]를 반환하고 j = (4 + 1) mod 6 = 5, n = 2다. 원소를 옮기지 않는다.
  4. 새 배열 b에 b[i] ← a[(j + i) mod m]으로 논리 순서대로 n개를 복사하고 j = 0으로 둔다.
문제 3

list로 만든 큐

원소가 n개인 Python list로 큐를 만든다.

  1. 뒤쪽을 인덱스 n − 1로 둘 때 enqueue와 dequeue에 쓰는 메서드와 비용을 적는다.
  2. 뒤쪽을 인덱스 0으로 둘 때 같은 두 연산의 비용을 적는다.
  3. 방향만 바꾸어서는 두 연산을 모두 O(1)로 만들 수 없는 이유를 적는다.
  4. list.pop(0) 대신 collections.deque의 어떤 메서드를 쓰면 되는지와 그 비용을 적는다.
해설 펼치기
  1. append(x)는 상각 O(1), pop(0)은 뒤 원소 n − 1개를 옮겨 O(n)이다.
  2. insert(0, x)가 O(n), pop()이 상각 O(1)이다.
  3. list는 왼쪽 끝의 추가·삭제가 원소 이동 때문에 O(n)인데, 큐는 두 끝을 모두 쓰므로 어느 방향이든 한 연산이 왼쪽 끝을 쓴다.
  4. popleft()를 쓰며 O(1)이다. append와 함께 쓰면 FIFO다.
문제 4

큐로 시뮬레이션하기

  1. 발표 차례를 정하려고 큐 [P, Q, R, S, T](왼쪽이 앞쪽)의 앞 사람을 뒤로 2번 보낸 뒤 다음 앞 사람에게 첫 발표 차례를 배정하고 큐에서 삭제한다. 무작위 추첨은 아니다. 이동마다 큐 상태와 첫 발표자, 삭제 뒤 큐를 적는다.
  2. 앞 사람을 뒤로 한 번 보내는 동작을 큐 연산 두 개로 적는다.
  3. 프린터 한 대에 작업이 도착 시각 0, 3, 4에 들어오고 처리 시간은 각각 5, 4, 2다. 프린터는 비면 앞쪽 작업부터 처리한다. 각 작업의 처리 시작 시각과 대기 시간, 평균 대기 시간을 구한다.
  4. 평균 대기 시간 한 번의 결과만으로 시뮬레이션을 판단하기 어려운 이유를 적는다.
해설 펼치기
  1. 1번: [Q, R, S, T, P], 2번: [R, S, T, P, Q]. 첫 발표자는 R이며 큐에서 삭제하면 [S, T, P, Q]가 된다.
  2. enqueue(dequeue())다.
  3. 시작 시각은 0, 5, 9이고 대기 시간은 0 − 0 = 0, 5 − 3 = 2, 9 − 4 = 5다. 평균은 (0 + 2 + 5) / 3 = 7/3 ≈ 2.33이다.
  4. 도착이 무작위면 실행마다 결과가 달라지므로 여러 번 실행한 평균과 큐에 남은 작업 수도 함께 봐야 한다.
문제 5

덱의 양 끝

빈 덱에 다음 연산을 차례로 호출한다. 상태는 왼쪽이 앞쪽이다.

add_rear(1) → add_rear(2) → add_front(0) → remove_rear() → add_front(9) → remove_front()
  1. 두 삭제 연산의 반환값과 마지막 상태를 적는다.
  2. 덱으로 스택과 큐를 만들 때 각각 추가와 삭제에 쓸 끝을 적는다.
  3. 문자열 level과 radix를 덱의 양 끝 비교로 회문 검사할 때 각각 몇 번째 비교에서 결론이 나는지와 결과를 적는다.
  4. 인덱스로 가운데 원소를 자주 읽는 작업에서 deque보다 list가 나은 이유를 적는다.
해설 펼치기
  1. remove_rear()는 2, remove_front()는 9를 반환하고 마지막 상태는 [0, 1]이다.
  2. 스택은 같은 끝에서 추가·삭제하고, 큐는 뒤쪽에서 추가하고 앞쪽에서 삭제한다.
  3. level은 l과 l, e와 e를 비교해 같고 가운데 v 하나가 남아 2번째 비교 뒤 회문으로 결론 난다. radix는 첫 비교(r과 x)에서 달라 회문이 아니다.
  4. list는 인덱스로 임의 접근이 O(1)이다. deque는 양 끝 연산이 빠르게 설계되었을 뿐 모든 리스트 연산이 빠른 구조가 아니다.