덱(Double Ended Queue, 데크)은 큐(Queue) 자료구조의 한 종류로, 앞(front)과 뒤(rear) 양쪽 끝에서 모두 삽입과 삭제 연산을 수행할 수 있는 자료구조입니다. 일반적인 큐는 한쪽에서만 삽입하고 반대쪽에서만 삭제할 수 있지만, 덱은 데이터를 앞과 뒤 어느 위치에서든 추가하거나 제거할 수 있어 훨씬 유연하게 활용됩니다.
C++ 표준 템플릿 라이브러리(STL)는 이러한 덱을 <deque> 헤더 파일을 통해 기본으로 제공하며, 별도의 직접 구현 없이도 다양한 멤버 함수를 손쉽게 사용할 수 있습니다.
STL deque의 주요 멤버 함수
d.size()– 덱에 저장된 요소의 개수를 반환합니다.d.push_back()– 덱의 뒤쪽에 요소를 추가합니다.d.push_front()– 덱의 앞쪽에 요소를 추가합니다.d.pop_back()– 덱의 뒤쪽에서 요소를 제거합니다.d.pop_front()– 덱의 앞쪽에서 요소를 제거합니다.d.front()– 덱의 맨 앞 요소를 반환합니다.d.back()– 덱의 맨 뒤 요소를 반환합니다.
이러한 연산들은 모두 상수 시간 O(1)에 수행되므로, 양방향 삽입·삭제가 빈번한 상황에서 매우 효율적입니다.
알고리즘
시작 deque 컨테이너와 반복자(iterator)를 선언한다. 사용자의 선택에 따라 입력을 받는다. switch 문 안에서 아래 함수들을 호출한다: d.size() → 덱의 크기를 반환한다. d.push_back() → 덱의 뒤쪽에 요소를 삽입한다. d.push_front() → 덱의 앞쪽에 요소를 삽입한다. d.pop_back() → 덱의 뒤쪽에서 요소를 삭제한다. d.pop_front() → 덱의 앞쪽에서 요소를 삭제한다. d.front() → 덱의 맨 앞 요소를 반환한다. d.back() → 덱의 맨 뒤 요소를 반환한다. 덱의 모든 요소를 출력한다. 끝.
예제 코드
#include<iostream>
#include <deque>
#include <string>
#include <cstdlib>
using namespace std;
int main() {
deque<int> d;
deque<int>::iterator it;
int c, item;
while (1) {
cout<<"1.Size of the Deque"<<endl;
cout<<"2.Insert Element at the End"<<endl;
cout<<"3.Insert Element at the Front"<<endl;
cout<<"4.Delete Element at the End"<<endl;
cout<<"5.Delete Element at the Front"<<endl;
cout<<"6.Front Element at Deque"<<endl;
cout<<"7.Last Element at Deque"<<endl;
cout<<"8.Display Deque"<<endl;
cout<<"9.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Size of the Deque: "<<d.size()<<endl;
break;
case 2:
cout<<"Enter value to be inserted at the end: ";
cin>>item;
d.push_back(item);
break;
case 3:
cout<<"Enter value to be inserted at the front: ";
cin>>item;
d.push_front(item);
break;
case 4:
item = d.back();
d.pop_back();
cout<<"Element "<<item<<" deleted"<<endl;
break;
case 5:
item = d.front();
d.pop_front();
cout<<"Element "<<item<<" deleted"<<endl;
break;
case 6:
cout<<"Front Element of the Deque: ";
cout<<d.front()<<endl;
break;
case 7:
cout<<"Back Element of the Deque: ";
cout<<d.back()<<endl;
break;
case 8:
cout<<"Elements of Deque: ";
for (it = d.begin(); it != d.end(); it++)
cout<<*it<<" ";
cout<<endl;
break;
case 9:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}실행 결과
프로그램을 실행하면 다음과 같이 메뉴가 반복적으로 출력되며, 사용자가 번호를 입력해 원하는 연산을 수행할 수 있습니다.
1.Size of the Deque 2.Insert Element at the End 3.Insert Element at the Front 4.Delete Element at the End 5.Delete Element at the Front 6.Front Element at Deque 7.Last Element at Deque 8.Display Deque 9.Exit Enter your Choice: 1 Size of the Deque: 0 Enter your Choice: 2 Enter value to be inserted at the end: 1 Enter your Choice: 3 Enter value to be inserted at the front: 2 Enter your Choice: 6 Front Element of the Deque: 2 Enter your Choice: 7 Back Element of the Deque: 1 Enter your Choice: 1 Size of the Deque: 2 Enter your Choice: 8 Elements of Deque: 2 1 Enter your Choice: 2 Enter value to be inserted at the end: 4 Enter your Choice: 3 Enter value to be inserted at the front: 5 Enter your Choice: 8 Elements of Deque: 5 2 1 4 Enter your Choice: 4 Element 4 deleted Enter your Choice: 5 Element 5 deleted Enter your Choice: 8 Elements of Deque: 2 1 Enter your Choice: 9
실행 결과 분석
위 실행 과정을 단계별로 살펴보면 다음과 같습니다.
- 처음에는 덱이 비어 있으므로 크기가 0으로 출력됩니다.
- 메뉴 2번으로 값 1을 뒤쪽에 삽입하고, 메뉴 3번으로 값 2를 앞쪽에 삽입하면 덱은 [2, 1]이 됩니다.
- 앞 요소 조회(6번)에서는 2, 뒤 요소 조회(7번)에서는 1이 출력됩니다.
- 값 4를 뒤에, 값 5를 앞에 추가하면 덱은 [5, 2, 1, 4]가 됩니다.
- 뒤쪽 삭제(4번)로 4가, 앞쪽 삭제(5번)로 5가 제거되어 최종적으로 [2, 1]만 남습니다.
마무리
이처럼 C++ STL의 deque 컨테이너를 활용하면 양쪽 끝에서의 삽입과 삭제가 모두 가능한 덱 자료구조를 간단한 코드로 구현할 수 있습니다. 슬라이딩 윈도우 최댓값 계산, 작업 스케줄링, 되돌리기(Undo) 기능 등 양방향 처리가 필요한 다양한 알고리즘 문제에서 덱은 강력한 도구로 활용되니, 위 예제를 직접 실행해 보며 동작 방식을 익혀보시기 바랍니다.