Deque 자료구조 예제 및 정리

Deque

Queue는 선형 리스트로 선입선출(FIFO) 방식을 사용하고 시작과 끝을 가리키는 포인터로 삽입과 삭제를 한다. 이렇게 Queue는 앞으로는 삭제, 뒤로는 삽입을 할 때 사용하는데 Deque는 삽입과 삭제를 한쪽이 아닌 앞, 뒤 양쪽에서 할 수 있다.

 

Deque의 특징

1. 크기가 가변적이다.

2. 앞과 뒤에서 삽입과 삭제가 좋다.

3. 중간에 데이터 삽입, 삭제가 용이하지 않다.

4. 구현이 쉽지 않다.

5. 랜덤 접근이 가능하다.

 

Deque를 사용하는 경우

1. 앞과 뒤에서 삽입, 삭제를 한다.

2. 저장할 데이터 개수가 가변적이다.

3. 검색을 거의 하지 않는다.

4. 데이터 접근을 랜덤하게 하고 싶다.

---

아래 코드는 덱을 활용한 백준 #28279 덱2의 소스코드이다.

#include <iostream>
#include <deque>

using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    deque<int> dq;
    while(N-->0) {
        int n;
        cin >> n;

        if (n==1) {
            int a;
            cin >> a;
            dq.push_front(a);
        }
        else if (n==2) {
            int a;
            cin >> a;
            dq.push_back(a);
        }
        else if (n==3) {
            if (dq.empty()) cout << -1 << '\n';
            else {
                cout << dq.front() << '\n';
                dq.pop_front();
            }
        }
        else if (n==4) {
            if (dq.empty()) cout << -1 << '\n';
            else {
                cout << dq.back() << '\n';
                dq.pop_back();
            }
        }
        else if (n==5) cout << dq.size() << '\n';
        else if (n==6) dq.empty() ? cout << "1\n" : cout << "0\n";
        else if (n==7) {
            if (dq.empty()) cout << -1 << '\n';
            else cout << dq.front() << '\n';
        }
        else if (n==8) {
            if (dq.empty()) cout << -1 << '\n';
            else cout << dq.back() << '\n';
        }
    }

    return 0;
}