📢 스택과 큐
01. 스택
: 삽입과 삭제 연산이 후입선출 LIFO
: 삽입과 삭제가 한쪽에서만 발생
- top : 삽입 삭제가 일어나는 위치
- push : 새로운 데이터 삽입
- pop : 데이터 삭제하고 확인
- peek : top 위치에 있는 데이터 확인
2. 큐
: 삽입과 삭제 연산이 선입선출 FIFO
: 삽입 삭제가 양방향에서 발생
- rear : 큐에서 가장 끝 데이터를 가리키는 영역
- front : 큐에서 가장 앞의 데이터를 가리키는 영역
- add : rear 부분에 새로운 데이터 삽입
- poll : front 부분에 데이터 삭제하고 확인
- peek : front 부분에 있는 데이터 확인
문제1. 백준 1874번 스택으로 오름차순 수열 만들기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // 수열의 개수
Stack<Integer> arr = new Stack<Integer>(); // 스택
int num = 1; // 스택에 추가할 수
boolean result = true; // 결과값
StringBuffer bf = new StringBuffer(); // 콘솔창 입력
for(int i = 0; i < n; i++) {
int target = Integer.parseInt(br.readLine()); // 입력받은 수
if(target >= num) { // 예. target = 4 num = 1
while (target >= num) {
arr.push(num++);
bf.append("+\n");
}
arr.pop(); // target = num일 때 실행
bf.append("-\n");
} else { // target = 3이고 num이 5
int num2 = arr.pop();
if(num2 > target) {
System.out.println("NO");
result = false;
break;
} else {
bf.append("-\n");
}
}
}
if(result) System.out.println(bf.toString());
}
}
StringBuffer 사용하는 이유 결과를 나중에 한꺼번에 출력하려고 그럼
문제2. 백준 17298번 오큰수 구하기
package part1;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;
public class stackQueue2 {
public static void main(String[] args) throws IOException {
/* 백준 17298번 오큰수 구하기 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine()); // 크기
// 1) 변수 정의
StringTokenizer line = new StringTokenizer(br.readLine());
int [] arr = new int[size]; // 입력받은 수 배열
int [] ans = new int[size]; // 정답 배열
for(int i = 0; i < size; i++) {
arr[i] = Integer.parseInt(line.nextToken());
}
Stack<Integer> stack = new Stack<Integer>();
stack.push(0); // 비교를 위한 초기화
// 2) 오큰수 판별
for(int i = 1; i < size; i++) {
// 만약, arr[2] = 3이면 스택에 1과 2가 존재
// arr[3] = 8이 되었을 때, ans[1, 2] = arr[8]이 된다.
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) { // arr[0] = 3 arr[1] = 5 오큰수일 때, 정답 배열에 넣기
ans[stack.pop()] = arr[i]; // 0이 pop되고, ans[0]= 5가 됨
}
stack.push(i);
}
// 3) -1 처리하기
while(!stack.empty()) { // 반복문 다 돌고 stack이 빌 때까지 -1 넣기
ans[stack.pop()] = -1;
}
// 4) 출력하기
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < size; i++) {
bw.write(ans[i] + " ");
}
bw.flush();
}
}
인덱스를 스택에 저장하는 거 어케 생각하지 .. ? 대단하다
문제 3. 백준 2164번 카드게임
🔎 접근법
- 큐를 사용한다!
삭제는 poll() 추가는 add()
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
/* 백준 2164번 카드게임 */
Scanner sc = new Scanner(System.in);
Queue<Integer> q = new LinkedList<>();
// 1. 변수 선정 및 초기화
int num = sc.nextInt();
for(int i = 1; i <= num; i++) {
q.add(i);
}
// 2. 한장 남을때까지 반복
while(q.size() > 1) {
q.poll(); // 첫장 버리기
q.add(q.poll()); // 버린 거 다시 아래에 넣기
}
// 3. 한장 출력
System.out.println(q.poll());
}
}
문제 4. 백준 11286번 절대값 힙 구하기
🔎 접근법
-
들어온 순서에 상관없이 크기가 작으면 삭제할 수 있어야함 -> 우선순위 큐 ( 저장 시 오름차순 정렬)
-
절댓값 힙
: 정수 x 넣는다 ( x != 0)
: 배열에서 절댓값 가장 작은 수 출력 후 제거
: 값이 같을 경우 그중 가장 작은 수 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) throws IOException {
/* 백준 11286번 절댓값 힙 구하기 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine());
PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if (first_abs == second_abs) {
/* [1과 -1의 의미]
* 1은 뒤로 가야 함
* -1은 앞으로 가야 함 */
return o1 > o2 ? 1 : -1;
} else {
return first_abs - second_abs;
}
});
for(int i = 0; i < size; i++) {
int n = Integer.parseInt(br.readLine());
if(n == 0) { // 제거
if(q.isEmpty()) {
System.out.println("0");
} else {
System.out.println(q.poll());
}
} else { // 추가
q.add(n);
}
}
}
}
~*