[C++] 자료구조 std::deque의 특징 및 사용법에 대해서

728x90

반응형

Photo by Markus Spiske on Unsplash

덱의 특징

 

C++의 표준 라이브러리(STL)에서 제공하는 std::deque는 "double-ended queue(덱)"을 나타내는 컨테이너입니다. 덱은 큐(queue)와 유사하지만, 양 끝에서 원소의 삽입 및 삭제가 모두 허용되는 특징이 있습니다. 따라서 앞과 뒤에서 빠르게 삽입, 삭제가 가능합니다.

std::deque의 주요 특징과 사용법은 다음과 같습니다:

1. 데이터 구조:
   • 덱은 여러 개의 블록으로 나뉘어 있는 배열로 구현되어 있습니다. 각 블록은 독립적인 메모리 조각을 가지고 있어 중간에 원소를 삽입하거나 삭제할 때 효율적입니다.
2. 헤더 파일:
   • #include <deque>를 통해 사용할 수 있습니다.
3. 선언 및 초기화:
   • std::deque은 다양한 초기화 방법을 지원합니다.
     

     #include <deque>
     
     // 비어있는 덱 선언
     std::deque<int> myDeque;
     
     // 초기값을 가지는 덱 선언
     std::deque<int> myDeque = {1, 2, 3, 4, 5};​

4. 원소의 삽입 및 삭제:
   • push_back, push_front, pop_back, pop_front 등을 사용하여 원소를 삽입하거나 삭제할 수 있습니다.
     

     myDeque.push_back(6);   // 덱의 뒤쪽에 6 추가
     myDeque.push_front(0);  // 덱의 앞쪽에 0 추가
     
     myDeque.pop_back();     // 덱의 뒤쪽에서 원소 제거
     myDeque.pop_front();    // 덱의 앞쪽에서 원소 제거​

5. 임의 접근 및 반복자:
   • operator[]나 at()을 사용하여 임의의 위치에 있는 원소에 접근할 수 있습니다.
     

     int element = myDeque[2];  // 인덱스 2의 원소에 접근
     
     for (auto it = myDeque.begin(); it != myDeque.end(); ++it) {
         // 반복자를 사용한 덱 순회
     }​

6. 기타 멤버 함수:
   • size(), empty(), clear(), front(), back() 등 다양한 멤버 함수를 제공합니다.

 

덱은 양 끝에서의 빠른 삽입 및 삭제가 필요한 경우에 유용하게 사용됩니다. 하지만 중간에서의 삽입 및 삭제는 벡터(std::vector)보다는 리스트(std::list)가 더 효율적일 수 있습니다. 선택할 컨테이너는 사용하고자 하는 작업의 특성에 따라 결정되어야 합니다.

 

덱의 예제

 

예제 1: 덱의 초기화 및 출력

#include <iostream>
#include <deque>

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

    // 덱의 크기 및 원소 출력
    std::cout << "덱의 크기: " << myDeque.size() << std::endl;
    std::cout << "덱의 원소: ";
    for (const auto& element : myDeque) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

 

예제 2: 덱의 앞과 뒤에 원소 삽입 및 삭제

#include <iostream>
#include <deque>

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

    // 앞과 뒤에 원소 추가
    myDeque.push_front(0);
    myDeque.push_back(6);

    // 앞과 뒤에서 원소 제거
    myDeque.pop_front();
    myDeque.pop_back();

    // 결과 출력
    std::cout << "덱의 크기: " << myDeque.size() << std::endl;
    std::cout << "덱의 원소: ";
    for (const auto& element : myDeque) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

예제 3: 덱을 사용한 회전 연산

#include <iostream>
#include <deque>

void rotateDeque(std::deque<int>& myDeque, int k) {
    if (myDeque.empty()) return;

    k = k % myDeque.size();
    std::rotate(myDeque.begin(), myDeque.begin() + k, myDeque.end());
}

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

    // 덱을 오른쪽으로 2번 회전
    rotateDeque(myDeque, 2);

    // 결과 출력
    std::cout << "덱의 크기: " << myDeque.size() << std::endl;
    std::cout << "덱의 원소: ";
    for (const auto& element : myDeque) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

예제 4: 덱을 이용한 회문(Palindrome) 검사

#include <iostream>
#include <deque>
#include <cctype>

bool isPalindrome(const std::string& str) {
    std::deque<char> charDeque;

    // 문자열에서 알파벳 문자만 덱에 삽입
    for (char c : str) {
        if (std::isalpha(c)) {
            charDeque.push_back(std::tolower(c));
        }
    }

    // 덱의 앞뒤에서 문자를 꺼내며 비교
    while (charDeque.size() > 1) {
        if (charDeque.front() != charDeque.back()) {
            return false; // 회문이 아님
        }
        charDeque.pop_front();
        charDeque.pop_back();
    }

    return true; // 회문임
}

int main() {
    std::string input;
    std::cout << "문자열을 입력하세요: ";
    std::getline(std::cin, input);

    if (isPalindrome(input)) {
        std::cout << "입력한 문자열은 회문입니다." << std::endl;
    } else {
        std::cout << "입력한 문자열은 회문이 아닙니다." << std::endl;
    }

    return 0;
}

 

예제 5: 덱을 이용한 슬라이딩 윈도우 평균 계산

#include <iostream>
#include <deque>
#include <vector>

std::vector<double> slidingWindowAverage(const std::vector<int>& nums, int k) {
    std::vector<double> averages;
    std::deque<int> windowSum;

    for (int i = 0; i < nums.size(); ++i) {
        if (i >= k) {
            averages.push_back(static_cast<double>(windowSum.front()) / k);
            windowSum.pop_front();
        }

        windowSum.push_back(nums[i]);
    }

    // 마지막 윈도우의 평균 추가
    averages.push_back(static_cast<double>(windowSum.front()) / k);

    return averages;
}

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int windowSize = 3;

    std::vector<double> result = slidingWindowAverage(numbers, windowSize);

    std::cout << "슬라이딩 윈도우 평균: ";
    for (double avg : result) {
        std::cout << avg << " ";
    }
    std::cout << std::endl;

    return 0;
}