[CS / TOPCIT] 자료구조

자료구조

1. 정의

자료를 컴퓨터의 기억장치 내에 저장하는 방법으로 다양한 자료를 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것

 

2. 분류

• 선형구조 : 배열, 선형리스트, 연결리스트, 스택, 큐, 데크 등
• 비선형구조 : 트리, 그래프 등

스택

1. 정의

한 곳에서만 출입 가능한 LIFO구조로 가장 나중에 쌓인 데이터가 가장 먼저 출력하게 되는 자료구조임

 

2. 연산의 종류

• top() : 스택의 맨 위에 있는 데이터 값 반환
• push() : 스택에 데이터 추가
• pop() : 스택에 데이터 삭제
• isempty() : 스택에 원소가 없으면 true
• isfull() : 스택에 원소가 있으면 true

큐

1. 정의

데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료구조로 FIFO 즉, 나중에 삽입된 원소가 먼저 출력된다

 

2. 연산의 종류

• enQueue : 데이터 삽입, rear를 움직여 큐의 공간을 확보한 후 데이터 삽입
• deQueue : 데이터 삭제, front를 움직여 가장 오래된 데이터를 다음 번째 데이터로 넘기게 된다

트리

1. 정의

원소들 간에 계층관계를 가지는 계층형 자료 구조, 원소들 간에 1:다 관계를 가진다. 트리는 레벨 0부터 시작함

 

2. 구성요소

• 루트 노드 : 트리의 시작 노드
• 간선 : 각 노드를 연결하는 선
• 자식 노드 : 루트 노드에 연결된 노드들
• 형제 노드 : 같은 부모 노드를 가진 자식 노드들
• 서브 트리 : 부모노드와 연결된 간선을 끊었을 때 생성되는 트리

그래프

1. 정의

객체를 나타내는 정점과 객체를 연결하는 간선들의 집합. 다:다 관계

 

2. 그래프 종류

• 무방향 그래프
• 방향 그래프
• 완전 그래프 : 그래프의 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프
• 가중 그래프