2-1 데이터 입출력 구현

자료구조

 - 선형 구조(데이터를 연속적으로 연결한 자료 구조): 리스트,스택,큐,데크

 - 비선형 구조(데이터를 비연속적으로 연결한 자료 구조): 트리, 그래프

 

스택

 - LIFO(Last-In First-Out)형식

 - 입출력이 한쪽 끝으로만 제한된 리스트

 - PUSH,POP

 - 연산 시 1. 삽입 : OverFlow, 2. 삭제: UnderFlow

 - 인터럽트 처리, 함수 호출(재귀 호출 포함), 후위표현 연산(Postfix), DFS(깊이 우선 탐색)

 

큐

 - FIFO(First-In First-Out)형식

 - 한쪽에서는 ENQUEUE(삽입, 데이터를 차례대로 넣는 연산), 다른 쪽에서는 DEQUEUE(삭제, 처음 저장된 데이터부터 하나씩 꺼내는       연산

 - 데이터가 꺼내는 쪽에서 가장 가까운 데이터 Head(Front), 데이터를 넣는 쪽에서 가장 가까운 데이터 Tail(Rear)

- 운영체제의 작업 스케쥴링에 사용됨

 

데크(Deque: Double Ended Queue)

- 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조이다

- 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다

- 데크를 이용한 스택과 큐의 구현이 가능하다

- PUSH,POP

 -입력 제한 데크는 Scroll, 출력 제한 데크는 Shelf이다

 

선형 리스트

- 연속 리스트(Contiguous List) => 순차적

    - 배열과 같이 연속되는 기억장소에 저장되는 리스트

    - 중간에 데이터를 삽입하기 위해 연속되 빈 공간이 있어야함

    - 삽입, 삭제 시 자료의 이동이 필요함

   

 - 연결 리스트: 비순차적

     자료들을 반드시 연속적으로 배열X, 임의의 기억공간을 기억

      노드의 삽입, 삭제 작업이 용이

      기억공간이 연속적으로 놓여 있지 않아도 저장가능

      연결을 위한 포인터가 필요하기 때문에 순차 리스트에 비해 기억 공간의 효율이 좋지 않음

      연결을 위한 포인터를 찾는 시간이 필요하기 대문에 접근 속도가 느림

      중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

 

트리(Tree)

 - 그래프의 특수한 형태

 - 노드와 선분으로 되어 있고, 정점 사이에 사이클이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조

 - 근 노드(Root Node): 트리의 맨 위에 있는 노드

 - 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지의 수

 - 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수

 - 단말 노드(Terminal Node): 자식이 하나도 없는 노드, Degree가 0인 노드

 

트리 순회방법

 - 전위 순회(Preorder Traversal): Root -> Left -> Right

 - 중위 순회(Inorder Traversal): Left -> Root -> Right

 - 후위 순회(Postorder Traversal): Left -> Right -> Root

 

트리 종류

-이진 탐색 트리 (차수가 2이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리

                       부모 노드보다 작은 값은 외쪽으로 부모 노드보다 큰 값은 오른쪽 노드에 생성

 

-AVL 트리
  두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형 잡는 이진 탐색 트리

 

-2-3 트리

 2-3 트리는 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리

 AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분

 

-레드-블랙 트리

  레드-블랙 트리의 각 노드는 빨강 또는 검정의 색상을 가지고 있으며 스스로 균형을 잡는 이진 탐색 트리

 

그래프

방향 그래프

- 정점을 연결하는 선에 방향이 있는 그래프 n(n-1)

 

무방향 그래프

- 정점을 연결하는 선에 방향이 없는 그래프 n(n-1)/2