스택, 큐, 힙, 트리

# 스택, 큐, 힙, 트리

# 스택(stack)

모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조(linear data structure)로서, 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다. 스택은 종종 pushdown stack이라고도 하는데, 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것(FILO, First In Last Out)을 pop이라 한다. 이와 같은 스택 연상은 항상 스택의 top에서 발생하므로 top 포인터의 값을 1씩 증가 또는 감소시킴으로써 수행된다.

# 큐(queue)

리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과는 달리 리스트의 한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화된 리스트. 가장 먼저 리스트에 삽입된 원소가 가장 먼저 삭제되므로 선입 선출(先入先出)인 FIFO(first in first out) 리스트라고 한다.

# 힙(heap)

컴퓨터의 기억 장소에서 그 일부분이 프로그램들에 할당되었다가 회수되는 작용이 되풀이되는 영역. 스택 영역은 엄격하게 후입 선출(LIFO) 방식으로 운영되는 데 비해 히프는 프로그램들이 요구하는 블록의 크기나 요구/횟수 순서가 일정한 규칙이 없다는 점이 다르다. 대개 히프의 기억 장소는 지시자(pointer) 변수를 통해 동적으로 할당받고 돌려준다. 이는 연결 목록이나 나무, 그래프 등의 동적인 자료 구조를 만드는 데 꼭 필요한 것이다.

# 트리(tree)

트리 회로. 나무가 하나의 뿌리(root)에서 줄기(trunk)가 나와 가지(branch)로 나누어지는 것처럼, 어떤 하나의 집합(레코드나 디렉토리 등)으로부터 하위 레벨(lower level)로 가지가 나오는 집합 관계를 갖는 계층 구조(hierarchic structure)를 말한다. 부분적으로도 결코 루트를 형성하는 경우는 없다. 따라서 처음에 가지가 나오기 시작되고 있는 집합으로부터 차례대로 「가지」를 더듬어가면 목적의 집합을 찾을 수 있다. 정보 처리 분야에는 이 같은 트리 구조(tree structure)를 가진 개념이 많이 있고, 이 트리 구조에는 순서 트리(ordered tree)나 2진 트리(binary tree) 등이 있다.