스택: 먼저 넣게 되는 자료가 마지막으로 나오게 되는 First-In Last-Out(FILO) 구조이다. 데이터가 들어가고 나오는 입구가 하나뿐이므로 입구로 들어간 데이터가 스택에 차곡차곡 쌓여있다가 들어간 반대 순서로 나온다. 마지막에 들어간 원소가 처음에 나온다.
큐: 먼저 넣게 되는 자료가 가장 먼저 나오는 First-In First-Out(FIFO) 구조이다.
트리: 정점과 간선을 이용해 사이클을 이루지 않도록 구성한 Graph의 특수한 형태로, 계층이 있는 데이터를 표현하기에 적합하다.
힙: 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리이다.
[리스트/벡터 차이]
벡터는 메모리가 연속적으로 되어 있어 읽는 속도가 빠르지만 맨뒤를 제외한 모든 곳의 삽입삭제는 밀고 당기는 비용이 발생
리스트는 불연속적으로 나열되어 있어 읽는 속도는 벡터보다 느리지만 지점을 찾아 연결된 링크만 수정하면 되어 삽입삭제가 효율적입니다.
[ 버블소트, 셀렉소트, 머지소트, 퀵소트 ]
버블소트는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬합니다. 시간복잡도는 O(n2)입니다.
셀렉소트는 원소를 넣을 위치를 정해두고 어떤 원소를 넣을지 선택하는 알고리즘입니다. 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫번째에 놓고, 두번째 자료를 세번재 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두번재에 놓고 ... 이러한 과정을 반복하여 정렬을 수행한다. 시간복잡도는 O(n2)입니다.
[BST(Binary Search Tree)]
이진탐색트리는 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조로, 이진 트리이면서 같은 값을 갖는 노드가 없어야한다.
왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 크다. 즉, 정렬이 되어있어야 한다.