728x90
문제
스택, 큐 문제와 마찬가지로 덱을 구현하는 문제로
양 끝에서 모두 추가/삭제가 가능한 자료구조를 구현해야 한다.
접근 방식
이번에도 배열을 이용해서 구현할 것이기 때문에
배열의 크기를 지정해줘야 한다.
주어진 입력의 크기가 15라면
양쪽에서 최대 15개씩 총 30개의 값이 들어올 수가 있다.
그래서 배열의 크기는 주어진 입력의 크기 * 2 + 1을 해주면 충분하다.
기존 스택과 큐는 한쪽에서만 추가/삭제하는 메서드가 있었다면
메서드를 하나씩 추가해서 끝 부분에서도 추가/삭제가 가능하게 구현해 주면 된다.
풀이
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<Integer> deque = new Deque<>(n);
for (int i = 0; i < n; i++) {
String[] command = br.readLine().split(" ");
switch (command[0]) {
case "push_back": {
deque.pushBack(Integer.parseInt(command[1]));
break;
}
case "push_front": {
deque.pushFront(Integer.parseInt(command[1]));
break;
}
case "pop_back": {
sb.append(deque.popBack()).append("\n");
break;
}
case "pop_front": {
sb.append(deque.popFront()).append("\n");
break;
}
case "back": {
sb.append(deque.back()).append("\n");
break;
}
case "front": {
sb.append(deque.front()).append("\n");
break;
}
case "size": {
sb.append(deque.size()).append("\n");
break;
}
case "empty": {
sb.append(deque.empty()).append("\n");
break;
}
}
}
System.out.println(sb);
}
private static class Deque<T> {
private T[] dq;
private int front;
private int back;
public Deque(int size) {
this.dq = (T[]) new Object[size * 2 + 1];
this.front = size / 2;
this.back = size / 2 + 1;
}
public void pushFront(T x) {
dq[front--] = x;
}
public void pushBack(T x) {
dq[back++] = x;
}
public Object popFront() {
return empty() == 0 ? dq[++front] : -1;
}
public Object popBack() {
return empty() == 0 ? dq[--back] : -1;
}
public int size() {
return back - front - 1;
}
public int empty() {
return size() == 0 ? 1 : 0;
}
public Object front() {
return empty() == 0 ? dq[front + 1] : -1;
}
public Object back() {
return empty() == 0 ? dq[back - 1] : -1;
}
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 5430번 : AC (1) | 2023.10.04 |
---|---|
[백준] 1021번 : 회전하는 큐 (0) | 2023.10.04 |
[백준] 2164번 : 카드2 (0) | 2023.10.03 |
[백준] 10845번 : 큐 (0) | 2023.10.03 |
[백준] 2493번 : 탑 (0) | 2023.10.03 |