C++容器适配与栈的实现及dequeque和优先级详解

C++容器适配与栈的实现及deque和优先级详解

容器适配器（Container Adapters）概述

容器适配器是C++标准库中的一类特殊容器，它们是由已有的基本数据结构通过组合和封装，扩展而来的。C++标准库提供了三种常见的容器适配器：栈（stack）、队列（queue）和优先级队列（priority_queue）。本文将重点讲解栈的实现以及deque（双端队列）和优先级队列的用法。

栈（stack）的实现

栈是一种后进先出（LIFO）的数据结构，它只允许在容器的一端（称为栈顶）进行插入和删除操作。C++标准库提供了stack模板类来实现栈。

栈模板类的定义和常用操作

在C++标准库中，栈模板类的定义如下：

template <class T, class Container = deque<T>>
class stack;

• T：栈中存储的元素类型。
• Container：底层容器类型，默认为deque（双端队列）。

常用操作如下：
- push(element)：将元素element压入栈顶。
- pop()：删除栈顶元素。
- top()：返回栈顶元素的引用。
- empty()：判断栈是否为空。
- size()：返回栈中元素的个数。

下面是一个使用栈的示例代码：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << "栈的大小：" << s.size() << std::endl;
    std::cout << "栈顶元素：" << s.top() << std::endl;

    s.pop();
    std::cout << "弹出栈顶元素后，栈顶元素：" << s.top() << std::endl;

    return 0;
}

输出结果为：

栈的大小：3
栈顶元素：3
弹出栈顶元素后，栈顶元素：2

双端队列（deque）的详解

双端队列是一种支持在两端进行插入和删除操作的数据结构，它允许在队列的两端同时进行插入和删除操作。C++标准库中的deque模板类实现了双端队列。

deque模板类的定义和常用操作

在C++标准库中，deque模板类的定义如下：

template <class T, class Allocator = allocator<T>>
class deque;

• T：队列中存储的元素类型。
• Allocator：分配器类型，默认使用std::allocator。

deque模板类的常用操作与向量（vector）相似，包括：
- push_back(element)：将元素element插入到队列尾部。
- push_front(element)：将元素element插入到队列头部。
- pop_back()：删除队列尾部的元素。
- pop_front()：删除队列头部的元素。
- back()：返回队列尾部元素的引用。
- front()：返回队列头部元素的引用。
- empty()：判断队列是否为空。
- size()：返回队列中元素的个数。

下面是一个使用deque的示例代码：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    dq.push_back(1);
    dq.push_front(2);
    dq.push_back(3);

    std::cout << "双端队列的大小：" << dq.size() << std::endl;
    std::cout << "队列头部元素：" << dq.front() << std::endl;
    std::cout << "队列尾部元素：" << dq.back() << std::endl;

    dq.pop_front();
    std::cout << "删除队列头部元素后，队列头部元素：" << dq.front() << std::endl;

    return 0;
}

输出结果为：

双端队列的大小：3
队列头部元素：2
队列尾部元素：3
删除队列头部元素后，队列头部元素：1

优先级队列（priority_queue）的详解

优先级队列是一种特殊的队列，在插入元素时会根据元素的优先级自动排序，每次访问队列时都能取出优先级最高的元素。C++标准库中的priority_queue模板类实现了优先级队列。

priority_queue模板类的定义和常用操作

在C++标准库中，priority_queue模板类的定义如下：

template <class T, class Container = vector<T>,
          class Compare = less<typename Container::value_type>>
class priority_queue;

• T：队列中存储的元素类型。
• Container：底层容器类型，默认为vector。
• Compare：比较器类型，默认为std::less，可以自定义比较器实现不同的排序方式。

priority_queue模板类的常用操作如下：
- push(element)：将元素element插入到优先级队列中。
- pop()：删除优先级最高的元素。
- top()：返回优先级最高的元素的引用。
- empty()：判断优先级队列是否为空。
- size()：返回优先级队列中元素的个数。

下面是一个使用优先级队列的示例代码：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(3);
    pq.push(1);
    pq.push(2);

    std::cout << "优先级队列的大小：" << pq.size() << std::endl;
    std::cout << "优先级最高的元素：" << pq.top() << std::endl;

    pq.pop();
    std::cout << "删除优先级最高的元素后，优先级最高的元素：" << pq.top() << std::endl;

    return 0;
}

输出结果为：

优先级队列的大小：3
优先级最高的元素：3
删除优先级最高的元素后，优先级最高的元素：2

希望以上内容对您有所帮助！