[자료구조] Queue와 Stack 그리고 Heap

스택(Stack)과 큐(Queue)가 무엇인지,

더 나아가 덱(Deque) 그리고 우선순위 큐(Priority Queue)와 힙(Heap)에 대해서 알아보자.

스택 (Stack)

• 후입선출(Last In First Out)의 자료구조
• 가장 나중에 삽입된 데이터가 먼저 삭제된다.
• Linked List를 이용하여 구현하면 쉽다.
• 가장 위에 있는 데이터가 위치한 곳을 Top이라고 한다.
• Top을 통해 데이터를 삽입하는 연산을 push , 삭제하는 연산을 pop이라고 한다.

큐 (Queue)

• 선입선출(First In First Out)의 자료구조
• 먼저 삽입된 데이터가 먼저 삭제된다.
• Linked List를 이용하여 구현하면 쉽다.
• 삭제연산이 수행되는 곳을 Front, 삽입연산이 이루어지는 곳을 Rear 또는 Back 이라고 한다.
• Rear에서 이루어지는 삽입연산을 인큐(Enqueue)
• 프론트에서 이루어지는 삭제연산을 디큐(Dequeue)라고 부른다.

덱 (Deque)

일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 데 비해,

덱(Deque)는 양쪽에서 모두 삽입과 삭제가 가능한 스택과 큐의 특징을 모두 갖고 있다.

양쪽으로 삽입, 삭제가 이루어지기 때문에 이중연결리스트로 구현하면 구현이 쉽다.

 

우선순위 큐(Priority Queue)

큐에 우선순위의 개념이 들어간 자료구조이다. 각각의 데이터들이 우선순위를 가진다.

큐는 먼저 삽입된 데이터가 먼저 삭제 됐다면,

우선순위 큐는 데이터 삽입시 우선순위에 따라 데이터가 정렬되며

삭제시에는 높은 우선순위를 가진 데이터가 먼저 삭제 된다.

우선순위에 따른 정렬이 필요하기 때문에 큐나 스택처럼 선형(Linear) 자료구조를 이용하면 좋은 성능은 기대할 수 없다.

따라서 우선순위 큐의 데이터의 삽입과 삭제는 자료구조 힙(Heap)을 이용하여 구현할 수 있으며

데이터의 삽입과 삭제 모두 $log_{2}N$의 시간복잡도를 가진다.

힙 (Heap)

• 힙(heap)은 무엇인가를 차곡차곡 쌓아올린 더미라는 뜻을 지니고 있다.
• 항상 완전 이진 트리의 형태를 가진다.
• 힙의 종류로 Max heap: 최대 힙과 Min heap: 최소 힙이 있다.

• 데이터의 삽입과 삭제 모두 $log_{2}N$의 시간복잡도를 가진다.

 

데이터 삽입

1. 데이터 삽입시, 완전 이진 트리의 마지막 노드 다음 위치에 새로 삽입할 데이터를 추가한다.
2. 최대힙 또는 최소힙 기준에 따라, 부모노드와 비교하여 노드 위치를 스왑한다.
3. 변경할 필요가 없을때까지 반복한다.

• 해당 연산은 $log_{2}N$의 시간복잡도를 가진다.

 

데이터 삭제

1. 루트노드를 삭제한다.
2. 완전 이진 트리의 마지막 노드를 루트노드 위치로 삽입한다.
3. 최대힙 또는 최소힙 기준에 따라, 자식노드와 비교하여 노드 위치를 스왑한다.
   이때, 최대힙 최소힙에 따라 더 크거나 더 작은 자식노드와 스왑한다.
4. 변경할 필요가 없을때까지 반복한다.

• 해당 연산은 $log_{2}N$의 시간복잡도를 가진다.

힙의 구현

• 완전 이진 트리를 사용하므로 배열로 트리를 구현하면 메모리의 큰 낭비 없이 힙을 쉽게 구현할 수 있다.
• 아래의 그림과 같이 부모노드의 인덱스가 $n$일때 왼쪽 자식노드의 인덱스는 $n * 2$,
  오른쪽 자식노드의 인덱스는 $n * 2 +1$ 로 간단하게 계산할 수 있다.

 

References

• 나무위키 - 큐 (자료구조)
• 나무위키 - 힙 트리