C++中的deque怎么使用

這篇文章主要介紹“C++中的deque怎么使用”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C++中的deque怎么使用”文章能幫助大家解決問題。

1）deque的定義及基本用法

要使用deque，我們需要包含頭文件，定義deque對象如下：

#include <deque>
using namespace std;
deque<int> dq; // 定義deque對象dq，其中元素類型為int型

deque支持的基本操作如下：

• 在deque的隊首插入元素：push_front()方法。

• 在deque的隊尾插入元素：push_back()方法。

• 刪除deque隊首的元素：pop_front()方法。

• 刪除deque隊尾的元素：pop_back()方法。

• deque的長度：size()方法。

• 判斷deque是否為空：empty()方法。

• 訪問deque隊首元素：front()方法。

• 訪問deque隊尾元素：back()方法。

示例代碼如下：

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;
    dq.push_front(1);   // 在隊首插入元素1
    dq.push_back(2);    // 在隊尾插入元素2
    dq.push_front(3);   // 在隊首插入元素3
    dq.pop_back();      // 刪除隊尾元素2
    cout << "長度：" << dq.size() << endl;      // 打印長度
    while(!dq.empty()){
        cout << dq.front() << ' ';     // 打印隊列中的每一個元素
        dq.pop_front();     // 刪除隊首元素
    }
    return 0;
}

執行結果：

長度：2
3 1

2）deque的迭代器

deque支持迭代器，可以按照指針的方式遍歷deque中的所有元素。deque迭代器支持前向訪問，但不支持隨機訪問，即不支持下標操作。deque迭代器又分為普通迭代器和反向迭代器，可以分別用begin()，end()，rbegin()，rend()方法來獲取。

示例代碼如下：

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_front(4);
    cout << "正向遍歷：";
    for(deque<int>::iterator it=dq.begin();it!=dq.end();it++)
        cout << *it << ' ';    // 打印所有元素
    cout << endl;
    cout << "反向遍歷：";
    for(deque<int>::reverse_iterator it=dq.rbegin();it!=dq.rend();it++)
        cout << *it << ' ';    // 打印所有元素（反向）
    cout << endl;
    return 0;
}

執行結果：

正向遍歷：4 1 2 3 
反向遍歷：3 2 1 4 

3）deque的性能

對于在最差情況下，即內存池容量已滿的情況，deque在表現上比較優，它的時間復雜度為O(1)，因為deque在前端和后端進行插入和刪除的操作所需時間復雜度為O(1)，但如果在中間進行插入和刪除，則時間復雜度為O(N)，因為因為需要把后面的元素往后移動。同時，它的空間復雜度為O(N)，其中N表示deque中元素的個數。

4）deque的應用：滑動窗口問題

滑動窗口問題是指在一個序列中找出所有長度為k的子序列，并且每次移動一個單位，重復執行這個操作，最終得到所有的子序列。這個問題在處理字符串問題，尤其是搜索問題中經常出現。我們可以用deque來解決這個問題，將待處理的數據元素存入到deque中，每次向右滑動窗口的時候從左邊移除最先加入的元素，同時從右邊添加一個新的元素。

示例代碼如下：

#include <iostream>
#include <deque>

using namespace std;

void printMax(int arr[], int n, int k)
{
    deque<int> dq; // 存儲元素下標，用于判斷窗口是否失效，同時也維護了單調性
    for (int i=0; i<k; i++) {
        while (!dq.empty() && arr[i] >= arr[dq.back()])
            dq.pop_back();  // 維護單調性，刪除隊列中元素使其單調遞增
        dq.push_back(i);    // 將元素下標存入隊列
    }
    for (int i=k; i<n; i++) {
        cout << arr[dq.front()] << " ";    // 打印當前窗口中的最大值
        while (!dq.empty() && dq.front() <= i-k)
            dq.pop_front(); // 刪除隊首元素，判斷隊首元素是否已失效
        while (!dq.empty() && arr[i] >= arr[dq.back()])
            dq.pop_back();  // 維護單調性，刪除隊列中元素使其單調遞增
        dq.push_back(i);    // 將元素下標存入隊列
    }
    cout << arr[dq.front()] << endl;    // 打印最后一個窗口中的最大值
}

int main()
{
    int arr[] = {4, 3, 5, 4, 2, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    printMax(arr, n, k);
    return 0;
}

此示例代碼中，我們定義了一個deque用于存儲元素下標，同時維護單調性，使得隊列中的元素單調遞增。在每次可取的滑動窗口過程中，只需找到隊列中的最大值。這個示例中的時間復雜度為O(N)。

關于“C++中的deque怎么使用”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。