Stack, Queue, Graph, Tree

1.Stack

• Stack의 사전적 의미는 '쌓다','쌓이다','포개지다' 등이 있다. 이것처럼 Stack은 데이터를 순서대로 쌓는 구조를 말한다. 이렇게 데이터를 순서대로 쌓다보면, 제일 먼저 들어간 데이터는 가장 나중에 나올 수 있을 것이다.
• 이러한 Stack 자료 구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다.
• 실생활 예시로는 '막다른 골목길'을 생각하면 좋다. 컴퓨터에서의 예시는 '뒤로가기,앞으로가기'기능이 있다.
• 코드 구현시, 배열의 push, pop을 사용하면 편리하다.

2. Queue

• Queue의 사전적 의미는 '줄을 서서 기다리다','대기 행렬' 등이 있다. Stack과는 반대개념이다. 가장 먼저 들어온 데이터가 제일 먼저 나가기 때문이다.
• Queue 의 자료구조를 FIFO(First In First Out) 또는 LILO(Last In Last Out)라고 부른다.
• 실생활 예시로는 '톨게이트'가 있고, 컴퓨터에서의 예시로는 프린터 인쇄 작업이 있다.
• 보통 컴퓨터 장치들이 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위해서 임시 기억 장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 Buffer라고 한다.
• 코드 구현시, 배열의 push, shift를 사용하면 편리하다.

3. Graph

• 컴퓨터 공학에서의 자료구조 그래프는 네트워크 망처럼 '여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조'의 모습을 가지고 있다.
• 하나의 점을 그래프에서는 정점(vertex)라고 부르고,
• 두 점이 직접적인 관계에 있는 경우 간선(edge)으로 연결되어 있고,
• 간접적인 관계라면 몇개의 점과 선에 걸쳐 이어진다.
• 추가적인 정보, 예를들면 가중치(연결의 강도을 알려주는 수치)가 적혀있지 않으면 비가중치 그래프라고 한다.
• 간선에 연결정도(거리 등)를 표현한 그래프를 가중치 그래프라고 한다.

3-1. Undirected Graph

: 무(방)향 그래프 : 양방향이 가능할 때

3-2. Directed Graph

: 일방통행처럼 한방향일 때

3-3. in-degree(진입차수)/out-degree(진출차수)

: 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지 나타낸다.

3-4. Adjacency(인접)

: 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.

3-5. Self loop(자기 루프)

: 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우를 '자기 루프를 가졌다'라고 한다. 다른 정점을 가지지 않는 것이 특징이다.

3-6. Cycle(사이클)

: 한 정점에서 출발하여 다시 해당 정점으로 돌아올 수 있다면 '사이클이 있다'라고 한다.

4. Graph의 표현방식: 인접행렬 & 인접리스트

4-1. 인접행렬

• 두 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 표이다. 만약, 가중치 그래프라면 1 대신 의미 있는 값이 저장되어 있을 것이다.
• 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 많은 메모리를 차지한다.

4-2. 인접리스트

• 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한 것이다.
• 인접 리스트는 인접할 때만을 보여주기 때문에 메모리를 효율적으로 사용할고 싶을때 사용한다.

5. Tree

• Graph의 일종으로, 단방향 그래프를 한 구조이다. 아래로만 뻗어나가기때문에 사이클은 없다.
• 가계도처럼 보이는 이 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조이다.
• 하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있어서 비선형 구조에 해당한다.
• 루트(Root)라는 하나의 꼭지점 데이터를 시작으로 여러개의 데이터를 간선으로 연결한다.그리고, 각 데이터를 노드(Node)라고 한다. 두 개의 노드가 상하계층으로 연결되면 부모/자식관계가 된다. 자식이 없는 노드는 Leaf Node라고 부른다.
• 트리의 대표적인 실사용 예제는 조직도가 있고, 컴퓨터에서는 폴더구성에 트리구조가 적용되어있다.

5-1. Node(노드)

:트리 구조를 이루는 모든 개별 데이터

5-2. Root (루트)

:트리 구조의 시작점이 되는 노드

5-3. Parent Node(부모노드)

: 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드

5-4. Child Node(자식노드)

: 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

5-5. Leaf(리프)

: 트리 구조의 끝지점이고, 자식 노드가 없는 노드

5-6. Depth(깊이)

: 루트로부터 하위 계층의 특정 노드까지의 깊이

5-7. Level(레벨)

: 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 할 수 있다. 이렇게 같은 레벨에 나란히 있는 노드를 형제 노드라고 부른다.
: 루트노드의 레벨이 1이다.

5-8. Height(높이)

: 리프 노드를 기준으로 루트까지의 간선 수
: 리프 노드의 높이는 0이다.

5-9. Sub tree(서브트리)

: 트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다.

6. Binary Search Tree

6-1. Binary Tree(이진 트리)

• 자식 노드가 최대 두개인 노드들로 구성된 트리이다. 이 두개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.
  -이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.
• Full binary tree(정 이진 트리): 각 노드가 0개 혹은 2개의 자식 노드를 가진다.
• Complete binary tree(포화 이진 트리): 마지막 레벨을 제외한 모든 노드가 가득 차 있어야하고, 마지막 레벨의 왼쪽이 채워져있어야한다.
• Perfect binary tree(완전 이진 트리): 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져있는 트리이다.

6-2. Binary Search Tree(이진 탐색 트리)

• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.
• 균형 잡힌 데이터가 입력되는 경우, 한쪽으로 노드들이 몰리게 될 수 있다.