NAME

queue - 연결 리스트 및 큐 구현

DESCRIPTION

<sys/queue.h> 헤더 파일에서 다음 자료 구조들을 정의하고 조작하는 매크로 세트를 제공한다.

• 단일 연결 리스트 (SLIST)

• 이중 연결 리스트 (LIST)

• 단일 연결 꼬리 큐 (STAILQ)

• 이중 연결 꼬리 큐 (TAILQ)

• 이중 연결 원형 큐 (CIRCLEQ)

모든 자료 구조에서 다음 기능성을 지원한다.

• 리스트 머리에 새 항목 삽입하기.

• 리스트 내 임의 항목 뒤에 새 항목 삽입하기.

• 리스트 머리에서 O(1)으로 항목 제거하기.

• 순방향으로 리스트 순회하기.

사용 자료 구조의 복잡도에 따라 코드 크기와 실행 시간이 달라지므로 프로그래머들은 적절한 자료 구조를 고르도록 신경쓸 필요가 있다.

단일 연결 리스트 (SLIST)

단일 연결 리스트는 가장 단순하며 위의 기능들만 지원한다. 단일 연결 리스트는 데이터 양이 많고 제거가 드물거나 없는 응용에, 또는 LIFO 큐 구현에 잘 맞는다. 단일 연결 리스트에는 추가로 다음 기능성이 있다.

• 리스트 내 임의 항목을 O(n)으로 제거하기.

단일 연결 꼬리 큐 (STAILQ)

단일 연결 꼬리 큐에는 추가로 다음 기능성이 있다.

• 리스트 끝에 항목 추가하기.

• 리스트 내 임의 항목을 O(n)으로 제거하기.

• 두 리스트 이어 붙이기.

하지만

• 리스트 삽입 시 리스트 머리를 지정해야 한다.

• 각 머리 항목에 포인터가 한 개가 아니라 두 개 필요하다.

단일 연결 꼬리 큐는 데이터 양이 많고 제거가 드물거나 없는 응용에, 또는 FIFO 큐 구현에 잘 맞는다.

이중 연결 자료 구조들

이중 연결 방식 자료 구조 모두(리스트와 꼬리 큐)에서 추가로 다음이 가능하다.

• 리스트 내 임의 항목 앞에 새 항목 삽입하기.

• 리스트 내 임의 항목을 O(1)으로 제거하기.

하지만

• 각 항목에 포인터가 한 개가 아니라 두 개 필요하다.

이중 연결 리스트 (LIST)

연결 리스트는 가장 단순한 이중 연결 자료 구조다. 위에 더해서 다음 기능성이 있다.

• 역방향으로 순회하기.

하지만

• 역방향으로 순회하려면 순회를 시작할 항목과 그 항목을 담은 리스트를 지정해야 한다.

이중 연결 꼬리 큐 (TAILQ)

꼬리 큐에는 추가로 다음 기능성이 있다.

• 리스트 끝에 항목 추가하기.

• 꼬리에서 머리로 역방향 순회하기.

• 두 리스트 이어 붙이기.

하지만

• 리스트 삽입 및 제거 시 리스트 머리를 지정해야 한다.

• 각 머리 항목에 포인터가 한 개가 아니라 두 개 필요하다.

이중 연결 원형 큐 (CIRCLEQ)

원형 큐에는 위에 더해서 다음 기능성이 있다.

• 첫 번째 항목과 마지막 항목이 연결되어 있다.

하지만

• 순회 종료 조건이 더 복잡하다.

CONFORMING TO

POSIX.1, POSIX.1-2001, POSIX.1-2008에 없다. BSD들에 있다. (4.4BSD에서 매크로들이 처음 등장했다.)

NOTES

일부 BSD들에선 STAILQ 대신 SIMPLEQ를 제공한다. 둘은 동일하지만 역사적 이유 때문에 다른 이름이 붙었다. STAILQ는 FreeBSD에서 유래했고 SIMPLEQ는 NetBSD에서 유래했다. 어떤 시스템에선 호환성을 위해 두 매크로 세트를 모두 제공한다. glibc에서 STAILQ와 SIMPLEQ를 모두 제공하는데, STAILQ_CONCAT()에 대응하는 SIMPLEQ 매크로가 없다는 점을 빼면 동일하다.

SEE ALSO

circleq(3), insque(3), list(3), slist(3), stailq(3), tailq(3)

---

2021-03-22