다음과 같이 이중연결리스트를 이용하여 큐 자료구조를 정의하였다. add… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

다음과 같이 이중연결리스트를 이용하여 큐 자료구조를 정의하였다. add는 큐의 삽입 알고리즘이고, delete는 큐의 삭제 알고리즘이다. ㉠, ㉡에 들어갈 내용을 바르게 연결한 것은?
typedef struct _dnode {
  int key;
  struct _dnode *prev, *next;
} dnode;
dnode *head = (dnode*)malloc(sizeof(dnode));
dnode *tail = (dnode*)malloc(sizeof(dnode));
head->prev = head;   head->next = tail;
tail->prev = head;   tail->next = tail;

int add(int k) {
  dnode *t = (dnode*)malloc(sizeof(dnode));
  if (t == NULL) {
    printf("\n Out of memory.");
    return -1;
  }
  t->key = k;
  ( ㉠ )
  tail->prev = t;  t->next = tail;
  return k;
}

int delete(void) {
  dnode *t; int i;
  t = head->next;
  if (t == tail) {
    printf("\n Queue underflow.");
    return -1;
  }
  i = t->key;
  ( ㉡ )
  free(t);  return i;
}

㉠ tail->prev = t;  t->prev = tail->prev;
㉡ head->next = t->next;  t->next->prev = head;

㉠ tail->prev->next = t;  t->prev = tail->prev->next;
㉡ head->next = t->next;  t->next->prev = head;

㉠ tail->prev->next = t;  t->prev = tail->prev;
㉡ head->next = t->next;  t->next = head;

㉠ tail->prev->next = t;  t->prev = tail->prev;
㉡ head->next = t->next;  t->next->prev = head;

㉠은 tail->prev->next = t; t->prev = tail->prev;, ㉡은 head->next = t->next; t->next->prev = head;이다.
add는 tail 바로 앞에 t를 끼우므로, tail->prev를 바꾸기 전에 기존 마지막 노드의 next와 t의 prev를 먼저 연결해야 한다. delete는 첫 노드 t를 빼고 head와 t의 다음 노드를 양방향으로 잇는다.
㉠에서 tail->prev = t를 먼저 실행하면 t->prev가 t 자신이 되고, 기존 마지막 노드의 next도 갱신되지 않는다.
㉠에서 t->prev = tail->prev->next로 쓰면 직전 문장으로 그 값이 이미 t이므로 t->prev가 자기 자신을 가리킨다.
㉡에서 t->next = head로 쓰면 새 첫 노드의 prev가 해제될 t를 계속 가리켜 역방향 연결이 깨진다.