deque

전체 코드

---

📌 1. deque란?

• deque(Double-Ended Queue, 덱):
  • 양쪽 끝에서 삽입과 삭제가 가능한 시퀀스 컨테이너
  • 배열 기반이지만 메모리 할당 정책이 vector와 다름
  • 중간 삽입/삭제는 느리지만, 처음과 끝의 삽입/삭제는 빠름
  • 임의 접근(Random Access) 지원 (index 접근 가능)
  • vector처럼 크기가 증가할 때 기존 데이터 복사가 발생하지 않음

---

📂 2. deque의 메모리 할당 정책

✅ vector vs. deque의 메모리 할당 차이점

컨테이너	메모리 할당 방식	중간 삽입/삭제	끝 삽입/삭제	임의 접근
vector	연속된 메모리 블록 사용. 공간이 부족하면 새로운 블록 할당 후 데이터 복사	느림 (데이터 이동 필요)	빠름 (맨 끝 추가/삭제)	지원 (O(1))
deque	여러 개의 작은 메모리 블록을 연결하여 사용	느림 (데이터 이동 필요)	빠름 (양쪽 삽입/삭제 가능)	지원 (O(1))

🔹 vector는 한 번에 큰 메모리를 할당해야 해서 메모리 관리가 어렵지만 성능이 빠름
🔹 deque는 여러 블록을 연결하여 관리하므로 메모리 관리가 쉽지만 중간 삽입/삭제는 비효율적

---

📜 3. deque 사용 예제 및 코드 분석

✅ 1) deque 기본 사용법

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

int main() {
    deque<int> dq;  // 정수형 덱 생성

    dq.push_back(1);  // 뒤에 1 추가
    dq.push_front(2); // 앞에 2 추가

    cout << "첫 번째 요소: " << dq[0] << endl;  // Random Access 지원

    return 0;
}

🔎 📌 분석

1. deque<int> dq; → 정수형 deque 선언
2. dq.push_back(1); → 뒤쪽에 1을 추가
3. dq.push_front(2); → 앞쪽에 2를 추가
4. cout << dq[0]; → 임의 접근을 지원하므로 []로 값 조회 가능

📢 deque는 push_front()를 지원하며, vector와 달리 처음 삽입/삭제가 효율적임

---

✅ 2) vector vs. deque 비교

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

int main() {
    vector<int> v(3, 1);  // 크기 3, 값 1로 초기화
    deque<int> dq(3, 1);  // 크기 3, 값 1로 초기화

    v.push_back(2);
    v.push_back(2);

    dq.push_back(2);
    dq.push_back(2);

    dq.push_front(3);
    dq.push_front(3);

    cout << "deque의 세 번째 요소: " << dq[3] << endl;  // Random Access 가능
    return 0;
}

🔎 📌 분석

1. vector<int> v(3, 1); → 크기 3, 값 1로 초기화
2. deque<int> dq(3, 1); → 크기 3, 값 1로 초기화
3. v.push_back(2); → vector 뒤에 2 추가
4. dq.push_back(2); → deque 뒤에 2 추가
5. dq.push_front(3); → deque 앞에 3 추가
6. cout << dq[3]; → deque는 vector처럼 인덱스로 접근 가능

📢 결론:

• deque는 vector와 달리 push_front() 지원
• vector는 capacity 개념 존재 (초기 할당된 크기 이상 증가 시 데이터 복사)
• deque는 새로운 메모리 블록을 할당하는 방식으로 크기 증가

---

✅ 3) deque의 삽입/삭제 성능

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

int main() {
    deque<int> dq = {1, 2, 3, 4, 5};

    dq.insert(dq.begin() + 2, 10);  // 세 번째 위치에 10 삽입
    dq.erase(dq.begin() + 3);       // 네 번째 요소 삭제

    for (int num : dq) {
        cout << num << " ";
    }

    return 0;
}

🔎 📌 분석

1. {1, 2, 3, 4, 5} 초기화
2. dq.insert(dq.begin() + 2, 10); → 세 번째 위치에 10 삽입
3. dq.erase(dq.begin() + 3); → 네 번째 요소 삭제
4. 출력 결과:

   1 2 10 4 5

📢 주의:

• deque의 중간 삽입/삭제는 vector와 동일하게 비효율적
• 중간 요소를 삽입하면 데이터가 이동해야 하므로 성능 저하 발생

---

✅ 4) deque에서 iterator 사용

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

int main() {
    deque<int> dq = {10, 20, 30, 40, 50};

    deque<int>::iterator it;
    for (it = dq.begin(); it != dq.end(); ++it) {
        cout << *it << " ";
    }

    return 0;
}

🔎 📌 분석

1. deque<int>::iterator it; → deque 반복자 선언
2. for (it = dq.begin(); it != dq.end(); ++it) → 반복자를 사용한 순회
3. cout << *it; → 현재 반복자가 가리키는 요소 출력

📢 결론:

• deque는 vector와 마찬가지로 반복자(iterator) 사용 가능
• begin(), end() 사용하여 순회 가능

---