위에 쌓이는 것을 우선적으로, Stack

• 스택(Stack), 영어표현 그대로 ‘쌓기’를 나타낸다. 제일 위에 쌓여있는 요소를 가장 먼저 꺼낼 수 있는 자료구조이다. (LIFO : Last In First Out)
• 구조상 한쪽 끝에서만 자료를 넣고 뺄 수 있는 구조다.
• 값을 넣고(push), 값을 꺼내고(pop), 제일 위의 값을 확인하는(top, peek) 작업을 할 수 있다.
• 재귀 함수가 실행되는 순서나 여러 함수가 중첩되어 호출되는 경우 스택 구조로 작동한다.
• 스택 각각에 주어진 메모리보다 데이터를 더 넣거나(stack-overflow) 메모리가 비어있는 스택에서 값을 꺼내려고 하는 경우(stack-underflow) 오류가 발생한다.

차례대로 할 수 있어요, Queue

• 실생활의 줄서기와 비슷한 큐는 제일 먼저 들어온 데이터를 가장 먼저 꺼내야 하는 자료구조이다.
• 보통 맨 처음(head, front)와 맨 끝(rear, tail)을 의미하는 요소가 있다.
• 값을 넣고(enqueue), 값을 꺼내고(dequeue), 제일 앞의 값을 확인(front)하는 작업을 할 수 있다.
• 순환 큐 : front와 rear가 서로 연결된 구조의 큐. 메모리 관리가 쉽지만 자바스크립트는 garbage collection으로 인해 메모리를 쉽게 낭비하지 않다는 장점이 있다.
• 우선순위 큐 : 실생활에서 응급환자를 먼저 치료하는 것과 비슷하다. 데이터의 우선순위를 따져서 큐로 구성한다. 데이터를 선별하여 삽입해야 하기 때문에 번거로운 단점이 있다.

배열과는 사뭇다른 연결형 자료구조, 연결 리스트

• 크기가 동적이고, 데이터간 연결성을 부여하여 관리하는 자료구조이다.
• 연결 리스트는 데이터를 담고 있는 바구니인 노드(Node)로 구성되고, 노드간 연결이 핵심이다.
• 노드는 데이터를 담고 있지만 동시에 다음 노드를 향한 주소를 가지고 있다.
• 단일 연결 리스트 : 한 방향으로만 주소를 가지고 있는 연결 리스트, 노드는 다음 노드에 대한 정보만 알 수 있다.
• 이중 연결 리스트 : 양방향으로 노드를 연결하는 리스트, 일상생활의 음악 재생 앱과 비슷하다.
• 연결 리스트에 값을 추가하거나 삭제하는 것은 손쉽다. 해당위치에 노드를 만들어 데이터를 넣거나 빼고, 연결성을 만들어주면 된다.
• 연결 리스트는 배열과 다르게 인덱스를 가지지 않는다. 따라서 특정한 값을 검색하기 위해서는 재수가 없을 경우, 머리부터 끝까지 조사해야 한다.

자료구조	가져오기, 특정 데이터 검색	추가하기	삭제하기
연결리스트	O(n)	O(1)	O(1)

키와 값을 쌍으로. 암호화에 사용되는 해시테이블

내가 이전에 정리한 해시테이블 블로그 보러가기

• 데이터를 키와 값의 쌍으로 저장한다. 여기서 키는 해싱함수를 통과하게 되고, 암호화된 코드로 변환된다.
• 두 개 이상의 값에 하나의 키를 사용할 수 없다.
• 해싱함수를 통해서 동일한 암호화 코드가 나오면 충돌이 발생하게 된다. 다시 말해서, 해싱함수가 서로 다른 키에 대해서 동일한 버켓주소를 주는 경우이다.
• 해싱 충돌을 방지하기 위해서 버킷을 연결리스트로 구현하거나 개방주소법, 분리 연결법과 같은 방법을 사용한다.
• 해시테이블은 메모리를 고정시켜놓고 사용할 수 있다는 점, 검색을 빠르게 할 수 있다는 점에서 유리하다. 또한 키를 암호화 시켜 저장할 수 있다.

노드와 선으로 연결시키는, 그래프(Graph) 자료구조

• 데이터를 담은 노드(node, vertex)와 노드간의 연결성을 나타내는 엣지(edge, arc)로 구성된 자료구조

• 노드간의 엣지는 방향성이 있을 수도 있고(비대칭성), 방향이 없을 수도 있다(대칭성).

• 다른 노드로 부터 오는 엣지의 개수를 우리는 in-degree, 진입차수라고 한다.

• 반대로 한 노드에서 다른 노드로 가는 엣지의 개수를 out-degree, 진출차수라고 한다.

• 트리구조와는 다르게 부모-자식 관계가 형성되지 않는 자료구조 이다.

• 현실에서는 지하철 노선도와 교차로가 얽힌 도로등이 그래프 자료구조 모습과 비슷하다.

• 그래프 자료구조 구현 방법 01 : 이차원 배열(행렬), 공간을 많이 차지(노드 ^ 2), 덜 복잡하다.
• 그래프 자료구조 구현 방법 02 : 인접 리스트(연결형), 공간을 덜 차지(노드 개수 + 엣지 개수), 구현이 조금 복잡하다.

나무를 뒤로 뒤짚은 듯한, 트리(Tree) 자료구조

• 노드간의 계층이 구분된 자료구조이다. 부모-자식-손자 관계가 형성된다.
• 최상위 노드(root)에서 더 이상 자식이 없는 노드(leaf)까지의 계층이 형성되어 있고, 각각의 계층간 거리를 depth라고 표현한다.

• 같은 depth(층)에 있는 노드들의 관계를 sibling이라고 한다.

• 사실상, 위에서 공부한 그래프 자료구조에서 ‘방향성이 있는 그래프 구조 === 트리’라고 부를 수 있을 것이다. 완전하게 동일한 개념은 아니지만, 트리는 그래프 중에서 방향성이 있는 자료구조라고 불릴 수 있다.
• 위의 말은 노드간 연결을 나타내는 엣지에 방향성이 있다는 말이다.

크고 작음을 구분하여 트리구조에 반영하는 BST, 이진 탐색 트리 자료구조

• 개별 노드가 최대 2개의 자식만 가질 수 있는 특수한 트리 자료구조
• 부모 노드의 값 보다 큰 값은 오른쪽으로, 작은 값은 왼쪽 노드로 분류시키는 재귀형 자료구조