*** 자바에서는 기본적으로 Deque인터페이스를 지원해주지만, 기본적인 Deque의 구조를 알고 쓰고자 작성하였습니다.
1. 덱(Deque)
Deque(덱 혹은 데크)은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미합니다.
덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있습니다. 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 합니다.
Queue의 연장선이기 때문에 Queue와의 차이점은 한쪽에서만 뺄 수 있느냐(단방향이냐) 양쪽에서 뺄 수 있느냐(양방향이냐)일 뿐 다른 차이점은 없어 단방향구조였던 Queue 인터페이스를 상속받아서 양방향으로 메소드를 더 추가해주는 과정을 거친 것이 Deque라고할 수 있습니다.
장점
- 데이터의 삽입과 삭제가 빠르다.
- 크기가 가변적이다.
- 앞, 뒤에서 데이터를 삽입/삭제할 수 있다.
- index로 임의 원소 접근이 가능하다.
- 새로운 원소 삽입 시에, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
단점
- deque의 중간에서의 삽입과 삭제가 어렵다.구현이 어렵다.
1.1 Deque 메서드
-
addFirst()
덱의 앞쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다 -
offerFirst()
덱의 앞쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다. -
addLast()
덱의 마지막 쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량 초과시 예외가 발생한다 -
add()
addLast()와 동일 -
offerLast()
덱의 마지막 쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다.
-
removeFirst()
덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다. -
pollFirst()
덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다. -
removeLast()
덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다. -
pollLast()
덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다. -
remove()
removeFirst()와 동일 -
poll()
pollFirst()와 동일
-
getFirst()
덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다 -
peekFirst()
덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 null이 리턴된다. -
getLast()
덱의 마지막쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다. -
peekLast()
덱의 마지막 엘리먼트 하나를 제거하지 않은 채 리턴한다. 덱이 비어있으면 null이 리턴된다. -
peek()
peekFirst()와 동일 -
removeFirstOccurrence(Object o)
덱의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다. -
removeLastOccurrence(Object o)
덱의 뒤쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다. -
element()
removeFirst()와 동일 -
addAll(Collection <? extends E c)
입력 받은 Collection의 모든 데이터를 덱의 뒤쪽에 삽입한다. -
push()
addFirst()와 동일. 덱을 스택으로 사용할 때 쓰임 -
pop()
removeFirst()와 동일. 덱을 스택으로 사용할 때 쓰임 -
remove(Object o)
removeFirstOccurrence(Object o)와 동일 -
contain(Object o)
덱에 Object o와 동일한 엘리먼트가 포함되어 있는지 확인 -
size()
덱의 크기 -
iterator()
덱의 앞쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴 -
descendingIterator()
덱의 뒤쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴
- BOJ 10866-덱 풀이
https://www.acmicpc.net/problem/10866
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Deque{
/*
* Deque 배열에서 front가 최종적으로 가리키는 위치는 항상 비워둔다.
* 즉, 가장 앞에있는 원소는 front + 1이 된다.
*
* 이유는 만약 front의 최종 위치에 원소를 넣게 되면 다음과 같
* 예외가 발생한다.
*
* 예로들어 push_front(3) 을 실행하려 하는데 아무 원소도 없을 때
* front--; 감소시킨 뒤 deque[front] = 3; 이 되면
* deque[9999] = 3; 이 된다. 이때 front = 9999; back = 0 이 된다.
*
* 하지만, 원소가 한 개만 있을 경우 해당 원소는 front 이자 back 원소가 된다.
* 이러한 경우를 방지하기 위해 deque[front] 에 원소를 넣은 뒤,
* front = (front - 1 + array.length) % array.length; 을 해준다.
*
* 결과적으로 front 요소 자체는 deque[(front + 1) % array.length] 위치에 자리한다.
* ((front + 1) % array.length == (front + 1) % 10000)
*/
private int[] arr;
private int front;
private int back;
private int size;
Deque(int size) {
arr = new int[size];
front = 0;
back = 0;
this.size = 0;
}
public void push_front(int X){
// 원소를 먼저 넣은 뒤 front을 감소시킨다.
arr[front] = X;
// 음수가 되지 않도록 배열 크기만큼 더해준다.
front = (front - 1 + arr.length) % arr.length;
this.size++;
}
public void push_back(int X){
/*
* arr[size] 까지 꽉 찼을 경우 0으로 가리키기 위해
* 배열 크기만큼 나눠 나머지를 구한다.
*/
back = (back +1) % arr.length;
this.size++;
arr[back] = X;
}
public int pop_front() {
if(this.size == 0)
return -1;
/*
* front + 1이 front 원소이므로 해당 원소를 임시 변수에 둔 뒤
* front 을 +1 증가시킨다.
*/
int ret = arr[(front +1) % arr.length];
front = (front + 1) % arr.length;
this.size--;
return ret;
}
public int pop_back() {
if(this.size == 0)
return -1;
int ret = arr[back];
back = (back-1 + arr.length) % arr.length;
this.size--;
return ret;
}
public int size() {
return this.size;
}
public int empty() {
if(this.size == 0){
return 1;
}
return 0;
}
public int front() {
if(this.size==0)
return -1;
return arr[(front+1) % arr.length];
}
public int back() {
if(this.size == 0){
return -1;
}
return arr[back];
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
Deque deque = new Deque(n);
for(int i=0;i<n;i++){
String str = br.readLine();
if(str.contains(" ")){
if(str.split(" ")[0].equals("push_front"))
deque.push_front(Integer.parseInt(str.split(" ")[1]));
else
if(str.split(" ")[0].equals("push_back"))
deque.push_back(Integer.parseInt(str.split(" ")[1]));
}
else switch(str){
case "pop_front" :
sb.append(deque.pop_front() + "\n");
break;
case "pop_back" :
sb.append(deque.pop_back() + "\n");
break;
case "size" :
sb.append(deque.size() + "\n");
break;
case "empty" :
sb.append(deque.empty() + "\n");
break;
case "front" :
sb.append(deque.front() + "\n");
break;
case "back" :
sb.append(deque.back() + "\n");
break;
}
}
System.out.println(sb);
}
}