3. 선형 자료구조 [디딤돌 자료구조와 알고리즘 with C++]

3. 선형 자료구조

자료를 선형으로 보관하는 자료 구조에는 배열, 연결리스트, 스택, 큐, 덱 등이 있어요. 이와 같은 자료구조에 자료를 보관하거나 삭제, 검색 등의 연산을 수행할 때 반복적인 방법으로 해결할 때가 많아요.

 

배열은 자료를 연속적인 메모리에 보관하는 자료구조예요. 순차리스트라고도 부르죠. 연결리스트는 하나의 자료를 보관하는 노드들을 선형으로 그릴 수 있어요. 실제 메모리는 순차적이지 않지만 논리적으로 선형으로 나타낼 수 있어요. 연결리스트를 구성하는 노드는 하나의 데이터와 링크의 조합이예요. 링크는 노드의 위치 정보로 노드에 하나의 링크가 있으면 단순 혹은 단일 연결리스트라 부르고 두 개 있으면 이중 연결리스트라 불라요.

 

특히 배열은 프로그래밍 언어에서 제공하는 형식 배열만 있는 것이 아니라 연속적인 메모리에 같은 자료를 보관하는 자료구조는 배열이예요. STL에서는 확장 가능한 배열인 vector와 연결 리스트를 list 이름의 템플릿 클래스를 제공하고 있어요.

 

이 책에서는 vector와 list의 사용 방법을 소개한 후에 이들을 모델로 삼아 직접 구현해 보는 실습을 진행할 거예요. 이미 만들어져 있는 것을 사용하면 될 것을 왜 만드냐고 할 수도 있겠지만 여기에서는 자료구조의 특징을 이해하는 것과 반복 알고리즘을 연습하기 위한 것이예요.

 

 

 

그리고 배열과 연결리스트를 이용하여 임시적으로 자료를 보관하거나 꺼내서 사용하는 버퍼 중에 이름이 붙여진 자료구조들이 있어요. 이름이 붙여진 버퍼에는 스택과 큐와 덱이 있어요. 스택은 한 쪽으로 보관하고  꺼내는 버퍼로 LIFO(Last In First Out)방식으로 동작해요. 큐는 한 쪽으로 보관하고 다른 쪽으로 꺼내는 버퍼로 FIFO(First In First Out)방식으로 동작해요. 덱은 양쪽으로 보관하거나 꺼낼 수 있는 버퍼예요.

 

이 책에서는 스택과 큐, 덱을 이해하기 위해 간단히 만들어 보고 STL에서 제공하는 stack, queue, deque을 살펴볼 거예요.

 

특히 큐는 운영체제의 스케쥴러에서 주요한 자료구조로 사용하는데 이 책에서는 라운드 로빈 방식의 스케쥴러 시뮬레이션을 만드는 과정을 통해 큐를 활용하는 방법을 배울 거예요.

 

그리고 책의 뒷 부분에 가면 동적 프로그래밍의 순열 문제와 깊이 우선 탐색을 다루면서 스택을 활용하는 방법을 배울 거예요.