덱에 대해 알아보자

- 덱이란?

 

양쪽 끝 모두에서 자료를 넣고 뺄 수 있는 자료구조.

한 쪽에서만 자료를 넣고 빼면 스택처럼 사용할 수 있고 

한 쪽에서 자료를 넣고 한 쪽으로 빼면 큐처럼 사용할 수 있다.

 

하지만 덱을 사용해야만 풀 수 있는 문제는 거의 없기 때문에 PS에서는 거의 사용되지 않는다

 

- 주로 사용하는 메소드

 

addFirst: 덱 앞 쪽에 자료를 넣는 연산

addFirst: 덱 뒷 쪽에 자료를 넣는 연산
removeFirst: 덱 앞 쪽에서 자료를 빼는 연산

removeLast: 덱 뒷 쪽에서 자료를 빼는 연산

getFirst : 덱 앞 쪽에있는 자료를 가져온다

getLast : 덱 뒷 쪽에있는 자료를 가져온다
empty: 덱이 비어있는지 아닌지를 알아보는 연산

 

자세한 메소드는 

 

java.util.Deque<Integer> d = new ArrayDeque<Integer>();

 

위와 같은 코드로 덱 인스턴스 생성하면 확인 가능합니다!

 

- 구현

 

정확한 구현이 아닌

백준 10866번 덱 문제 ( https://www.acmicpc.net/problem/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.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
 
    private ArrayList<Integer> deque = new ArrayList<Integer>();
 
    public void pushFront(int x) {
        deque.add(0, x);
    }
 
    public void pushBack(int x) {
        deque.add(x);
    }
 
    public void popFront() {
        if (deque.size() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(deque.get(0));
            deque.remove(0);
        }
    }
 
    public void popBack() {
        if (deque.size() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(deque.get(deque.size() - 1));
            deque.remove(deque.size() - 1);
        }
    }
 
    public void size() {
        System.out.println(deque.size());
    }
 
    public void empty() {
        if (deque.size() == 0) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
 
    public void front() {
        if (deque.size() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(deque.get(0));
        }
    }
 
    public void back() {
        if (deque.size() == 0) {
            System.out.println(-1);
        } else {
            System.out.println(deque.get(deque.size() - 1));
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        Main deque = new Main();
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
 
        s = br.readLine();
        int count = Integer.parseInt(s);
 
        for (int i = 0; i < count; i++) {
            s = br.readLine();
 
            if (s.startsWith("push_back")) {
                String[] words = s.split(" ");
                int input = Integer.parseInt(words[1]);
 
                deque.pushBack(input);
 
            } else if (s.startsWith("push_front")) {
                String[] words = s.split(" ");
                int input = Integer.parseInt(words[1]);
 
                deque.pushFront(input);
            } else if (s.startsWith("front")) {
                deque.front();
            } else if (s.startsWith("back")) {
                deque.back();
            } else if (s.startsWith("size")) {
                deque.size();
            } else if (s.startsWith("empty")) {
                deque.empty();
            } else if (s.startsWith("pop_front")) {
                deque.popFront();
            } else if (s.startsWith("pop_back")) {
                deque.popBack();
            }
 
        }
 
    }
 
}