자료구조

자료 구조란?
프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론, 혹은 과목.
컴퓨터과학에서 알고리즘과 함께 가장 중요한 기초이론이다. 이것을 공부하지 않고 상위 과목을 공부하는 건 사실상 불가능하다. 영어로 치면 알파벳을 모르는 상태로 독해를 공부하겠다는 것과 마찬가지다. -나무위키-

Stack

데이터를 순서대로 쌓는 구조.
예를 들어 동전을 쌓는다고 가정해보자. 동전을 바닥부터 하나씩 쌓아올리게 된다. 그리고 쌍인 동전을 무너뜨리지 않고, 처음에 쌓은 동전을 꺼내고 싶다면 마지막에 쌓은 동전부터 차례대로 치워나가야한다. 이때 동전을 쌓을때는 맨위 동전의 위로 차곡차곡, 동전을 치울때도 맨위 동전부터라는 하나의 방향으로 이루어지는데 이를 제한적 접근이라고하며, 이는 Stack 자료구조의 특징이다.

• LIFO; Last in First Out 마지막 데이터가 먼저나온다.
• FILO; First in Last Out 처음 데이터가 마지막에 나온다.

Queue

큐(Queue)는 '대기행렬', '줄을 서서 기다리다'라는 뜻을 가지고 있다. Stack과 다르게 처음 데이터가 처음에 나오고, 마지막데이터가 마지막에나오는 형태다. 순서대로라고도 할 수 있겠다. 예를들어보자면 유명한 맛집을 갔더니 줄이 길었다. 이대 먼저 줄을선 사람들이 먼저 음식을 먹는다고 생각하면 되겠다.
컴퓨터 장치들 상에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도의차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용하며, 이를 통틀어 Buffer라고 한다. 흔이 말하는 버퍼링의 예로 영상재생을 위한 데이터가 충분하지 않을때 데이터를 Queue에 모아두는 작업을 말한다.

• LIFO; Last in First Out 마지막 데이터가 마지막에나온다.
• FILO; First in Last Out 처음 데이터가 처음에 나온다.

Graph

여기서 말하는 Graph는 흔히들 말하는 선형그래프나, 막대그래프 등이 아니고, 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조다.

Graph와 Tree 비교

	Graph	Tree
정의	노드(Node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조	Graph의 한 종류이면서, DAG(DirectedAcyclic Graph, 방향성이 있는 비순환 그래프)의 한종류
방향성	방향 그래프(Directed), 무방향(Undirected) 모두 존재	방향 그래프(Directed)
루트 노드	루트 노드의 개념이 없음	한 개의 루트 노드만이 존재, 모든 자식 노드는 한개의 부모 노드만을 가짐
부모-자식	부모-자식의 개념이 없음	부모-자식 관계, top-bottom, bottom-top으로 이루어짐.

BST; Binary Search Tree

이진트리(Binary Tree)란?
자식 노드가 최대 두개인 노드들로 구성된 트리구조.
이진 탐색 트리(Binary Search Tree)란?
모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

이진트리 종류별 특징

종류	특징
정 이진 트리(Full binary tree)	각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
포화 이진 트리(Perfect binary tree)	정 이진 트리이면서 완전 이진 트리인 경우로, 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 채워저 있는 트리이다.
완전 이진 트리(Complete binary tree)	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.