cs/자료구조
[자료구조] 덱(Deque)의 개념과 구현(Java)
천방지축 개발자
2023. 7. 11. 12:00
덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말합니다. 이 이름은 Double-Ended Queue에서 나왔습니다. 스택과 큐의 일반적인 특성을 모두 가지고 있어서 스택처럼 LIFO(Last In First Out) 구조, 큐처럼 FIFO(First In First Out) 구조로 사용할 수 있습니다.
덱이란?
- 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말함
- 스택과 큐의 일반적인 특성을 모두 가지고 있음
- 덱이란 앞쪽 뒤쪽 모두 삽입 삭제가 많이 이루어지는 작업에 적합
- 인덱스 조회 후 삽입 삭제에는 불리함
덱의 구현
- 원형 배열
- 연결 리스트
이 글에선 원형 배열로만 구현하겠습니다.
덱의 자료구조 설계
- add_front: 덱의 앞쪽에 요소를 추가
- add_rear: 덱의 뒤쪽에 요소를 추가.
- delete_front: 덱의 앞쪽에서 요소를 제거하고 반환
- delete_rear: 덱의 뒤쪽에서 요소를 제거하고 반환
- isFull(가득 찼는지 검사)
- isEmpty(비었는지 검사)
- 자료의 rear(초기값 0) , front(초기값 0)
초기값
front = 0
rear = 0
add_front
front가 가리키는 인덱스에 원소 추가
추가 후 front = (front-1)% size
add_rear
rear = (rear+1)% size 후
rear 인덱스에 원소 추가
delete_front
front = (front+1)% size
front가 가리키는 인덱스에 원소 추가
delete_rear
rear 인덱스에 원소 추가
rear = (rear-1)% size
원형 배열을 사용하였기 때문에 % size를 하였고,
인덱스 범위를 넘어가도 인덱스 범위를 오버하지 않고 배열의 크기를 사용하기 위해 원형 배열을 사용하였습니다.
isEmpty
rear == front
rear와 front 가 같으면 비었다고 봅니다.
isFull
rear == (front-1)%size ( 또는 (rear+1) %size )
isEmpty연산과 구별을 위해 항상 원형 배열의 가득 찬 경우는 size 보다 1개를 더 적게 사용합니다.
수행시간
- 앞 뒤 삽입 삭제: O(1)
구현 (Java)
public class Deque <E>{
private int size;
private int front;
private int rear;
private E[] deque;
public Deque(int size){
this.size = size;
this.front = 0;
this.rear = 0;
this.deque = (E[])new Object[this.size];
}
public Deque(){
this(10);
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
return (rear+1)%size == front;
}
public void add_front(E data){
if (isFull()){
return;
}
else{
deque[front] = data;
front = (front - 1 + size) % size;
}
}
public void add_rear(E data){
if (isFull()){
return;
}
else{
rear = (rear+1)%size;
deque[rear] = data;
return;
}
}
public E delete_front(){
if (isEmpty()){
return null;
}
else {
front = (front + 1) % size;
return deque[front];
}
}
public E delete_rear(){
if (isEmpty()){
return null;
}
else {
E temp = deque[rear];
rear = (rear - 1) % size;
return temp;
}
}
public void Print(){
if (isEmpty()){
System.out.println("없음");
return;
}
else{
int f = front;
int r = rear;
System.out.print("front->");
while(f!=r){
f = (f+1)%size;
System.out.print(deque[f]+ "->");
}
System.out.println();
}
}
}