Stack
- LIFO
Stack<E> stack = new Stack<E>();
주요 메소드
push(E item): 주어진 객체를 스택에 넣기peek(): 스택의 맨 위 객체를 가져오기. 객체를 스택에서 제거하지 않음.pop(): 스택의 맨 위 객체를 가져오기. 객체를 스택에서 제거함.
Queue
- FIFO
Queue<E> queue = new LinkedList<E>();- Queue 인터페이스를 구현한 대표적인 클래스는 LinkedList다.
- LinkedList는 List 인터페이스를 구현했기 때문에 List 컬렉션이기도 하다.
주요 메소드
offer(E e): 주어진 객체를 넣기 (리턴 타입 : boolean)peek(): 객체 하나를 가져오기. 객체를 큐에서 제거하지 않음poll(): 객체 하나를 가져오기. 객체를 큐에서 제거함.
예시 코드
프로그래머스 코딩테스트 문제 중 ‘네트워크’ 문제 풀이할 때 나온 코드 -> 비선형 자료구조 탐색에 해당
선형 자료구조 탐색
선형이었다면, 이런 형태였을 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] visit = new boolean[n];
for (int i = 0; i < n; i++) {
// 방문기록 존재시 건너뛰기
if (visit[i]) {
continue;
}
// i번째에 연결된 모든 곳 찾아내기
for (int j = 0; j < n; j++) {
if (visit[j]) {
continue;
}
if (computers[i][j] == 1) {
visit[j] = true;
}
}
}
return answer;
}
}
비선형 자료구조 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
boolean[] visit = new boolean[n];
for (int i = 0; i < n; i++) {
// 방문기록 존재시 건너뛰기
if (visit[i]) {
continue;
}
answer++;
visitAll(n, computers, visit, i);
}
return answer;
}
void visitAll(int n, int[][] computer, boolean[] visit, int i) {
// BFS라서 앞에서부터 꺼내온다. (Queue)
// 만일 DFS였다면, 뒤에서부터 꺼내온다 (Stack)
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
while(!queue.isEmpty()) {
int c = queue.poll();
for (int j = 0; j < n; j++) {
if(visit[j]) {
continue;
}
if (computers[c][j] == 1) {
queue.offer(j);
visit[j] = true;
}
}
}
}
}
