[CS] 자료구조

1. 분류

1) 선형 vs 비선형

(1) 선형구조: 배열, 선형리스트, 연결리스트, 스택, 큐, 데크 (1:1 관계)

(2) 비선형구조: 트리, 그래프 (1:다, 다:다 관계)

 

2) 순차 vs 연결

(1) 순차자료구조: 배열 (논리적 순서 = 물리적 순서)

(2) 연결자료구조: 포인터 (논리적 순서 != 물리적 순서)

 

2. 스택 (Stack)

LIFO (Last In First Out)

출입구 = top

 

- top(): 반환

- push(): 삽입

- pop(): 삭제 및 반환

- isempty()

- isfull()

 

3. 큐 (Queue)

FIFO (First In First Out)

입구 = rear

출구 = front

 

- enQueue: 삽입

- deQueue: 삭제

 

4. 트리 (Tree)

계층형 자료 구조 (1:다)

 

5. 그래프

정점과 간선의 집합 (다:다)

 

* 그래프 구현 방법

- 인접행렬: 배열 (순차자료구조) 활용, 간선의 유무 저장

- 인접리스트: 포인터 (연결자료구조) 활용, 각 정점의 차수만큼 노드 연결

 

6. 자료구조 활용

1) 리스트: DBMS 인덱스, 탐색, 정렬

2) 스택: 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 후위 표기법(e.g., 11+, 22+)으로 표현된 수식의 연산, 텍스트 에디터 Undo

3) 큐: 운체 작업스케줄링, 대기 행렬 처리, 비동기(비순차) 데이터 교환, 키보드 버퍼 이용, 스풀(중앙처리장치와 입출력장치 독립적으로 동작하게) 운용

4) 데크(Deque): 스택과 큐의 장점만 활용

5) 트리: 탐색, 정렬, 문법 파싱, 허프만 코드(문자열을 사용한 빈도수에 따라 압축하는 알고리즘), 결정 트리(분류규칙), 게임

6) 그래프: 컴퓨터 네트워크, 전기회로 분석, 이항 관계, 연립 방정식