백준 10866 (Deque)

▶ 10866문제 - 덱

 

▶덱(Deque)

- Deque은 Double-Ended Queue의 줄임말로 큐의 양쪽에 데이터 넣고 뺄 수 있는 형태의 자료구조를 말한다.

- 큐(Queue)와 스택(Stack)을 합쳐 놓은 형태라고 생각하면 됨.

- Deque 앞쪽으로 데이터 넣고 뒤에서 뺴면 - 큐(Queue)형식

- Deque 앞쪽에서 데이터 넣고 다시 앞에서 뺴면 스택(Stack)형식으로 사용할 수 있음.

- 이중 한쪽으로만 입력 가능하게 설정한 덱 : 스크롤(Scroll)

- 한쪽으로만 출력할수 있도록 설정한 덱 : 셸프(Shelf)

 

- 덱 생성

Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new ConcurrentLinkedDeque<>();
Deque<String> deque4 = new LinkedList<>();

 

- 덱에 값 넣기

deque.addFirst(); //Deque 앞쪽에 데이터 삽입, 용량 초과시 Exception
deque.offerFirst(); //Deque 앞쪽에 데이터 삽입 후 true, 용량 초과시 false

deque.addLast(); //Deque 뒤쪽에 데이터 삽입, 용량 초과 시 Exception
deque.add(); //addLast()와 동일
deque.offerLast();//Deque 뒤쪽에서 데이터 삽입 후 true, 용량 초과 시 false
deque.offer(); //offerLast()와 동일

deque.push(); //addFirst()와 동일
deque.pop(); //removeFirst()와 동일

 

-덱에 있는 값 제거

 

deque.removeFirst(); //Deque의 앞에서 제거, 비어있으면 예외
deque.remove();//removeFirst()와 동일
deque.poll(); //Deque의 앞에서 제거, 비어있으면 null리턴
deque.pollFirst(); //poll()과 동일

deque.removeLast();//Deque의 뒤에서 제거, 비어있으면 예외
deque.pollLast(); //Deque의 뒤에서 제거, 비어있으면 null리턴

 

- 덱에 있는 값 확인

deque.getFirst(); //첫번째 엘리먼트 확인, 비어있으면 예외
deque.peekFirst(); //첫번째 엘리먼트를 확인, 비어있으면 null리턴
deque.peek(); //peekFirst()와 동일

deque.getLast(); //마지막 엘리먼트 확인, 비어있으면 예외
deque.peekLast(); //마지막 엘리먼트 확인, 비어있으면 null리턴

deque.contain(Object o); //Object인자와 동일한 엘리먼트가 포함되어 있는지 확인
deque.size(); //deque에 들어있는 엘리먼트 개수

 

참고) https://hbase.tistory.com/128

[Java] Deque (덱/데크) 사용법 및 예제

 

▶ 풀이방법

- Stack문제( https://shinny.tistory.com/136 ) Queue문제( https://shinny.tistory.com/139 )와 비슷

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int count = Integer.parseInt(br.readLine());
		Deque<Integer> deq = new ArrayDeque<>();
		
		for(int i = 0; i < count; 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.add(Integer.parseInt(st.nextToken()));
				break;
			case "pop_front":
				if(deq.isEmpty()) bw.write("-1\n");
				else bw.write(deq.remove() + "\n");
				break;
			case "pop_back":
				if(deq.isEmpty()) bw.write("-1\n");
				else bw.write(deq.removeLast() + "\n");
				break;
			case "size":
				bw.write(deq.size() + "\n");
				break;
			case "empty":
				if(deq.isEmpty()) bw.write("1\n");
				else bw.write("0\n");
				break;
			case "front":
				if(deq.isEmpty()) bw.write("-1\n");
				else bw.write(deq.peek() + "\n");
				break;
			case "back":
				if(deq.isEmpty()) bw.write("-1\n");
				else bw.write(deq.peekLast() + "\n");
				break;
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}