- Stack(스택)이란?
스택은 LIFO(Last In First Out) 구조의 자료형으로 한 쪽으로만 데이터를 넣고 뺄 수 있는 선형 구조로 되어있다. 즉, 마지막으로 넣은 데이터가 먼저 나오게 된다.
스택에서 삽입은 push, 삭제는 pop 명령어로 실행된다.
이는 브라우저에서 뒤로가기, 문서 작업 시 컨트롤+Z 같은 이전 상태로 되돌리기 등에 사용되며 DFS알고리즘에도 사용되는 자료형이다.
마지막 위치에 해당하는 데이터를 읽기 위해서는 Peek 명령어를 사용한다.
스택에 데이터가 꽉 차서 넣을 공간이 없는데 push를 하게 되는 경우를 overflow라고 하며 데이터가 없는데 pop을 하는 경우는 underflow라고 한다.
스택을 구현하는 방법은 배열을 사용하는 방법과 연결 리스트를 사용하는 방법이 있다.
배열을 사용하면 구현이 쉽고 인덱스를 사용하여 데이터의 접근 속도가 빠르다는 장점이 있다. 하지만 데이터의 최대 개수를 미리 정해야 하며 아래 그림처럼 데이터의 삽입과 삭제가 한 쪽으로만 이루어 지기 때문에 매우 비효율적이다.
연결 리스트를 사용하면 데이터의 최대 개수가 정해져 있지 않으며 데이터들이 순차적으로 나열되어 있기 때문에 데이터의 삽입과 삭제가 편하다.
아래 그림에서 연결 리스트를 구성하고 있는 요소들을 노드라고 하는데 이 노드가 데이터와 다음 위치에 해당하는 노드의 주소값을 가지기 때문에 연결 리스트 중간에 데이터를 삽입하기가 쉬운 것이다. 하지만 이런 구조 때문에 링크를 따라 하나씩 데이터를 찾아야 하기 때문에 배열처럼 한번에 원하는 데이터에 접근을 할 수 없다.
- Queue(큐)란?
큐는 스택과 반대 개념이다. FIFO(First In First Out) 구조의 자료형으로 선입선출, 대기열이라고도 한다.
먼저 들어간 데이터가 먼저 나오는 구조로 데이터가 들어오는 곳과 나가는 곳이 다르다.
데이터가 들어오는 위치는 가장 뒤에 있고 데이터가 나가는 위치는 가장 앞에 있어서 선입선출 구조가 된다. 때문에 가장 마지막에 들어온 데이터를 삭제하려면 앞에 있는 데이터들을 전부 삭제해야한다.
push 명령으로 데이터를 삽입하며 pop 명령으로 데이터를 뺀다.
데이터가 있는데 push를 하는 경우를 overflow라고 하며 가장 앞(데이터가 나가는 위치)에 데이터가 없는데 pop을 하는 경우는 underflow라고 한다.
큐는 들어온 순서를 보장해야하는 경우인 작업 대기, 대기줄, 프로세스 관리 등에 사용되며 BFS 알고리즘에도 사용된다.
큐는 우선순위 큐, 원형 큐 등의 변형이 존재하며 입력 동작을 Enqueue, 출력 동작은 Dequeue라고 한다.
+) 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다. 우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수 있다. 원형 큐는 선형 큐를 보완하기 위한 자료구조로 포인터 증가 방식이 변환되어 비열의 첫 인덱스부터 다시 데이터의 삽입이 가능하다.
큐를 구현할 때 보통 배열을 사용면 앞쪽은 채워지고 뒤쪽은 빠져나가 데이터가 앞으로 밀리는 문제가 생기기 때문에 원형 버퍼를 사용한다. 시작과 끝 부분을 포인터로 지정 후 Enqueue와 Dequeue를 하는 형태이다. 데이터가 가득 차 있을 땐 포인터가 같은 위치를 지정하기 때문에 한 공간을 비워놓아야 한다.
연결 리스트를 사용하면 배열보다 쉽게 구현이 가능하다.
- Heap(힙)이란?
힙은 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 하는 자료구조이다.
<A가 B의 부모 노드이면 A의 키 값과 B의 키 값 사이에는 대소 관계가 성립한다.> 라는 힙 속성을 만족한다.
힙은 가장 높거나 가장 낮은 우선순위를 가지는 노드가 항상 뿌리 노드에 있는 특징이 있다. 이를 응용해 우선순위 큐와 같은 추상적 자료형을 구현할 수도 있다.
위의 그림은 1부터 100까지 정수를 저장한 최대 힙의 예시이다. 모든 부모 노드들이 그 자식 노드들보다 큰 값을 가진다.
힙의 종류에는 최대 힙과 최소 힙이 있다.
최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙이며 최소 힙은 아래 그림과 같이 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙이다.
키 값의 대소 관계는 부모 노드와 자식 노드 간에만 성립하기 때문에 형제 사이에는 대소 관계가 정해지지 않는다.
각 노드의 자식 노드 최대 개수는 힙 종류에 따라 다른데, 대부분 자식 노드의 개수가 최대 2개인 이진 힙을 사용한다. 때문에 힙은 이진 힙이라고도 한다.
이진 힙은 내부 노드에 키와 요소를 저장한 이진 트리로 트리가 T, 내부 노드가 v라면 아래와 같은 특징을 갖는다.
1. 뿌리 노드를 제외한 각 내부 노드는 Key(T.parent(v)) < key(v)) 또는 key(T.parent(v)) > key(v)이다.
2. 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진트리를 형성한다.
