[자료구조] 덱(Deque, Double Ended Queue)

[목차]

1. Deque이란?
2. Deque 기능
   1. 주요 기능 소개
   2. 구현해보기
   3. 주요 기능들의 성능 분석
   4. 예제 코드
3. Deque의 특징
4. 예제 문제

---

 

1. Deque이란?

선형 자료구조에는 Stack, Queue, Deque, Linked List가 있다. Duque는 선형 자료구조의 한 종류이다.

Double Ended Queue의 줄임말로 양쪽에서 삽입과 삭제가 가능한 Queue를 말한다.

주로 배열을 뒤집어서 원소를 추가/삭제하는 경우에 Deque를 쓰면 효율적으로 구현할 수 있다.

 

C++과 java 모두 Deque을 지원한다. 따라서 그냥 가져다 쓰면 된다. 여기서는 C++에서 Deque의 주요 기능들을 간단히 소개하고 구현해본다.

예제는 [백준 5430번]을 이용한다.

---

2. Deque의 기능

1) 주요 기능

문제풀이에서 주로 쓰는 기능이다.

멤버 함수	설명
push_front	deque의 앞에 원소 추가
push_back	deque의 뒤에 원소 추가
pop_front	앞의 원소를 제거
pop_back	마지막 원소를 제거
front	deque의 앞의 원소를 반환
back	duque의 마지막 원소를 반환
size	deque의 크기를 반환
empty	비어있는지 확인해주는 기능, 저장한 원소가 있으면 false, 없으면 true 반환

 

2) 기능 구현해보기

배열과 연결리스트로 모두 구현 가능하지만 배열로 구현하는 것이 더 간단한다.

배열로 구현할 경우 크기는 MX(최대 크기) x 2 + 1이다. (앞뒤로 MX만큼 추가가 가능하기 때문이다.)

이때 MX가 배열의 가운데 index가 된다. 따라서 head와 tail 모두 MX로 초기화한다.

이후에 앞이나 뒤에 하나씩 원소를 추가 / 제거해주면 된다.

[앞에 원소를 추가한 경우]

[뒤에 원소를 추가한 경우]

이렇게 head와 tail로 원소를 추가, 제거하며 대소관계로 empty 여부 등을 판단하는 것이다.

선언

#define MX 10000

int dat[2*MX + 1];
int  head = MX, tail =  MX;

 

push_front

void push_front(int x){
    dat[--head] = x;
}

먼저 head를 1감소시키고 원소를 추가하면 된다.

push_back

void push_back(int x){
    dat[tail++] = x;
}

먼저 tail에 원소를 추가하고 tail을 1증가시키면 된다.

pop_front

void pop_front(){
    head++;
}

head만 1증가시키면 된다. 어차피 다음의 push_front때 원소가 덮어씌워지므로 원소의 값은 그대로 두어도 된다.

pop_back

int pop_back(){
    tail--;
}

tail만 1감소시키면 된다. 어차피 다음의 push_back때 원소가 덮어씌워지므로 원소의 값은 그대로 두어도 된다.

front

int front(){
    return dat[head];
}

head에 있는 원소를 가져오면 된다.

back

int back(){
   return dat[tail-1];
}

tail - 1에 있는 원소를 가져오면 된다.

size

int size(){
    return tail - head;
}

tail - head가 deque의 사이즈이다.

empty

bool empty(){
    if(head == tail) return true;
    return false;
}

head와 tail의 대소 관계로 empty의 여부를 판단한다. head와 tail이 같다면 비어있는 것이다.

3) 주요 기능들의 성능 분석

push_front와 push_back의 시간 복잡도는 O(1)이다.

front와 back도 O(1)이며 pop_front와 pop_back 모두 O(1)이다.

empty와 size도 모두 O(1)이다.

 

4) 구현한 코드

다음 접은글은 직접 구현한 경우와 STL의 <deque>를 사용한 경우 두 가지를 이용하여 예제 문제를 구현한 코드이다. 문제는 [백준 5430번]이다.

[직접 구현한 코드]

#include<iostream>
#define MX 10000
using namespace std;

int dat[2*MX + 1];
int  head = MX, tail =  MX;

void push_front(int x){
    dat[--head] = x;
}

void push_back(int x){
    dat[tail++] = x;
}

int pop_front(){
    if(head < tail) return dat[head++];
    return -1;
}

int pop_back(){
    if(head < tail) return dat[--tail];
    return -1;
}
int front(){
    if(head < tail) return dat[head];
    return -1;
}
int back(){
    if(head < tail) return dat[tail-1];
    return -1;
}
int size(){
    return tail - head;
}
bool empty(){
    if(head == tail) return true;
    return false;
}

int main(void){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    
    int T;
    cin >> T;
    while(T--){
        int x;
        string order;
        cin >> order;
        if(order == "push_front"){
            cin >> x;
            push_front(x);
        }
        else if(order == "push_back"){
            cin >> x;
            push_back(x);
        }
        else if(order == "pop_front") cout << pop_front() << "\n";
        else if(order == "pop_back") cout << pop_back() << "\n";
        else if(order == "front") cout << front() << "\n";
        else if(order == "back") cout << back() << "\n";
        else if(order == "size") cout << size() << "\n";
        else cout << empty() << "\n";
    }
    return 0;
}

 

[STL을 사용하여 구현한 코드]

#include<iostream>
#include<deque>
using namespace std;

deque<int> DQ;

int main(void) {
	int T;
	cin >> T;
	while (T--) {
		string order;
		cin >> order;
		if (order == "push_front") {
			int x;
			cin >> x;
			DQ.push_front(x);
		}
		else if (order == "push_back") {
			int x;
			cin >> x;
			DQ.push_back(x);
		}
		else if (order == "pop_front") {
			if (DQ.empty()) cout << -1 << "\n";
			else cout << DQ.front() << "\n", DQ.pop_front();
		}
		else if (order == "pop_back") {
			if (DQ.empty()) cout << -1 << "\n";
			else cout << DQ.back() << "\n", DQ.pop_back();
		}
		else if (order == "size") cout << DQ.size() << "\n";
		else if (order == "empty") cout << DQ.empty() << "\n";
		else if (order == "front") {
			if (DQ.empty()) cout << -1 << "\n";
			else cout << DQ.front() << "\n";
		}
		else {
			if (DQ.empty()) cout << -1 << '\n';
			else cout << DQ.back() << "\n";
		}
	}
	return 0;
}

---

 

3. Duque의 특징

정리

C++의경우 vector가 존재하여 Deque와 비슷한 것을 느낄 수 있다. 동작 방식과 메모리적인 측면에서 차이가 있는데 다음을 참고하자.

[참고]

C++에서 vector와 deque의 차이점

---

 

4. 예제

주로 배열을 뒤집어 원소를 추가 제거할 수 있는 문제에서 deque가 많이 활용된다.

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

5430번: AC