덱(Deque) 자료구조

덱 (Deque)

메소드

삽입

• addFirst() : 덱의 앞에 요소를 삽입한다. 전체 크기를 초과하면 예외가 발생한다.

• addLast() : 덱의 뒤에 요소를 삽입한다. 전체 크기를 초과하면 예외가 발생한다.

• offerFirst() : 덱의 앞에 요소를 삽입한다. 요소 삽입 성공 여부가 true/false로 반환된다.

• offerLast() : 덱의 뒤에 요소를 삽입한다. 요소 삽입 성공 여부가 true/false로 반환된다.

• add() : addLast()와 동일

삭제

• removeFirst() : 덱의 앞에서 요소 하나를 제거하고, 해당 요소를 반환한다. 덱이 비어있는 경우 예외가 발생한다.

• removeLast() : 덱의 뒤에서 요소 하나를 제거하고, 해당 요소를 반환한다. 덱이 비어있는 경우 예외가 발생한다.

• pollFirst() : 덱의 앞에서 요소 하나를 제거하고, 해당 요소를 반환한다. 덱이 비어있는 경우 null이 반환된다.

• pollLast() : 덱의 뒤에서 요소 하나를 제거하고, 해당 요소를 반환한다. 덱이 비어있는 경우 null이 반환된다.

• remove() : removeFirst()와 동일

• poll() : pollFirst()와 동일

값 확인

• getFirst() : 덱의 앞에서 요소 하나의 값을 반환한다(제거 X). 덱이 비어있는 경우 예외가 발생한다.

• getLast() : 덱의 뒤에서 요소 하나의 값을 반환한다(제거 X). 덱이 비어있는 경우 예외가 발생한다.

• peekFirst() : 덱의 앞에서 요소 하나의 값을 반환한다(제거 X). 덱이 비어있는 경우 null이 반환된다.

• peekLast() : 덱의 뒤에서 요소 하나의 값을 반환한다(제거 X). 덱이 비어있는 경우 null이 반환된다.

• peek() : peekFirst()와 동일

기타

• removeFirstOccurrence(Object o) : 덱의 앞에서부터 탐색하여 Object o와 동일한 첫 요소를 제거한다.

• removeLastOccurrence(Object o) : 덱의 뒤에서부터 탐색하여 입력한 Object o와 동일한 첫 요소를 제거한다.

• push() : addFirst()와 동일.

• pop() : removeFirst()와 동일.

• remove(Object o) : removeFirstOccurrence(Object o)와 동일.

• contain(Object o) : 덱에 Object o와 동일한 요소가 포함되어 있는지 여부를 반환한다.

• size() : 덱에 들어있는 요소의 개수를 반환한다.

• isEmpty() : 덱이 비어있는 지 여부 반환한다.

사용

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

백준 #10866번 : 덱

문제

• push_front X: 정수 X를 덱의 앞에 넣는다.

• push_back X: 정수 X를 덱의 뒤에 넣는다.

• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 덱에 들어있는 정수의 개수를 출력한다.

• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.

• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

출력

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Deque<Integer> deque = new ArrayDeque<>();

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command) {
                case "push_front":
                    int xF = Integer.parseInt(st.nextToken());
                    deque.addFirst(xF);
                    break;
                case "push_back":
                    int xB = Integer.parseInt(st.nextToken());
                    deque.addLast(xB);
                    break;
                case "pop_front":
                    Integer pF = deque.pollFirst();
                    if(pF == null) pF = -1;
                    sb.append(pF).append("\n");
                    break;
                case "pop_back":
                    Integer pB = deque.pollLast();
                    if(pB == null) pB = -1;
                    sb.append(pB).append("\n");
                    break;
                case "size":
                    sb.append(deque.size()).append("\n");
                    break;
                case "empty":
                    if(deque.isEmpty()) sb.append(1).append("\n");
                    else sb.append(0).append("\n");
                    break;
                case "front":
                    Integer vF = deque.peekFirst();
                    if(vF == null) vF = -1;
                    sb.append(vF).append("\n");
                    break;
                case "back":
                    Integer vB = deque.peekLast();
                    if(vB == null) vB = -1;
                    sb.append(vB).append("\n");
                    break;
            }
        }
        System.out.println(sb);
    }
}

Integer pF = deque.pollFirst();
if(pF == null) pF = -1;
sb.append(pF).append("\n");

백준 #1835번 : 카드

문제

1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.

2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.

3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.

4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.

5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

입력

출력

풀이

1. 덱을 선언하고, 0부터 N-1까지의 인덱스를 덱에 추가한다.

2. 인덱스가 저장되어 있는 덱에서 맨 앞에 있는 카드를 뒤로 보내는 시행을 단계 만큼 반복한 후, 그 다음 맨 앞에 있는 카드를 덱에서 제거하고, 제거한 카드의 인덱스 위치에 1부터 1씩 증가시키며 값을 배치한다.

3. ans 배열에 저장된 숫자를 출력하면 주어진 조건에 맞는 카드의 초기 순서를 출력할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int ans[] = new int[N];

        Deque<Integer> deque = new ArrayDeque<>();
        for(int i=0; i<N; i++) {
            deque.addLast(i);
        }

        int value = 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<i+1; j++) {
                int f = deque.pollFirst();
                deque.addLast(f);
            }
            int index = deque.pollFirst();
            ans[index] = value++;
        }

        for(int i=0; i<N; i++) {
            sb.append(ans[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}