덱(Dequeue, Double Ended Queue)은 큐(Queue) 자료구조를 일반화한 형태로, 양쪽 끝(앞과 뒤)에서 모두 삽입과 삭제가 가능한 자료구조입니다. 일반적인 큐는 한쪽에서만 삽입하고 반대쪽에서만 삭제할 수 있지만, 덱은 이러한 제약이 없어 더욱 유연하게 활용할 수 있습니다.
덱의 기본 연산
덱에서 사용되는 대표적인 기본 연산은 다음과 같습니다.
- insert_at_beg() : 덱의 앞(front)에 요소를 삽입합니다.
- insert_at_end() : 덱의 뒤(rear)에 요소를 삽입합니다.
- delete_fr_beg() : 덱의 앞(front)에서 요소를 삭제합니다.
- delete_fr_rear() : 덱의 뒤(rear)에서 요소를 삭제합니다.
아래에서는 C++를 활용해 덱을 직접 구현하는 방법을 살펴보겠습니다.
알고리즘
시작
front(f)와 rear(r) 변수를 가지는 dequeue 클래스를 선언하고 아래 함수들을 정의한다.
insert_at_beg(int): 앞에 요소 삽입
큐가 가득 차 있지 않으면 앞에 요소를 삽입하고 front와 rear 값을 갱신한다.
그렇지 않으면 오버플로우(overflow) 메시지를 출력한다.
insert_at_end(int): 뒤에 요소 삽입
큐가 가득 차 있지 않으면 뒤에 요소를 삽입하고 front와 rear 값을 갱신한다.
그렇지 않으면 오버플로우(overflow) 메시지를 출력한다.
delete_fr_beg(): 앞에서 요소 삭제
큐가 비어 있으면 언더플로우(underflow) 메시지를 출력하고,
그렇지 않으면 맨 앞 요소를 삭제한 후 front 값을 갱신한다.
delete_fr_end(): 뒤에서 요소 삭제
큐가 비어 있으면 언더플로우(underflow) 메시지를 출력하고,
그렇지 않으면 맨 뒤 요소를 삭제한 후 rear 값을 갱신한다.
끝
C++ 예제 코드
#include<iostream>
using namespace std;
#define SIZE 10
class dequeue {
int a[20], f, r;
public:
dequeue();
void insert_at_beg(int);
void insert_at_end(int);
void delete_fr_front();
void delete_fr_rear();
void show();
};
dequeue::dequeue() {
f = -1;
r = -1;
}
void dequeue::insert_at_end(int i) {
if(r >= SIZE - 1) {
cout << "\n insertion is not possible, overflow!!!!";
} else {
if(f == -1) {
f++;
r++;
} else {
r = r + 1;
}
a[r] = i;
cout << "\nInserted item is" << a[r];
}
}
void dequeue::insert_at_beg(int i) {
if(f == -1) {
f = 0;
a[++r] = i;
cout << "\n inserted element is:" << i;
} else if(f != 0) {
a[--f] = i;
cout << "\n inserted element is:" << i;
} else {
cout << "\n insertion is not possible, overflow!!!";
}
}
void dequeue::delete_fr_front() {
if(f == -1) {
cout << "deletion is not possible::dequeue is empty";
return;
} else {
cout << "the deleted element is:" << a[f];
if(f == r) {
f = r = -1;
return;
} else
f = f + 1;
}
}
void dequeue::delete_fr_rear() {
if(f == -1) {
cout << "deletion is not possible::dequeue is empty";
return;
} else {
cout << "the deleted element is:" << a[r];
if(f == r) {
f = r = -1;
} else
r = r - 1;
}
}
void dequeue::show() {
if(f == -1) {
cout << "Dequeue is empty";
} else {
for(int i = f; i <= r; i++) {
cout << a[i] << " ";
}
}
}
int main() {
int c, i;
dequeue d;
do { // 스위치 연산 수행
cout << "\n 1.insert at beginning";
cout << "\n 2.insert at end";
cout << "\n 3.show";
cout << "\n 4.deletion from front";
cout << "\n 5.deletion from rear";
cout << "\n 6.exit";
cout << "\n enter your choice:";
cin >> c;
switch(c) {
case 1:
cout << "enter the element to be inserted";
cin >> i;
d.insert_at_beg(i);
break;
case 2:
cout << "enter the element to be inserted";
cin >> i;
d.insert_at_end(i);
break;
case 3:
d.show();
break;
case 4:
d.delete_fr_front();
break;
case 5:
d.delete_fr_rear();
break;
case 6:
exit(1);
break;
default:
cout << "invalid choice";
break;
}
} while(c != 7);
}
실행 결과
1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:4 deletion is not possible::dequeue is empty 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:5 deletion is not possible::dequeue is empty 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:1 enter the element to be inserted7 inserted element is:7 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:2 enter the element to be inserted6 Inserted item is6 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:2 enter the element to be inserted4 Inserted item is4 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:3 7 6 4 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:4 the deleted element is:7 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:5 the deleted element is:4 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:1 enter the element to be inserted7 inserted element is:7 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:3 7 6 1.insert at beginning 2.insert at end 3.show 4.deletion from front 5.deletion from rear 6.exit enter your choice:6
코드 설명 및 참고 사항
위 코드는 배열 기반으로 덱을 구현한 예제입니다. 주요 동작 방식은 다음과 같습니다.
- 생성자 : 초기 상태에서 front와 rear를 -1로 설정하여 덱이 비어 있음을 나타냅니다.
- 오버플로우 처리 : rear가 배열 크기(SIZE)의 한계에 도달하면 더 이상 뒤에 삽입할 수 없으며, front가 0이면 앞에도 삽입할 수 없습니다.
- 언더플로우 처리 : front가 -1이면 덱이 비어 있는 상태이므로 삭제 연산이 불가능합니다.
- show() 함수 : front부터 rear까지 순회하며 현재 덱에 저장된 모든 요소를 출력합니다.
실행 결과를 보면, 빈 덱에서 삭제를 시도하면 언더플로우 메시지가 출력되고, 요소를 앞과 뒤에 번갈아 삽입한 후 show()로 확인하면 7 6 4와 같이 저장 순서대로 출력되는 것을 알 수 있습니다. 또한 앞(front)과 뒤(rear)에서 각각 삭제했을 때 정상적으로 동작하는 것도 확인할 수 있습니다.
실무에서는 STL에서 제공하는 std::deque 컨테이너를 사용하면 훨씬 간편하게 덱을 활용할 수 있지만, 이처럼 직접 구현해 보면 덱의 내부 동작 원리와 인덱스 관리 방식을 깊이 이해하는 데 큰 도움이 됩니다.