스택과 큐, 우선순위 큐, 힙

스택

스택(stack)은 삽입과 삭제 연산이 후입 선출(LIFO：Last-in First-out)로 이뤄지는 자료구조이다.

스택 용어

위치

• top： 삽입과 삭제가 일어나는 위치를 뜻한다.

연산

• push： top 위치에 새로운 데이터를 삽입하는 연산이다.
• pop： top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
• peek： top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

스택은 깊이 우선 탐색(DFS, Depth First Search), 백트래킹 종류의 코딩 테스트에 사용

예제

백준17298번

큐

큐(queue)는 삽입과 삭제 연산이 선입 선출(FIFO ： First-in First-out)로 이뤄지는 자료구조이다.

큐 용어

위치

• rear： 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front： 큐에서 가장 앞의 데이터를 가리키는 영역이다.

연산

• add： rear 부분에 새로운 데이터를 삽입하는 연산이다.
• poll： front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• peek： 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.

큐는 너비 우선 탐색(BFS, Breadth First Search)에서 자주 사용

예제

백준 2164번

힙

완전 이진 트리
부모의 값은 항상 자식(들)의 값보다 크거나(Max heap 최대 힙), 작아야(Min heap 최소 힙)한다. 루트노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹은 최솟값)을 O(1)안에 찾을 수 있다. 데이터의 삽입과 삭제는 모두 O(logN)이 소요된다.

데이터 삽입

1. 가장 끝의 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 서로 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. (부모노드는 삽입된 위치의 인덱스 번호에서 /2)
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

데이터 삭제

1. 최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.
2. 루트 노드를 제거한다.
3. 루트 자리에 가장 마지막 노드를 삽입한다.
4. 올라간 노드와 그의 자식 노드(들)와 비교한다.
5. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

배열 표현

인덱스 i위치에서 부모노드는 i/2 왼쪽 자식은 2i 오른쪽 자식은 2i + 1 위치에 있다.

우선순위 큐

우선순위 힙으로 구현한다.

PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
// 높은 숫자 순으로 우선순위 결정
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());	
add(), offer() //추가
poll(), remove() //제거
remove(int index) //index값 제거
clear() //모든 값 삭제
size() //크기
peek() //최고우선순위 값 확인

예제

절댓값 힙