| Stack | Queue | Deque | PriorityQueue | |
| 구조 | LIFO(LastInFirstOut) | FIFO(FirstInFirstOut) | FIFO(FirstInFirstOut) | FIFO(FirstInFirstOut) |
| 활용 | DFS | BFS | 최소/최대 값의 삽입, 삭제 작업이 잦을 때 | - |
| 입력 | push(obj) | add(obj) / offer(obj) |
앞쪽에 - 뒤쪽에 addFirst(obj) - addLast(obj) |
add(obj) / offer(obj) |
| 출력 | peek(); | element() / peek() | 앞쪽에서 - 뒤쪽에서 peekFirst() - peekLast(); |
element() / poll() |
| 출력 & 제거 | pop(); | remove() / poll() | 앞쪽에서 - 뒤쪽에서 removeFirst() - removeLast() / pollFirst() - pollLast() |
remove() / peak() |
| 원소 없을 때 | Exception 발생 | null 반환 / Exception 발생 | null 반환 / Exception 발생 | null 반환 / Exception 발생 |
1. Stack
1) 기본 사용법
import java.util.*;
public class Exam {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
while(!stack.isEmpty()){
System.out.print(stack.pop()+ " ");
}
}
}
// 출력
// 5 4 3 2 1 마지막에 push한 것이 가장 먼저 출력 되는 것을 볼 수 있다.
2. Queue
1) 기본 사용법
import java.util.*;
public class Exam {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(1);
q.add(2);
q.add(3);
q.add(4);
q.add(5);
q.add(6);
while(!q.isEmpty()){
System.out.print(q.poll()+" ");
}
}
}
// 출력
// 1 2 3 4 5 6 가장 먼저 add(enqueue) 한것이 가장 먼저 출력되는 것을 볼 수 있다.
3. Deque
1) 기본 사용법
import java.util.*;
public class Exam {
public static void main(String[] args) {
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1);
dq.addFirst(2);
dq.addFirst(3);
dq.addFirst(4);
dq.addLast(5);
dq.addLast(6);
dq.addLast(7);
for (Integer d : dq) {
System.out.print(d+ " ");
}
System.out.println();
dq.pollFirst(); // poll을 이용해 앞쪽에서 제거
for (Integer d : dq) {
System.out.print(d+ " ");
}
System.out.println();
dq.pollLast(); // poll을 이용해 뒤쪽에서 제거
for (Integer d : dq) {
System.out.print(d+ " ");
}
System.out.println();
dq.removeFirst(); // remove를 이용해 앞쪽에서 제거
for (Integer d : dq) {
System.out.print(d+ " ");
}
System.out.println();
dq.removeLast(); // remove를 이용해 뒤쪽에서 제거
for (Integer d : dq) {
System.out.print(d+ " ");
}
}
}
// 4 3 2 1 5 6 7
// 3 2 1 5 6 7
// 3 2 1 5 6
// 3 2 1 5
// 3 2 11을 기준으로 보면 addFirst를 통해 Deque에 넣으면 앞쪽으로 addLast를 통해 Deque에 넣으면 뒷쪽으로 입력되는 것을 볼 수 있다.
Deque에서 객체를 빼낼 때도 마찬가지로 remove, poll을 이용하여 앞쪽과 뒷쪽 중에 원하는 쪽에서 원소를 뺄 수 있다.
4. PriorityQueue
1) 기본 사용법
import java.util.*;
public class Exam {
public static void main(String[] args) {
// 최소힙(기본값)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 최대힙(Collections.reverseOrder()로 지정)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap.add(4);
minHeap.add(5);
minHeap.add(1);
minHeap.add(6);
minHeap.add(8);
maxHeap.add(4);
maxHeap.add(5);
maxHeap.add(1);
maxHeap.add(6);
maxHeap.add(8);
for (Integer integer : minHeap) {
System.out.print( integer+ " ");
}
System.out.println();
for (Integer integer : maxHeap) {
System.out.print( integer+ " ");
}
System.out.println();
System.out.println();
while(!minHeap.isEmpty()){
System.out.print(minHeap.poll()+ " ");
}
System.out.println();
while(!maxHeap.isEmpty()){
System.out.print(maxHeap.poll()+ " ");
}
}
}
// 1 5 4 6 8
// 8 6 1 4 5
// 1 4 5 6 8
// 8 6 5 4 1처음 원소들을 foreach문을 통해 단순 출력 했을 때는 Heap구조에 따라 원소들이 나열 된 것을 볼 수 있다.
두번째 poll을 통해 원소를 출력&제거를 할 때는 최소힙인 minHeap은 최소값 부터 최대힙인 maxHeap은 최대값부터 출력하는 것을 볼 수 있다.
2) 커스텀
가끔 단순한 minHeap, maxHeap과 같이 오른차순, 내림차순으로 우선순위를 정할 수 없을 때가 있다. 이때 Comparater를 활용하여 우선순위를 직접 설정해 주면 된다.
import java.util.*;
public class Exam {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b) {
int compareA = a>0?a:-a;
int compareB = b>0?b:-b;
if(compareA==compareB) return 0;
return compareA<compareB ? -1:1;
// -1,0 => 자리를 바꾼다 => a가 앞에 앞에 온다.
// 1 => 자리를 바꾸지 않는다 => b가 앞에 온다.
}
});
pq.add(1);
pq.add(3);
pq.add(7);
pq.add(-4);
pq.add(-5);
pq.add(-6);
Object obj=null;
while((obj=pq.poll())!=null){
System.out.print(obj+" ");
}
}
}
// 출력
// 1 3 -4 -5 -6 7 위의 예제는 절대값이 작은 대로 정렬한 것을 바탕으로 priorityqueue를 작성한 것이다. Comparator를 이용하여 익명클래스를 만들어 compare를 오버라이드 하여 비교하면 간편하게 비교 할 수 있다.
※ 클래스를 만들어서 Comparable을 implements하여 compareTo를 오버라이드 해도 비교할 수 있지만 위의 방법이 더 간단한 것 같다.
댓글