[자료구조] 스택, 큐, 트리, 힙

스택

• 모든 원소들의 삽입과 삭제가 한쪽 끝에서만 이루어진다.
• 한쪽 끝에서 이루어지기에 가장 마지막에 입력된 원소가 가장 처음으로 제거된다.
• 즉, 후입선출 (LIFO, Last In First Out)이 이루어진다.
• 웹사이트 방문기록, 실행 취소, 함수 호출 등, 가장 마지막에 실행한 것을 가장 처음으로 가져와야 할 때 사용된다.

 

 

큐

• 한 쪽 끝에서는 삭제가, 다른 한 쪽에서는 삽입이 일어난다.
• 즉 삭제와 삽입이 되는 구간이 다르기 때문에 가장 먼저 삽입된 원소가 가장 처음 제거된다.
• 즉, 선입선출 (FIFO, First In First Out)이 이루어진다.
• 종류로는 선형 큐와 원형 큐가 있는데, 선형 큐는 정해진 사이즈의 끝에 도달하면 더 이상 추가가 불가능하지만 원형 큐는 가능하다.
• BFS 알고리즘, 대기 번호, 프린터의 출력 처리 등 순서가 중요할 때 사용된다.

 

 

덱

• 삽입과 삭제가 양방향 모두에서 이루어진다.
• 양 끝에서의 데이터의 삽입과 삭제가 빠르지만 중간에서의 삽입과 삭제가 어렵다.
• 그래서 앞, 뒤에서만 삽입과 삭제가 일어날 때 자주 사용된다.

 

 

트리

• 계층적인 자료구조
• 하나의 노드에서 자식 노드로 가지가 뻗어나가는 계층구조이다.
• 이진트리, 완전 이진트리, 사향 이진트리, 포화 이진트리 등으로 구성된다.

 

 

힙

• 완전 이진트리의 일종이다.
• 최대 힙과 최소 힙으로 나눌 수 있는데, 최대 힙은 부모의 값이 반드시 자식보다 커야 하며, 최소 힙은 작아야 한다.
• 각 힙은 모두 최대값과 최소값을 잘 찾기 위해 사용된다.
• 우선순위를 정할 때 사용할 수도 있다.