JArchive 프로그래밍 일기

목차

0x00 정의와 성질

0x01 기능과 구현

0x02 STL deque

0x03 연습문제 

0x00 정의와 성질

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 

deque == double linked queue 

추가, 제거, 앞/뒤 원소 확인 모두 O(1) 이다. 

그리고 덱 자료구조는 원소의 인덱스 확인이 애초에 불가능하다. 

하지만 독특하게도 STL deque에서는 인덱스로 원소 접근이 가능하다. (STL stack, queue에서는 인덱스로 원소 접근 불가.)

0x01 기능과 구현

배열로 간단히 덱을 구현해보자.

필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개다.

head는 가장 앞에 있는 원소의 인덱스이고 tail을 가장 뒤에 있는 원소의 인덱스 + 1 이다. 

설령 앞의 스택과 큐는 직접 구현해보지 않았더라도, 덱은 꼭 짜봤으면 좋겠다. 

배열로 덱 구현 템플릿 링크 

0x02 STL deque

STL deque는 vector와 비슷한 느낌이 강하다. 

하지만, vector와 달리 deque는 모든 원소가 메모리 상에 연속적으로 배치되어 있지 않다. 

앞쪽과 뒤쪽의 추가/제거가 모두 필요하다면 deque를 쓰는게 효율적이다. 

그렇지 않다면 vector를 쓰면 된다. 

deque 레퍼런스

#include <bits/stdc++.h>
using namespace std;

int main(void) {

    deque<int> deq;
    deq.push_front(10); // 10
    deq.push_back(50);  // 10 50
    deq.push_front(24); // 24 10 50

    for(auto x : deq) cout << x << ' ';
    cout << deq.size() << '\n';

    if(deq.empty()) cout << "deque is empty\n";
    else cout << "deque is not empty\n";
    deq.pop_front();  // 10 50
    deq.pop_back();   // 10

    cout << deq.back() << '\n';  // 10
    deq.push_back(72);        // 10 72
    cout << deq.front() << '\n'; // 10
    deq.push_back(12);        // 10 72 12
    deq[2] = 17;                 // 10 72 17

    deq.insert(deq.begin()+1, 33); // 10 33 72 17
    deq.insert(deq.begin()+4, 60); // 10 33 72 17 60

    for(auto x : deq) cout << x << ' ';
    cout << '\n';

    deq.erase(deq.begin()+3);
    cout << deq[3] << '\n';

    deq.clear(); // 모든 원소 제거
    cout << deq.size();
    return 0;
}

0x03 연습문제 

덱 문제집 

다음 시간에는 스택을 활용한 '수식의 괄호 쌍'을 배운다. 

공부 자료 출처: 바킹독 알고리즘 덱