자료구조 구현하기(C++) - 선형 자료구조

C++에서 다양한 자료구조는 STL(Standard Template Library) 컨테이너를 활용하여 간단하게 구현할 수 있습니다. 각 자료구조에 대해 어떤 STL 컨테이너를 사용할 수 있는지 설명하겠습니다.

---

대표적인 선형 자료구조의 목록과 권장 STL 컨테이너를 요약하면 다음과 같습니다.

---

1. 배열 (Array)

STL 추천 컨테이너

• 고정 크기 배열: std::array
• 동적 크기 배열: std::vector

STL 컨테이너 - Array 관련 글

https://coding-potato-record.tistory.com/20

STL 컨테이너 - Vector 관련 글

https://coding-potato-record.tistory.com/15

구현 방법

• 기본 배열 (Static Array)혹은 STL std::array 사용.

• 동적 배열: std::vector를 사용하면 크기를 유연하게 조절할 수 있음.

---

2. 리스트 (List)

STL 추천 컨테이너

• 단일 연결 리스트: std::forward_list
• 이중 연결 리스트: std::list
• 원형 연결 리스트: 사용자 정의(기본적으로 std::list 활용)

STL 컨테이너 - List 관련 글

https://coding-potato-record.tistory.com/18

STL 컨테이너 - Forward_List 관련 글

https://coding-potato-record.tistory.com/265

구현 방법

- 단일 연결 리스트 (Singly Linked List)

STL에서는 std::forward_list가 단일 연결 리스트를 지원합니다.

- 이중 연결 리스트 (Doubly Linked List)

STL에서는 std::list가 이중 연결 리스트를 지원합니다.

- 원형 연결 리스트 (Circular Linked List)

STL은 원형 연결 리스트를 직접 제공하지 않습니다.

• 이를 구현하려면 std::list를 활용하여 마지막 노드가 첫 번째 노드를 가리키게 연결하면 됩니다.

 

---

3. 스택 (Stack)

STL 추천 컨테이너

• std::stack을 사용.

STL 컨테이너 - Stack 관련 글

https://coding-potato-record.tistory.com/22

구현 방법

• STL std::stack: 내부적으로 std::deque를 기본 컨테이너로 사용합니다.
• std::deque는 LIFO(Last In First Out) 자료구조를 지원합니다.

• 필요에 따라 내부 컨테이너를 std::vector 또는 std::list로 변경 가능.

---

4. 큐 (Queue)

STL 추천 컨테이너

• 일반 큐: std::queue
• 우선순위 큐: std::priority_queue
• 덱: std::deque

STL 컨테이너 - Queue 관련 글

https://coding-potato-record.tistory.com/23

STL 컨테이너 - Deque 관련 글

https://coding-potato-record.tistory.com/19

구현 방법

- 일반 큐 (Queue)

• STL std::queue: FIFO(First In First Out) 자료구조를 지원합니다.

- 우선순위 큐 (Priority Queue)

• STL std::priority_queue: 내부적으로 힙(Heap)을 사용하며, 기본적으로 최대 힙(Max-Heap)을 지원합니다.

• 최소 힙(Min-Heap)을 구현하려면 커스텀 비교 함수를 제공합니다:

- 덱 (Deque)

• STL std::deque: 양쪽에서 삽입/삭제가 가능한 큐 자료구조입니다.

 

---

5. 정리

배열 (Array)	std::array, std::vector	고정 크기: std::array, 동적 크기: std::vector
단일 연결 리스트	std::forward_list	간단한 연결 리스트
이중 연결 리스트	std::list	양방향 연결 리스트
원형 연결 리스트	std::list (사용자 정의)	직접 연결 관계를 설정해야 함
스택 (Stack)	std::stack	내부 컨테이너 기본: std::deque
일반 큐 (Queue)	std::queue	FIFO 동작 지원
우선순위 큐 (Priority Queue)	std::priority_queue	최대 힙/최소 힙 구현 가능
덱 (Deque)	std::deque	양쪽 삽입/삭제 지원