java.util
- 자바의 자료 구조를 담고 있는 패키지
- import java.util.*;
Stack(스택)
- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 구조
- 동적 배열, 단일 연결 리스트로 구현할 수 있음
push
Stack<Integer> stack = new Stack<>();
for (int i = 1; i < 5; i++) {
stack.push(i);
}
System.out.println(stack); // [1, 2, 3, 4, 5]
- 스택의 top 에 데이터를 추가
- 시간복잡도 : O(1)
pop
Stack<Integer> stack = new Stack<>();
for (int i = 1; i <= 5; i++) {
stack.push(i);
}
for (int i = 1; i <= 3; i++) {
stack.pop();
}
System.out.println(stack); // [1, 2]
- 스택의 top 에서 데이터를 제거하고 반환
- 시간복잡도 : O(1)
- 비어있는 스택에서 pop 메소드를 호출하면 EmptyStackException 발생
peek
Stack<Integer> stack = new Stack<>();
for (int i = 1; i <= 5; i++) {
stack.push(i);
}
System.out.println(stack.peek()); // 5
- 스택의 top 에서 데이터를 제거하지 않고 반환
- 시간복잡도 : O(1)
- 비어있는 스택에서 peek 메소드를 호출하면 EmptyStackException 발생
isEmpty
Stack<Integer> stack = new Stack<>();
System.out.println(stack.isEmpty()); // true
stack.push(10);
System.out.println(stack.isEmpty()); // false
- 스택이 비어있는 지 여부를 boolean 으로 반환
size
Stack<Integer> stack = new Stack<>();
for (int i = 1; i <= 5; i++) {
stack.push(i);
}
System.out.println(stack.size());
- 스택의 요소의 개수를 반환
활용
- Last In First Out 을 문제에 적용할 수 있는지를 판단
스택에서 가장 중요한 것은 이 문제를 스택으로 풀어야겠다는 생각을 떠올리는 것
Queue(큐)
- 한쪽 끝에서 자료를 추가하고 반대쪽 끝에서 자료를 꺼내는 FIFO(First In First Out) 형식의 구조
- 원형 배열, 단일 연결 리스트로 구현할 수 있음
- 자바에서 Queue 는 인터페이스이기 때문에 일반적으로 ArrayDeque 또는 LinkedList 로 구현하여 사용함
offer
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= 5; i++) {
queue.**offer**(i);
}
System.out.println(queue);
- 큐의 back 에 데이터를 추가
- 시간복잡도 : O(1)
- add 메소드는 데이터 추가 불가 시 예외를 던지지만, offer 메소드는 false 를 리턴함
poll
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= 5; i++) {
queue.offer(i);
}
for (int i = 1; i <= 3; i++) {
int p = queue.**poll**();
System.out.print(p + " "); // 1 2 3
}
System.out.println(queue); // [4, 5]
- 큐의 front 에서 데이터를 제거하고 반환
- 시간복잡도 : O(1)
- remove 메소드는 데이터 삭제 불가 시 예외를 던지지만, poll 메소드는 false 를 리턴함
peek
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= 5; i++) {
queue.offer(i);
}
System.out.println(queue.**peek**()); // 1
- 큐의 front 에서 데이터를 제거하지 않고 반환
- 시간복잡도 : O(1)
- element 메소드는 큐가 비어있으면 예외를 던지지만, peek 메소드는 null 을 리턴함
PriorityQueue(우선순위 큐)
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 5; i >= 1; i--) {
pq.offer(i);
System.out.println(pq);
}
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
- heap 자료구조 사용하여 구현됨
- 데이터가 들어온 순서대로 나가는 것이 아닌 우선순위가 높은 데이터가 먼저 나가는 구조
Max-heap(내림차순)
PriorityQueue<Integer> pq = new PriorityQueue<>(**Collections.reverseOrder()**);
for (int i = 5; i >= 1; i--) {
pq.offer(i);
System.out.println(pq);
}
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
- 우선 순위 큐의 디폴트 설정은 오름차순(min-heap, 작은 값이 우선 순위를 가짐)
- Collections.reverseOrder() 를 사용하여 내림차순(max-heap) 설정
시간 복잡도
- 주어진 input 의 개수 : N 개
- 우선순위 큐에 하나의 input 을 저장 or 삭제 : O(logN)
- 우선순위 큐를 이용한 정렬
- N 개의 input 을 모두 큐에 저장 한 뒤 하나씩 꺼내기만 해도 알아서 정렬이 진행됨
- N 개를 큐에 저장하는 시간 + N 개를 큐에서 빼는 시간 = 2 * N * logN = O(NlogN)
- 따라서 우선순위 큐를 이용한 정렬은 O(NlogN) 의 시간 복잡도를 가짐
정렬 기준 설정(Comparable, Comparator)
- 우선순위 큐에 저장할 객체는 2 가지 방법으로 우선 순위 조건을 설정할 수 있음
- Comparable 인터페이스를 구현해서 compareTo 메소드를 오버라이드
- Comparator 인터페이스를 구현해서 compare 메소드를 오버라이드
1. Comparable 인터페이스 활용
// 2차원 배열의 좌표를 저장하는 객체
class Pair implements Comparable<Pair>{
int r;
int c;
public Pair(int r, int c) {
this.r = r;
this.c = c;
}
// 2차원 배열에서 가장 위쪽에 있는 좌표를,
// 그러한 좌표가 많다면 가장 왼족에 있는 좌표를 먼저 큐에서 뽑아냄
**@Override
public int compareTo(Pair o) {
if (this.r != o.r) {
return this.r - o.r;
} else {
return this.c - o.c;
}
}**
}
2. Comparator 활용
// 방법 1
PriorityQueue<Pair> pq1 = new PriorityQueue<>(new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
if (o1.r != o2.r) {
return o1.r - o2.r;
} else {
return o1.c - o2.c;
}
}
});
// 방법 2
PriorityQueue<Pair> pq2 = new PriorityQueue<>((o1, o2) -> {
if (o1.r != o2.r) {
return o1.r - o2.r;
} else {
return o1.c - o2.c;
}
});
둘 중 편한 방법으로 사용!
활용
- 힙과 관련된 문제
- 특정 조건들이 우선 순위를 가지는 상황이 주어질 때
