Restricted Structure
•
정의) 스택, 큐, 덱을 묶어서 Restricted Structure라고 부름. 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있기 때문임.
스택
•
정의) 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조
•
특징)
◦
삽입과 삭제가 한 쪽에서만 일어남
◦
깊이 우선 탐색, 백트래킹에 효과적으로 쓰임
◦
후입선출의 개념 자체가 재귀 함수 알고리즘과 일맥상통함
•
용어)
◦
위치
▪
top : 삽입과 삭제가 일어나는 위치
◦
연산
▪
push : top 위치에 새로운 데이터 삽입
▪
pop : top 위치에 현재 있는 데이터를 삭제하고 확인
▪
peek : top 위치에 현재 있는 데이터를 단순 확인
•
시간복잡도)
◦
제일 앞에 원소 추가 : O(1)
◦
제일 앞의 원소 제거 : O(1)
◦
최상단 원소 확인 : O(1)
▪
최상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 (배열을 이용해 스택을 구현한다면 가능하게 만들 수는 있음)
큐
•
정의) 삽입과 삭제과 선입선출로 이뤄지는 자료구조
•
특징)
◦
너비 우선 탐색에서 자주 사용함
◦
삽입과 삭제가 양방향에서 일어남
•
용어)
◦
위치
▪
rear : 큐에서 가장 끝 데이터 가리키는 영역
▪
front : 큐에서 가장 앞의 데이터를 가리키는 영역
◦
연산
▪
add : rear 부분에 새로운 데이터를 삽입
▪
poll : front 부분에 있는 데이터를 삭제하고 확인
▪
peek : front 부분에 있는 데이터를 단순 확인
•
시간복잡도)
◦
제일 뒤에 원소 추가 : O(1)
◦
제일 앞에 원소 제거 : O(1)
◦
제일 앞/뒤의 원소 확인 : O(1)
▪
제일 앞/뒤가 아닌 원소들의 확인/변경은 원칙적으로 불가능 (배열을 이용해 큐를 구현한다면 가능하게 만들 수는 있음)
우선순위 큐
•
정의) 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
•
특징)
◦
연산 이름은 큐와 동일하지만, 내부 구조는 큐와 완전히 다름
◦
큐 설정에 따라 front에 항상 우선순위가 가장 높은 값이 위치함
▪
예를 들어 front에 항상 최소값이 위치하게 했다는 건,
작은 수가 더 높은 우선순위를 가지고
높은 우선순위를 가진 원소가 먼저 나오기에
작은 수가 먼저 나온단 의미임
◦
일반적으로 힙(완전 이진 트리 → 뒤 챕터에서 다룰 예정)을 이용해 구현함
▪
힙 구조 상 max 값이 최상단에 있는 건 확실하지만 데이터를 항상 정렬하고 있진 않음
따라서, 큐 내부를 출력해보면 데이터가 정렬되어 있진 않음
허나, poll을 몇 번을 하든 front에 max 값이 존재한다는 건 확실하게 보장됨
•
시간 복잡도)
◦
제일 뒤에 원소 추가 : O(logN)
◦
제일 앞에 원소 제거 : O(logN)
◦
제일 앞의 원소 확인 : O(logN)
•
조건 변경하는 법 1) ex. 최대값이 우선순위 높게 (내림차순 정렬로 변경. 기본은 오름차순 정렬)
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
JSON
복사
•
조건 변경하는 법 2) ex. 절대값 작은 게 우선순위 높게 + 절대값 같을 땐 음수가 우선순위 높게
1.
compare 함수를 오버라이딩
PriorityQueue<Integer> pq = new PriorityQueue<>(
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (Math.abs(o1) == Math.abs(o2)) {
return o1 > o2 ? 1 : -1; // 절대값 큰 수가 더 큰 수(낮은 우선순위)
} else {
return Math.abs(o1) > Math.abs(o2) ? 1 : -1; // 양수가 더 큰 수(낮은 우선순위)
}
}
}
);
JSON
복사
2.
람다 사용
PriorityQueue<Integer> pq = new PriorityQueue<>(
(o1, o2) -> {
if (Math.abs(o1) == Math.abs(o2)) {
return o1 > o2 ? 1 : -1;
} else {
return Math.abs(o1) > Math.abs(o2) ? 1 : -1;
}
}
);
JSON
복사
◦
조건 변경 결과 ex
▪
일반적인 pq.poll 시 나오는 순서 = [-2, -1, -1, -1, 1, 1, 1, 2]
▪
구현한 pq.poll 시 나오는 순서 = [-1, -1, -1, 1, 1, 1, -2, 2]
덱(deque, 데큐) in Java
•
정의) Double-ended Queue 의 줄임말로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
•
특징)
◦
자바에서 덱은 인터페이스로 구현되어 있음. 덱의 여러 연산을 정의한 Deque 인터페이스가 있고, 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있음
•
시간복잡도)
◦
제일 앞/뒤에 원소 추가 : O(1)
◦
제일 앞/뒤의 원소 제거 : O(1)
◦
제일 앞/뒤의 원소 확인 O(1)
▪
제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 (C++ STL deque에선 인덱스로 원소에 접근 가능)
참고