TIL

덱을 배우고 구현해보았다.

덱(Deque)

(처음에 덱이 deck..인줄알았다.. 게임 그만하길)
double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용되지 않는다.

백준 10866번: 덱

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

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

public class Main{
	static int front =10000;
	static int back= 10000;
	static int size= 0;
	static int[] deque;
	
	static void push_front(int item) {
		deque[front] =item;
		front--;
		size++;
	}
	
	static void push_back(int item) {
		back++;
		size++;
		deque[back] = item;
	}

	static int pop_front() {
		if(size==0) {
			return -1;
		}
		int tmp=deque[front+1];
		front++;
		size--;
		return tmp;
	}
	
	static int pop_back() {
		if(size==0) {
			return -1;
		}
		int tmp=deque[back];
		back--;
		size--;
		return tmp;
	}
	
	static int size() {
		return size;
	}
	
	static int empty() {
		if(size==0) {
			return 1;
		}
		return 0;
	}
	
	
	static int front() {
		if(size==0) {
			return -1;
		}
		return deque[front+1];
	}
	
	static int back(){
		if(size==0) {
			return -1;
		}
		return deque[back];
	}
	
	
	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 n = Integer.parseInt(br.readLine());
		
		deque=new int[20001];
		
		int item = 0;
		
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			switch (str) {
			case "push_front":
				item = Integer.parseInt(st.nextToken());
				push_front(item);
				break;
			case "push_back":
				item = Integer.parseInt(st.nextToken());
				push_back(item);
				break;
			case "pop_front":
				bw.write(pop_front()+"\n");
				break;
			case "pop_back":
				bw.write(pop_back()+"\n");
				break;
			case "empty":
				bw.write(empty()+"\n");
				break;
			case "size":
				bw.write(size()+"\n");
				break;
				
			case "front":
				bw.write(front()+"\n");
				break;
			case "back":
				bw.write(back()+"\n");
				break;
			}
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

큐와 비슷한듯 다르게 구현한다.
front가 0이 아니라 배열의 중간부터 시작한다.
10000보다 더 큰 수는 입력으로 들어오지 않는다고 하니 10000부터 시작하면서 front에 push하면 front를 하나씩 줄여주는 방식.
back에 들어온다면 back을 하나씩 늘려주면 된다.
pop은 반대로 하면 되겠다.

다음엔 ArrayDeque 클래스를 사용해보도록 하겠다.