[백준] 덱2 / Dequq, LinkedList

 

 

Sliver 

 

 

문제

정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

1. 1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
2. 2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
3. 3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
4. 4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
5. 5: 덱에 들어있는 정수의 개수를 출력한다.
6. 6: 덱이 비어있으면 1, 아니면 0을 출력한다.
7. 7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
8. 8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

 

입력

 

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

 

 

출력

 

출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.

 

 

---

 

풀이

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Deque<Integer> dq = new LinkedList<>();
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++){
            String[] arr = br.readLine().split(" ");
            switch(arr[0]){
                case "1":
                    dq.offerFirst(Integer.parseInt(arr[1]));
                    break;
                case "2":
                    dq.offerLast(Integer.parseInt(arr[1]));
                    break;
                case "3":
                    sb.append(dq.isEmpty()?-1:dq.pollFirst()).append("\n");
                    break;
                case "4":
                    sb.append(dq.isEmpty()?-1:dq.pollLast()).append("\n");
                    break;
                case "5":
                    sb.append(dq.size()).append("\n");
                    break;
                case "6":
                    sb.append(dq.isEmpty()?1:0).append("\n");
                    break;   
                case "7":
                    sb.append(dq.isEmpty()?-1:dq.getFirst()).append("\n");
                    break;
                case "8":
                    sb.append(dq.isEmpty()?-1:dq.getLast()).append("\n");
                    break;
            }
        }
        System.out.println(sb);
        
        br.close();
    }

}

 

 

---

 

Dequq 덱

 

양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

 

 

1. Deque 선언 및 초기화

 

import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();

        // 요소 추가
        deque.addFirst("Apple");
        deque.addLast("Banana");
        deque.addLast("Cherry");

        // 첫 번째 요소와 마지막 요소 출력
        System.out.println("First element: " + deque.getFirst());
        System.out.println("Last element: " + deque.getLast());

        // 요소 제거
        deque.removeFirst();
        deque.removeLast();

        // 남은 요소 출력
        for (String fruit : deque) {
            System.out.println(fruit);
        }
    }
}

 

 

2. 주요 메서드

 

• 요소 추가
  • addFirst(E e) : 요소를 전단에 삽입한다. 
  • offerFirst(E e) : 요소를 전단에 삽입한다. 예외가 발생하지 않는다. 
  • addLast(E e) : 요소를 후단에 삽입한다
  • offerLast(E e) : 요소를 후단에 삽입한다. 예외가 발생하지 않는다. 
• 요소제거
  • removeFirst() : 덱의 전단 첫 번째 요소를 제거하고 반환한다.
  • pollFirst() : 덱의 전단 첫번째 요소를 제거하고 반환한다. 없다면 null을 반환한다. 
  • removeLast() : 덱의 후단 첫번째 요소를 제거하고 반환한다. 
  • pollLast() : 덱의 후단 첫번째 요소를 제거하고 반환한다. 없다면 null을 반환한다. 
• 요소출력
  • getFirst() : 덱 전단 첫번째 요소를 반환한다.
  • peekFirst() : 덱 전단 첫번째 요소를 반환한다. 없다면 null을 반환한다. 
  • getLast() : 덱 후단 첫번째 요소를 반환한다. 
  • peekLast() : 덱 후단 첫번째 요소를 반환한다. 없다면 null을 반환한다. 
• size() : 덱의 요소 개수를 반환한다.
• isEmpty() : 덱이 비어있는지 여부를 반환한다.
• clear() : 댁의 모든 요소를 제거한다. 

 

 

 

---

https://www.acmicpc.net/problem/28279