스택
- 삽입과 삭제 연산이 Last-in First-out로 이뤄지는 구조
- 삽입과 삭제가 "한 쪽"에서만 일어남
- Top: 삽입과 삭제가 일어나는 위치
- Push: top 위치에 새로운 데이터 삽입
- Pop: top 위치에 현재 있는 데이터 꺼냄
- Peek: top 위치에 현재 있는 데이터 확인
=> 스택은 깊이 우선 탐색(DFS)와 백트래킹 종류의 코딩 테스트에 효과적
큐
- 삽입과 삭제 연산이 First-in First-out
- 삽입과 삭제가 양방향에서 이루어짐
- Rear: 큐에서 가장 끝 데이터를 가리킴
- Front: 큐에서 가장 앞의 데이터를 가리킴
- Add: rear 부분에 새로운 데이터 삽입
- Poll: front 부분에 있는 데이터 꺼냄
- Peek: 큐의 front에 있는 데이터 확인
=> 큐는 너비 우선 탐색(BFS)에서 자주 사용함
실전! 문제 풀이(백준 1874)
import java.util.*;
class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int num = 1;
Stack<Integer> stack = new Stack<>();
StringBuffer bf = new StringBuffer();
boolean result = true;
for(int i=0; i<n ;i++){
arr[i]=sc.nextInt();
}
for(int i=0; i<n ;i++){
if(arr[i]>=num){
while(arr[i]>=num){
stack.push(num++);
bf.append("+\n");
}
stack.pop();
bf.append("-\n");
}else{
int popedNum= stack.pop();
if(popedNum>arr[i]){
System.out.println("NO");
result = false;
break;
}else{
bf.append("-\n");
}
}
}
if(result==true){
System.out.println(bf.toString());
}
}
}얻어갈 점:
- 처음에 문제를 해결하려할 때 int배열에 입력값만큼 1부터 1씩증가하는 값을 넣어 해결하려했는데, 배열은 중간 값을 꺼내고 빼는 것이 불편하기 때문에, 굳이 그렇게 하는 것보다는 int를 하나 선언하고 증감연산을 통해 풀이하는 것이 좋다!
실전! 문제 풀에(백준 2164)
import java.util.*;
class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Queue<Integer> queue = new LinkedList<>();
for(int i=0 ; i<n ; i++){
queue.add(i+1);
}
while(queue.size()>1){
queue.remove();
int polledData= queue.poll();
queue.add(polledData);
}
System.out.print(queue.poll());
}
}얻어갈 점:
- 왜 queue 자료 구조를 사용했는가? 문제에서 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이를 자칫 착각하면 스택구조로 풀이해야겠다라고 생각할 수 있지만 문제를 더 읽어보면(이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다) 한 쪽에서는 삭제를, 한 쪽에서는 삽입을 하는 것을 볼 때 스택이 아닌 큐 구조가 더 알맞다는 것을 알 수 있다!
- Queue는 인터페이스이기 때문에 구현체로 LinkedList 사용(다른 구현체도 있음)
- while(~)은 ~가 참일때 반복되는 구조 / ex) queue.size==1 (큐 사이즈가 1이 될때까지라고 생각하고 다음과 같이 입력하면 바로 false이기에 반복불가 => 큐 사이즈가 하나씩 줄어가다가 1이될 때 멈춰야 하기에 queue.size>1가 맞는 표현)
.