[CS] Stack&Queue&Heap

Stack

스택 (Stack)

스택은 데이터 구조 중 후입 선출(LIFO, Last-In-First-Out) 즉, 나중에 입력한 데이터가 먼저 나오는 데이터 구조이다. 삽입, 삭제 모두 맨 뒤 원소로만 이루어지기 때문에 연산이 간단하고 시간복잡도가 작다. 맨 뒤 원소만 접근이 가능하기 때문에 인덱스를 통한 접근이 불가능하다. C++에서는 주로 std::stack을 사용한다. 데이터의 순서를 보존하고 상위 요소 외에 접근을 제한하는 효과도 있다. 단일 리스트가 사실 스택의 특징과 동일하다.

[STL] 2. stack

응용

가장 최근 작업을 저장해야 할 때 사용된다. 괄호검사 알고리즘, 깊이우선탐색, 웹 페이지에서 이전페이지 기능 등에 사용된다.

Queue

큐 (Queue)

큐는 선입선출(First In First Out) 즉, 가장 먼저 삽입된 데이터가 먼저 출력된다. 스택과 다르게 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어진다. 삽입은 큐(Enqueue), 삭제는 디큐(Dequeue)라고 부른다. C++에서는 std::queue를 사용한다.

[STL] 3. queue

우선순위 큐 (Priority Queue)

큐에 우선순위라는 개념을 접목시킨 자료구조이다. 즉, 힙 자료구조에 정렬 기준을 더하면 우선순위 큐가 되는데, 최소힙, 최대힙이 우선순위 큐에 해당한다. 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나간다.

응용

순차적인 작업 수행이 필요할 때 사용된다. 운영체제의 작업 스케줄링, 프린터의 스풀러, 너비우선탐색 등에 사용된다.

Heap

힙 (Heap)

힙 자료구조는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 형제 노드간 대소 관계를 따지지 않고, 우선순위가 큰 값이 부모, 작은 값이 자식이 되는 반 정렬 상태다. 힙의 인덱스는 위에서 아래로, 왼쪽에서 오른쪽으로 이어진다. 삽입과 삭제 모두 O(logN) 시간 복잡도로, 최댓값 또는 최솟값을 빠르게 가져올 때 유용하다. C++에서는 힙 자체를 쓰기 보단, 주로 std::priority_queue를 사용한다.

[STL] 7. priority_queue

종류

내림차순인 최대힙과, 오름차순인 최소힙이 있다. 힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 가지고 구현한다. 힙에서의 우선순위를 비교하는 것을 heapify 라고 한다.

응용

우선순위 큐, 힙 정렬 알고리즘, 최단 경로 알고리즘 등에 사용된다.