자료 구조

자료 구조

자료 구조의 분류

자료 구조의 활용

• 정렬(Sort)
  • 집합된 데이터 레코드를 일정 기준으로 재배열하는 것
  • 오름차순(ASC), 내림차순(DESC)
• 검색(Search)
  • 저장된 데이터 레코드 중 원하는 값을 빠르게 찾는 것
• 인덱스(Index)
  • 데이터베이스 성능에 많은 영향을 주는 DBMS의 구성 요소로 테이블과 클러스터에 연관되어 독립적인 저장 공간을 보유하며, 데이터베이스에 저장된 자료를 더욱 빠르게 조회하기 위하여 별도로 구성한 순서 데이터
  • 예) 책의 맨 뒤에 빠르게 찾기에 해당함
  • B-트리 인덱스는 분기를 목적으로 하는 Branch Block을 가지고 있음
  • BETWEEN 등 범위(Range) 검색에 활용될 수 있음
• 파일 편성
  • 파일에서 레코드의 물리적인 배열 방법

 

선형 자료 구조

리스트(List)

• 선형 리스트(Linear List)
  • 배열(Array)과 같이 연속되는 기억 장소에 저장되는 리스트
  • 가장 간단한 데이터 구조 중 하나로 데이터 항목을 추가/삭제하는 것이 불편함

감자

배

옥수수

고구마

• 연결 리스트(Linked List)
  • 노드(Node)의 포인터 부분을 서로 연결시킨 리스트로 연속적인 기억 공간이 없어도 저장이 가능함
  • 노드의 삽입/삭제가 용이하며 포인터를 위한 추가 공간이 필요하므로 기억 공간이 많이 소모됨

 

스택(Stack)

• 리스트의 한쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 자료 구조
• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 방식
• 마지막 삽입된 자료의 위치를 Top, 가장 먼저 삽입된 자료의 위치를 Bottom이라고 함
• 스택 가드(Stack Guard) : 메모리상에서 프로그램의 복귀 주소와 변수 사이에 특정 값을 저장해 두었다가 그 값이 변경되었을 경우 오버플로우 상태로 가정하여 프로그램 실행을 중단하는 기술

• 스택의 응용 분야
  • 인터럽트 처리, 수식의 계산, 0-주소 지정 방식
  • 재귀 호출, 후위 표현(Postfix expression)의 연산 깊이 우선 탐색

스택의 삽입 일고리즘

if TOP >= n then call Stack-Full
else TOP ← TOP + 1
Stack(TOP) ← Data
end insert

스택의 삭제 일고리즘

if TOP = 0 then Underflow
else
remove Stack(TOP)
TOP ← TOP - 1

스택의 오버플로 알고리즘

TOP ← TOP + 1
if TOP > n then goto AA
else Stack(TOP) ← item

 

큐(Queue)

• 자료의 삽입 작업은 선형 리스트의 한쪽 끝에서, 삭제 작업은 다른 쪽 끝에서 수행되는 자료 구조
• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In First Out) 방식
• 큐의 응용 분야 : 운영체제의 작업 스케줄링 등에서 응용

 

데크(Deque)

• 자료의 삽입과 삭제가 리스트의 양쪽 끝에서 이루어지므로 두 개의 포인터를 사용하는 자료 구조
• 스택과 큐를 복합한 형태
• 입력 제한 데크를 Scroll, 출력 제한 데크를 Shelf라고 함