[면접 준비 - Algorithm]Stack, Queue, Tree, Graph

목차

 

Stack

 

Stack은 더미, 쌓다 등의 의미를 지니고 있다.

 

하나의 입출력 방향만을 가진 구조에 데이터를 넣는 것으로 생각할 수 있는데,

 

때문에 가장 큰 특징은 후입 선출 구조라는 점이다.

 

추가로 데이터를 한 번에 하나씩만 넣고 뺄 수 있다는 특성도 존재한다.

 

주로 브라우저의 앞으로 가기나 뒤로 가기, 실행 취소(컨트롤+z), 혹은 함수의 호출이나 재귀 함수 역시 스택에 기반을 두고 있다.

 

보통 고정된 크기를 가지기 때문에 다 사용하면 넘치게 되며, 이를 스택 오버플로우라고 부른다.

 

Queue

 

이에 반해 큐는 입력과 출력의 방향이 따로 정해진, 선입선출 구조를 지니고 있다.

 

스택과의 공통점은 데이터를 한 번에 하나씩만 넣거나 뺄 수 있다는 점이 있으며

 

프린터의 출력 알고리즘 같은 작업/데이터의 순차적 실행을 구현할 때 쓰이며,

 

스레드나 프로세스 사이, 또는 네트워크를 통해 데이터를 주고받을 때 일시 저장 용도로 쓰인다.

 

응용으로는

 

• 원형 큐 - 말 그대로 원형으로 빈 공간을 채우는 큐
• 우선순위 큐 - 내부적 우선순위에 따라 입력 값을 정렬하는 큐
• 데크 - 양쪽에서 모두 입/출력이 가능한, 스택과 큐의 특징을 합친 형태

등이 있다.

 

Stack vs. Queue

 

	Stack	Queue
공통점	한 번에 하나의 입출력만 가능하다.
차이점	입출력 방향이 하나뿐이다. 후입선출 구조를 갖는다.	입출력 방향이 따로 정해져 있다. 선입선출 구조를 갖는다.

 

Tree

 

 

트리는 부모 노드 아래에 자식 노드가, 또 그 아래에 자식 노드가 연결되는 재귀적 형태의 자료구조이다.

 

또한 항상 단방향이며 순환하지 않는, 그래프의 특수한 형태이기도 하다.

 

자료구조에서는 자식 노드의 개수를 최대 두 개로 제한하는 이진트리가 자주 사용되며

 

완전 이진트리의 경우엔 배열로 변환하는 것이 편리하고 언제나 가능하다.

 

참고로 이진트리의 종류엔 아래와 같은 세 가지가 존재한다.

 

 

• 정 이진트리(Full Binary Tree) - 모든 트리의 자식은 0 또는 2개이다.
• 포화 이진트리(Perfect Binary Tree) - 모든 리프 노드의 높이가 같으며 리프 노드를 제외한 모든 노드는 2개의 자식을 갖는다.
                                                               추가로 모든 포화 이진트리는 정 이진트리이다.
• 완전 이진트리(Complete Binary Tree) - 모든 리프 노드의 높이가 최대 1 차이가 나며,
                                                                   위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채운 트리이다.
                                                                   포화 이진트리는 완전 이진트리의 부분집합이다.

이진트리의 순회 방법과 이진 탐색 트리, 힙 트리 등에 대해서는 글을 분리한다.

 

Graph

 

그래프는 쉽게 말해 일반화된 트리이다.

 

방향성이 있을 수도, 없을 수도 있으며 순환할 수도, 그렇지 않을 수도 있다.

 

루트 또한 있을 수도 있고 없을 수도 있는 네트워크 모델의 형태를 가지며, 순회 방식도 더 일반적이다.

 

순회 방식과 인접 행렬, 인접 리스트에 대해서는 글을 분리한다.