[백준] 10866번 : 덱

문제

스택, 큐 문제와 마찬가지로 덱을 구현하는 문제로

양 끝에서 모두 추가/삭제가 가능한 자료구조를 구현해야 한다.

 

접근 방식

이번에도 배열을 이용해서 구현할 것이기 때문에

배열의 크기를 지정해줘야 한다.

 

주어진 입력의 크기가 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;
		}
	}
}