[JAVA] 백준 - 10828번, 10845번, 10866번 스택, 큐, 덱 (개념까지!)
안녕하세요. pitang입니다.
Stack, Queue, Deque 순서로 개념을 알아보고 문제까지 풀어보도록 하겠습니다.
스택, 큐, 덱은 데이터 값을 저장하는 기본적인 구조로 일차원의 선형 자료구조이다.
위의 그림들에 덧붙여 설명을 하자면
스택은 LIFO 후입 선출
큐는 FIFO 선입 선출
덱은 Stack + Queue 스택과 큐의 연산을 모두 지원하는 자료구조이다.
이 정도 알고 각각의 예제 문제들을 풀어보면 함수의 사용까지 확실히 알 수 있다.
10828번 Stack
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 작성하고 명령은 총 다섯 가지이다.
* push X : 정수 X를 스택에 넣는 연산이다.
* pop : 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
* size : 스택에 들어있는 정수의 개수를 출력한다.
* empty : 스택이 비어있으면 1, 아니면 0을 출력한다.
* top : 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력은 첫째 줄에 주어지는 명령의 수 N이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력은 출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
* ex)
14
push 1 2
push 2 2
top 0
size 2
empty 1
pop -1
pop 0
pop 1
size -1
empty 0
pop 3
push 3
empty
top
*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
// 자바에 있는 스택 쓰는 방법임! 기억해야함!
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < N; i++) {
String input = br.readLine();
StringTokenizer st = new StringTokenizer(input, " ");
// switch에다가 nextToken() 메서드를 넣어주고
switch(st.nextToken()) {
case "push":
// 여기서 st.nextToken() 해주면 숫자가 딱맞게 들어가게 됨.
// 나머지는 신경쓰지 않아도 됨.
stack.push(Integer.parseInt(st.nextToken()));
break;
case "pop":
if(!stack.empty()) sb.append(stack.pop()).append("\n");
else sb.append(-1).append("\n");
break;
case "size":
sb.append(stack.size()).append("\n");
break;
case "empty":
if(!stack.empty()) sb.append(0).append("\n");
else sb.append(1).append("\n");
break;
case "top":
// top 맨 위에 있는 것 꺼내는 명령어? 메서드? peek() 이다! 기억하기!
if(!stack.empty()) sb.append(stack.peek()).append("\n");
else sb.append(-1).append("\n");
break;
}
}
System.out.println(sb);
br.close();
}
}
10845번 Queue
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 작성하고 명령은 총 여섯 가지이다.
* push X : 정수 X를 큐에 넣는 연산이다.
* pop : 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
* size : 큐에 들어있는 정수의 개수를 출력한다.
* empty : 큐가 비어있으면 1, 아니면 0을 출력한다.
* front : 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
* back : 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력은 첫째 줄에 주어지는 명령의 수 N이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력은 출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
Queue<Integer> queue = new LinkedList<>();
int a = -1;
for(int i = 0; i < N; i++) {
String input = br.readLine();
StringTokenizer st = new StringTokenizer(input, " ");
switch(st.nextToken()) {
case "push" :
a = Integer.parseInt(st.nextToken());
queue.offer(a);
break;
case "pop" :
if(queue.isEmpty()) sb.append(-1).append("\n");
else sb.append(queue.poll()).append("\n");
break;
case "size" :
sb.append(queue.size()).append("\n");
break;
case "empty" :
if(queue.isEmpty()) sb.append(1).append("\n");
else sb.append(0).append("\n");
break;
case "front" :
if(queue.isEmpty()) sb.append(-1).append("\n");
else sb.append(queue.peek()).append("\n");
break;
case "back" :
if(queue.isEmpty()) sb.append(-1).append("\n");
else sb.append(a).append("\n");
break;
}
}
System.out.println(sb);
br.close();
}
}
10866번 Deque
정수를 저장하는 덱(Dequq)을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 작성하고 명령은 총 여덟 가지이다.
* push_front X : 정수 X를 덱의 앞에 넣는다.
* push_back X : 정수 X를 덱의 뒤에 넣는다.
* pop_front : 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
* pop_back : 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
* size : 덱에 들어있는 정수의 개수를 출력한다.
* empty : 덱이 비어있으면 1을, 아니면 0을 출력한다.
* front : 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
* back : 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력은 첫째 줄에 주어지는 명령의 수 N이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력은 출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
// deque
Deque<Integer> deq = new ArrayDeque<Integer>();
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String str = st.nextToken();
switch(str) {
case "push_front" :
deq.addFirst(Integer.parseInt(st.nextToken()));
break;
case "push_back" :
deq.addLast(Integer.parseInt(st.nextToken()));
break;
case "pop_front" :
if(deq.isEmpty()) sb.append(-1).append("\n");
else sb.append(deq.pollFirst()).append("\n");
break;
case "pop_back" :
if(deq.isEmpty()) sb.append(-1).append("\n");
else sb.append(deq.pollLast()).append("\n");
break;
case "size" :
sb.append(deq.size()).append("\n");
break;
case "empty" :
if(deq.isEmpty()) sb.append(1).append("\n");
else sb.append(0).append("\n");
break;
case "front" :
if(deq.isEmpty()) sb.append(-1).append("\n");
else sb.append(deq.peekFirst()).append("\n");
break;
case "back" :
if(deq.isEmpty()) sb.append(-1).append("\n");
else sb.append(deq.peekLast()).append("\n");
break;
}
}
System.out.println(sb);
br.close();
}
}
*m1 맥북을 사용 중입니다.*