큐(queue)를 연결리스트로 구현하는 경우 일반적으로 front와 r… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
큐(queue)를 연결리스트로 구현하는 경우 일반적으로 front와 rear 등 2개의 포인터를 사용한다. 만약 리스트의 포인터를 하나밖에 사용할 수 없다면 가장 효율적인 구조는? (단, 큐에 A, B, C, D의 순서로 입력되었고, 역원형리스트는 데이터가 입력된 순서의 역순으로 만든 원형리스트를 의미한다고 가정한다)
1
포인터가 첫 노드를 가리키는 원형리스트 구조
2
포인터가 마지막 노드를 가리키는 원형리스트 구조
3
포인터가 첫 노드를 가리키는 역원형리스트 구조
4
포인터가 마지막 노드를 가리키는 역원형리스트 구조
해설

포인터 하나로 큐를 구현할 때 가장 효율적인 것은 마지막 노드를 가리키는 원형리스트이다.

원형리스트에서 마지막 노드 D를 가리키면 그 다음 노드가 곧 첫 노드 A이다. 삽입은 ptr 뒤에 새 노드를 붙이고 ptr을 옮기면 되고, 삭제는 ptr의 다음 노드를 떼어내면 되므로 두 연산 모두 상수 시간에 끝난다.

  • 첫 노드를 가리키는 원형리스트는 삽입 위치인 마지막 노드를 찾으려면 리스트를 끝까지 순회해야 한다.
  • 첫 노드(가장 최근 입력 D)를 가리키는 역원형리스트는 가장 먼저 들어온 A를 삭제하려면 A의 앞 노드를 찾아 순회해야 한다.
  • 마지막 노드(A)를 가리키는 역원형리스트는 삽입은 쉽지만, A를 삭제하려면 앞 노드 B를 찾아 순회해야 한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 07년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기