[자료구조/알고리즘] 기초

자료구조

• 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것

자료구조의 분류

• 주어진 데이터들과 상황에 효율적으로 사용가능한 자료구조 중 선형구조와 비선형구조 를 배웠다.
• 선형구조의 스택 큐 비선형구조의 트리 그래프는 알고리즘 테스트에서 가장 많이 쓰이는 자료구조이다.

---

Stack의 특징

1. LIFO (last in first out) 후입선출 : 가장 나중에 추가된 데이터가 먼저 배출된다.
2. 데이터를 하나씩 넣고 뺌 : 한꺼번에 여러 개를 넣거나 뺄 수 없습니다.
3. 하나의 입출력 방향을 가짐 : 입출력 방향이 여러개면 Stack 구조가 아니다.
4. 스택에 쌓이는 데이터는 유한하고 정적이여야 함 : 정적할당이란 변수선언을 통해 필요한 메모리를 할당하는 방법
5. 스택의 크기는 제한되어있다 (넘치면 stack overflow)

stack 사용예시

1. 브라우저의 뒤로 가기, 앞으로 가기 기능
2. 문서작업의 ctrl + z

---

Queue의 특징

1. FIFO (first in first out) 선입선출 : 가장 먼저 추가된 데이터가 먼저 추가된다.
2. 데이터를 하나씩 넣고 뺌 : 한꺼번에 여러 개를 넣거나 뺄 수 없습니다.
3. 두개의 입출력 방향을 가짐 : 데이터의 입력, 출력 방향이 다릅니다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없습니다.

queue 사용예시

1. 프린터기의 인쇄 대기열
2. 은행창구의 번호표 대기
3. 너비 우선 탐색 알고리즘 (BFS)

Tree의 특징

• 트리는 노드로 구성된 계층적 자료구조다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다.