快捷導(dǎo)航

一文帶你了解C++中deque的使用

更新時(shí)間：2023年05月02日 09:48:04 作者：碼出世界的淡水魚(yú)

C++中的deque是一種雙端隊(duì)列，可以在隊(duì)列的前端和后端進(jìn)行插入元素和刪除操作，同時(shí)可以視作一個(gè)長(zhǎng)度不定的數(shù)組，支持高效的插入和刪除操作。本篇文章將深入探討C++中的deque的使用，感興趣的可以了解一下

1）deque的定義及基本用法

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

#include <deque>
using namespace std;
deque<int> dq; // 定義deque對(duì)象dq，其中元素類(lèi)型為int型

deque支持的基本操作如下：

在deque的隊(duì)首插入元素：push_front()方法。
在deque的隊(duì)尾插入元素：push_back()方法。
刪除deque隊(duì)首的元素：pop_front()方法。
刪除deque隊(duì)尾的元素：pop_back()方法。
deque的長(zhǎng)度：size()方法。
判斷deque是否為空：empty()方法。
訪(fǎng)問(wèn)deque隊(duì)首元素：front()方法。
訪(fǎng)問(wèn)deque隊(duì)尾元素：back()方法。

示例代碼如下：

#include <iostream>
#include <deque>

using namespace std;

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

執(zhí)行結(jié)果：

長(zhǎng)度：2
3 1

2）deque的迭代器

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

示例代碼如下：

#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;
}

執(zhí)行結(jié)果：

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

3）deque的性能

對(duì)于在最差情況下，即內(nèi)存池容量已滿(mǎn)的情況，deque在表現(xiàn)上比較優(yōu)，它的時(shí)間復(fù)雜度為O(1)，因?yàn)閐eque在前端和后端進(jìn)行插入和刪除的操作所需時(shí)間復(fù)雜度為O(1)，但如果在中間進(jìn)行插入和刪除，則時(shí)間復(fù)雜度為O(N)，因?yàn)橐驗(yàn)樾枰押竺娴脑赝笠苿?dòng)。同時(shí)，它的空間復(fù)雜度為O(N)，其中N表示deque中元素的個(gè)數(shù)。

4）deque的應(yīng)用：滑動(dòng)窗口問(wèn)題

滑動(dòng)窗口問(wèn)題是指在一個(gè)序列中找出所有長(zhǎng)度為k的子序列，并且每次移動(dòng)一個(gè)單位，重復(fù)執(zhí)行這個(gè)操作，最終得到所有的子序列。這個(gè)問(wèn)題在處理字符串問(wèn)題，尤其是搜索問(wèn)題中經(jīng)常出現(xiàn)。我們可以用deque來(lái)解決這個(gè)問(wèn)題，將待處理的數(shù)據(jù)元素存入到deque中，每次向右滑動(dòng)窗口的時(shí)候從左邊移除最先加入的元素，同時(shí)從右邊添加一個(gè)新的元素。

示例代碼如下：

#include <iostream>
#include <deque>

using namespace std;

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

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;
}

此示例代碼中，我們定義了一個(gè)deque用于存儲(chǔ)元素下標(biāo)，同時(shí)維護(hù)單調(diào)性，使得隊(duì)列中的元素單調(diào)遞增。在每次可取的滑動(dòng)窗口過(guò)程中，只需找到隊(duì)列中的最大值。這個(gè)示例中的時(shí)間復(fù)雜度為O(N)。

以上便是關(guān)于C++中deque的基本用法和應(yīng)用的相關(guān)介紹，希望對(duì)你有所幫助。

到此這篇關(guān)于一文帶你了解C++中deque的使用的文章就介紹到這了,更多相關(guān)C++ deque內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: