* Stack
FILO 방식 (First In Last Out)
// Stack 선언
Stack<String> st = new Stack<String>();
push(x) : 해당 스택의 제일 상단에 전달된 요소를 삽입함.
pop() : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
size() : 해당 스택에 들어있는 정수의 개수를 출력함.
empty() : 해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
peek() : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
* Queue
FIFO 방식 (First In First Out)
// Queue 선언
Queue<String> q = new LinkedList<String>();
add(E e), offer(E e) : 해당 큐의 맨 뒤에 전달된 요소를 삽입함.
element() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
peek() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
poll() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함.
remove() : 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.
* 우선순위 Queue
Heap Sort 알고리즘 사용
// 우선순위 Queue 선언
PriorityQueue<Integer> pq = new PriorityQueue<>();
우선순위 큐에 저장될 때, Heap Sort의 방식을 거쳐 저장된다. O(nlogn)
Heap Sort는 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이다.
우선순위 큐는 큐에서 뺄 때, 우선순위 순서대로 가져온다.
Default 는 최소 힙(작은 값이 루트 노드)이다. 즉, 숫자가 작을 수록 우선순위가 높다.
우선순위를 변경하고 싶으면 Comparator 를 사용하면 된다.
pq.add 시에 자동으로 최소/최대 힙을 만족하도록 수정하여 저장되며 이때의 시간복잡도는 O(logN)이다.
1 2 3 4 5 6 7 8 9 | PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(1); pq.add(3); pq.add(2); pq.poll(); //1 pq.poll(); //2 pq.poll(); //3 | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 | PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return Integer.compare(o2, o1); //내림차순 } }); pq.add(1); pq.add(3); pq.add(2); pq.poll(); //3 pq.poll(); //2 pq.poll(); //1 | cs |
'∙Algorithm Tech' 카테고리의 다른 글
| [Algorithm Tech] Bitmask(비트마스크) (0) | 2019.01.08 |
|---|---|
| [Algorithm Tech] BackTracking (0) | 2019.01.03 |
| [Algorithm Tech] BFS vs DFS (0) | 2018.12.29 |
| [Algorithm Tech] 알고리즘 기본 지식 (0) | 2018.12.27 |