[7급 국가직 자료구조론 2021년 9번]

다음과 같이 이중연결리스트를 이용하여 큐 자료구조를 정의하였다. 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;
}