다음은 연결 리스트를 이용하여 스택을 구현한 C 코드이다. (가), (… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

다음은 연결 리스트를 이용하여 스택을 구현한 C 코드이다. (가), (나)에 들어갈 내용을 바르게 연결한 것은?
typedef struct _node {
   int key;
   struct _node *next;
} node;

node *head = NULL;
node *tail = NULL;

void init() {
   head = (node*)malloc(sizeof(node));
   tail = (node*)malloc(sizeof(node));
   head->next = tail;
   tail->next = tail;
}

int push(int k) {
   node *t;
   if((t = (node*)malloc(sizeof(node))) == NULL) {
      printf("\n Out of memory");
      return -1;
   }
   t->key = k;
   [        (가)        ]
   head->next = t;
   return k;
}

int pop() {
   node *t;
   int i;
   if(head->next == tail) {
      printf("\n Stack underflow");
      return -1;
   }
   t = head->next;
   i = t->key;
   [        (나)        ]
   free(t);
   return i;
}
(가) (나)

t->next = head; head->next = t->next;

t->next = head->next; head->next = t->next;

t->next = head->next; head = t->next;

t->next = head->next; head->next = t;

(가)는 t->next = head->next;, (나)는 head->next = t->next;이다.
push는 새 노드 t를 head 바로 뒤에 끼워 넣으므로, 먼저 t가 기존 첫 노드를 가리키게 한 뒤 head->next = t를 수행한다. pop은 첫 노드 t를 떼어 내므로 head가 t의 다음 노드를 가리키게 한 뒤 t를 해제한다.
(가)를 t->next = head로 쓰면 새 노드가 더미 head를 가리켜 기존 노드들과의 연결이 끊긴다.
(나)를 head = t->next로 쓰면 더미 head 노드 자체가 바뀌어 스택 구조가 깨진다.
(나)에 head->next = t를 쓰면 곧 해제할 t를 계속 가리키게 되어 삭제가 되지 않는다.