덱(deque)

덱

• Double-Ended Queue
• 앞쪽과 뒤쪽에서 모두 삽입과 삭제가 가능한 큐

덱 연산

• push_front: 덱의 가장 앞에 값을 삽입
• push_back: 덱의 가장 뒤에 값을 삽입
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 반환한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 반환한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• isEmpty: 덱이 비어있으면 true, 그렇지 않으면 false 반환
• isFull: 덱이 가득차면 true, 그렇지 않으면 false 반환
• front: 덱의 가장 앞에 있는 정수를 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다.

덱 구현(배열 사용)

public class Deque{
	int deque[] = new int[10];
    int front = 0;
    int rear = 0;

    public void push_front(int item){
    	if(isFull()){
        	System.out.println("덱이 꽉 차있습니다.");
        	return;
        }
        deque[front] = item;
        front = (front - 1 + deque.length)%deque.length;
    }

		public void push_back(int item){
		    	if(isFull()){
		        	System.out.println("덱이 꽉 차있습니다.");
		        	return;
		        }
						rear = (rear+1)%deque.length;
		        deque[rear] = item;
		        rear = (rear+1)%deque.length;
		    }

    public int pop_front(){
    	if(isEmpty()){
        	System.out.println("덱이 비었습니다.");
            return -1;
        }
        int temp = deque[(front+1)%deque.length];
        front = (front - 1 + deque.length)%deque.length;
        return temp;
    }

		 public int pop_back(){
    	if(isEmpty()){
        	System.out.println("덱이 비었습니다.");
            return -1;
        }
        int temp = deque[rear];
        rear = (rear + 1)%deque.length;
        return temp;
    }

		public int front(){
    	if(isEmpty()){
        	System.out.println("덱이 비었습니다.");
            return -1;
        }
        return deque[(front+1)%deque.length]'
    }

		 public int back(){
    	if(isEmpty()){
        	System.out.println("덱이 비었습니다.");
            return -1;
        }
	      return deque[rear];
    }

    public boolean isEmpty(){
    	return (front==rear);
    }

    public boolean isFull() {
    	return (front==(rear+1)%deque.length);
    }

		public int size(){
			return (front<=rear) ? rear-front : deque.length-(front-rear);
		}
}

예시

• 백준 10866번 덱

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

1. 문제

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

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

1. 코드

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

public class b_10866 {
    static int front=0;
    static int rear = 0;
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int deque[] = new int[N];
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            switch (op){
                case "push_front":
                    int input = Integer.parseInt(st.nextToken());
                    deque[front] = input;
                    front = (front-1+N)%N;
                    break;
                case "push_back":
                    input = Integer.parseInt(st.nextToken());
                    rear = (rear +1) %N;
                    deque[rear] = input;
                    break;
                case "pop_front":
                    if(isEmpty())
                        sb.append(-1).append("\\n");
                    else{
                        front = (front +1)%N;
                        sb.append(deque[front]).append("\\n");
                    }
                    break;
                case "pop_back":
                    if(isEmpty())
                        sb.append(-1).append("\\n");
                    else{
                        sb.append(deque[rear]).append("\\n");
                        rear = (rear -1 + N)%N;
                    }
                    break;
                case "size":
                    if(rear>=front)
                        sb.append(rear-front).append("\\n");
                    else
                        sb.append(N-(front-rear)).append("\\n");
                    break;
                case "empty":
                    if(isEmpty())
                        sb.append(1).append("\\n");
                    else
                        sb.append(0).append("\\n");
                    break;
                case "front":
                    if(isEmpty())
                        sb.append(-1).append("\\n");
                    else
                        sb.append(deque[(front+1)%N]).append("\\n");
                    break;
                case "back":
                    if(isEmpty())
                        sb.append(-1).append("\\n");
                    else
                        sb.append(deque[rear]).append("\\n");
                    break;
            }
        }
        System.out.println(sb);
    }

    static boolean isEmpty(){
        if(rear==front)
            return true;
        else
            return false;
    }
}

이미지 출처 : (<https://commons.wikimedia.org/wiki/File:Deque.gif>)