[자료구조] 스택(Stack), 큐(Queue), 힙(Heap)

 

자료구조란 데이터를 효율적으로 저장하고 관리할 수 있도록 하는 구조를 말한다. 자료구조를 공부하다보면 특히 스택(Stack), 큐(Queue), 힙(Heap)에 대해 많이 얘기를 듣게 된다. 그만큼 활용도가 높고 많이 사용되기 때문이다. 하나씩 알아보도록 하자.

 

1. 스택(Stack)
스택은 "LIFO (Last In, First Out): 후입선출"의 원칙을 따르는 자료 구조로, 마지막에 들어간 데이터가 가장 먼저 나오는 특징을 가지고 있다.스택은 단어 뜻 그대로 쌓아진 물건을 생각하면 쉽다. 예를 들어 접시를 쌓아놓고 사용하면 맨 위에 있는 접시부터 꺼내서 사용하는 것을 생각하면 된다.

사용 예시: 웹 브라우저의 뒤로 가기 기능에서 스택이 사용될 수 있다. 사용자가 사이트를 방문할 때마다 해당 주소를 스택에 '푸시'(push)하여 저장한다. 이후 사용자가 뒤로 가기 버튼을 클릭하면 스택에서 가장 최근의 주소를 '팝'(pop)하여 꺼내 이전 주소의 페이지로 돌아가는 것이다.

2. 큐(Queue)
큐는 "FIFO (First In, First Out): 선입선출"의 원칙을 따르는 자료 구조로, 처음에 들어간 데이터가 가장 먼저 나오는 특징을 가지고 있다. 큐는 사람들이 줄을 서있는 것을 생각하면 쉽다. 줄을 설 때는 줄의 맨 뒤로 차례대로 서지만, 줄에서 나올 때는 맨 앞 사람부터 나오는 것을 생각하면 된다.

사용 예시: 프린터의 인쇄 대기열에서 큐를 사용할 수 있다. 여러 문서가 프린트될 때, 각 문서는 큐에 순서대로 들어가고, 프린터는 큐의 가장 앞에 있는 문서부터 차례로 인쇄하게 된다.

3. 힙(Heap)
힙은 특별한 종류의 완전 이진트리 기반 자료 구조이며, '최대 힙(max heap)'과 '최소 힙(min heap)' 두 가지 형태가 있다. 간단히 말해서 최대 힙은 이진트리의 최상위 노드에 가장 큰 수가 있고, 최소 힙은 반대로 가장 작은 수가 최상위 노드에 위치한 형태이다. 힙은 우선순위 큐(priority queue)의 구현에 주로 사용되며, 앞서 설명한 큐의 형태에서 우선순위의 개념을 더한 것으로 이해하면 쉽다.

사용 예시: 응급실에서 환자를 처리할 때 힙을 사용할 수 있다. 환자들이 각각 다른 우선순위를 가지고 있을 때, '최대 힙'을 사용하면 가장 높은 우선순위의 환자(가장 긴급한 상황)를 가장 먼저 처리할 수 있다. 각 환자의 도착 시간과 상태를 고려하여 우선순위를 결정하고, 힙을 통해 이를 효율적으로 관리할 수 있는 것이다.

각각의 사용 환경과 필요에 따라 자료구조를 활용할 수 있으며, 스택과 큐는 주로 일상적인 순차적 데이터 처리에 유용하고, 힙은 데이터의 우선순위에 따라 접근해야 할 때 효과적이다.