C++（STL3）容器适配器（1） stack<T>，queue<T> and priority_queue<T>

C++（STL3）容器适配器

容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。 这里有 3 种容器适配器：

1. stack<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack<T> 模板定义在头文件 stack 中。
2. queue<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。可以为它指定一个符合确定条件的基础容器。queue<T> 模板定义在头文件 queue 中。
3. priority_queue<T>：是一个封装了 vector<T> 容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。priority_queue<T> 模板定义在头文件 queue 中。.

目录

C++（STL3）容器适配器

一、stack

1.基本介绍

2.堆栈操作相关函数：

二、queue

1.基本认识

2.函数操作

三、priority_queue

1.基本介绍

2.priority_queue 操作

一、stack<T>

1.基本介绍

stack<T>容器适配器中的数据是以 LIFO 的方式组织的，这和自助餐馆中堆叠的盘子、箱子中的一堆书类似。图 1 展示了一个理论上的 stack 容器及其一些基本操作。只能访问 stack 顶部的元素；只有在移除 stack 顶部的元素后，才能访问下方的元素。

stack 容器适配器的模板有两个参数。第一个参数是存储对象的类型，第二个参数是底层容器的类型。stack<T> 的底层容器默认是 deque<T> 容器，因此模板类型其实是 stack<typename T, typename Container=deque<T>>。通过指定第二个模板类型参数，可以使用任意类型的底层容器，只要它们支持 back()、push_back()、pop_back()、empty()、size() 这些操作。下面展示了如何定义一个使用 list<T> 的堆栈：

std::stack<std::string,std::list<std::string>> fruit;

创建堆栈时，不能在初始化列表中用对象来初始化，但是可以用另一个容器来初始化，只要堆栈的底层容器类型和这个容器的类型相同。例如：

std::list<double> values {1.414, 3.14159265, 2.71828}; std::stack<double,std::list<double>> my_stack (values);

第二条语句生成了一个包含 value 元素副本的 my_stack。这里不能在 stack 构造函数中使用初始化列表；必须使用圆括号。如果没有在第二个 stack 模板类型参数中将底层容器指定为 list，那么底层容器可能是 deque，这样就不能用 list 的内容来初始化 stack；只能接受 deque。

stack<T> 模板定义了拷贝构造函数，因而可以复制现有的 stack 容器：

std::stack<double,std::list<double>>copy_stack {my_stack}

copy_stack 是 my_stack 的副本。如你所见，在使用拷贝构造函数时，既可以用初始化列表，也可以用圆括号。

2.堆栈操作相关函数：

和其他序列容器相比，stack 是一类存储机制简单、所提供操作较少的容器。下面是 stack 容器可以提供的一套完整操作：

• top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
• push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
• push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
• pop()：弹出栈顶元素。
• size()：返回栈中元素的个数。
• empty()：在栈中没有元素的情况下返回 true。
• emplace()：用传入的参数调用构造函数，在栈顶生成对象。
• swap(stack<T> & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

stack<T> 模板也定义了复制和移动版的 operator=() 函数，因此可以将一个 stack 对象赋值给另一个 stack 对象。stack 对象有一整套比较运算符。比较运算通过字典的方式来比较底层容器中相应的元素。字典比较是一种用来对字典中的单词进行排序的方式。依次比较对应元素的值，直到遇到两个不相等的元素。第一个不匹配的元素会作为字典比较的结果。如果一个 stack 的元素比另一个 stack 的多，但是所匹配的元素都相等，那么元素多的那个 stack 容器大于元素少的 stack 容器。

可以用stack 实现一个简单的计算器程序，如下：

// A simple calculator using stack containers
#include <cmath>                                          // For pow() function
#include <iostream>                                       // For standard streams
#include <stack>                                          // For stack<T> container
#include <algorithm>                                      // For remove()
#include <stdexcept>                                      // For runtime_error exception
#include <string>                                         // For string class
using std::string;
// Returns value for operator precedence
inline size_t precedence(const char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    if (op == '^')
        return 3;
    throw std::runtime_error {string {"invalid operator in precedence() function: "} + op};
}
// Execute an operation
double execute(std::stack<char>& ops, std::stack<double>& operands)
{
    double result {};
    double rhs {operands.top()};                            // Get rhs...
    operands.pop();                                         // ...and delete from stack
    double lhs {operands.top()};                            // Get lhs...
    operands.pop();                                         // ...and delete from stack
    switch (ops.top())                                      // Execute current op
    {
        case '+':
            result = lhs + rhs;
            break;
        case '-':
            result = lhs - rhs;
            break;
        case '*':
            result = lhs * rhs;
            break;
        case '/':
            result = lhs / rhs;
            break;
        case '^':
            result = std::pow(lhs, rhs);
            break;
        default:
            throw std::runtime_error {string{"invalid operator: "} + ops.top()};
    }
    ops.pop();                                              // Delete op just executed
    operands.push(result);
    return result;
}
int main()
{
    std::stack<double> operands;                            // Push-down stack of operands
    std::stack<char> operators;                             // Push-down stack of operators
    string exp;                                             // Expression to be evaluated
    std::cout << "An arithmetic expression can include the operators +, -, *, /, and ^ for exponentiation." << std::endl;
    try
    {
        while (true)
        {
            std::cout << "Enter an arithmetic expression and press Enter - enter an empty line to end:" << std::endl;
            std::getline(std::cin, exp, '\n');
            if (exp.empty()) break;
            // Remove spaces
            exp.erase(std::remove(std::begin(exp), std::end(exp), ' '), std::end(exp));
            size_t index {};                                    // Index to expression string
            // Every expression must start with a numerical operand
            operands.push(std::stod(exp, &index));              // Push the first (lhs) operand on the stack
            while (true)
            {
                operators.push(exp[index++]);                     // Push the operator on to the stack
                // Get rhs operand
                size_t i {};                                      // Index to substring
                operands.push(std::stod(exp.substr(index), &i));  // Push rhs operand
                index += i;                                       // Increment expression index
                if (index == exp.length())                        // If we are at end of exp...
                {
                    while (!operators.empty())                      // ...execute outstanding ops
                        execute(operators, operands);
                    break;
                }
                // If we reach here, there's another op...
                // If there's a previous op of equal or higher precedence execute it
                while (!operators.empty() && precedence(exp[index]) <= precedence(operators.top()))
                    execute(operators, operands);                   //  Execute previous op.
            }
            std::cout << "result = " << operands.top() << std::endl;
        }
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
    std::cout << "Calculator ending..." << std::endl;
}

以上代码转自C语言中文网

当然不用STL，仅仅利用栈的知识，也可以完成，比如在学数据结构时也完成了简单的计算器设计：https://blog.csdn.net/IT_flying625/article/details/88081169

二、queue<T>

1.基本认识

只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。 许多程序都使用了 queue 容器。queue 容器可以用来表示超市的结账队列或服务器上等待执行的数据库事务队列。对于任何需要用 FIFO 准则处理的序列来说，使用 queue 容器适配器都是好的选择。

queue 的生成方式和 stack 相同，下面展示如何创建一个保存字符串对象的 queue:

std::queue<std::string> words;

也可以使用拷贝构造函数：

std::queue<std::string> copy_words {words}; // A duplicate of words

stack<T>、queue<T> 这类适配器类都默认封装了一个 deque<T> 容器，也可以通过指定第二个模板类型参数来使用其他类型的容器：

std::queue<std::string, std::list<std::string>>words;

底层容器必须提供这些操作：front()、back()、push_back()、pop_front()、empty() 和 size()。

2.函数操作

queue 和 stack 有一些成员函数相似，但在一些情况下，工作方式有些不同：

• front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
• back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
• push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
• push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
• pop()：删除 queue 中的第一个元素。
• size()：返回 queue 中元素的个数。
• empty()：如果 queue 中没有元素的话，返回 true。
• emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
• swap(queue<T> &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

queue<T> 模板定义了拷贝和移动版的 operator=()，对于所保存元素类型相同的 queue 对象，它们有一整套的比较运算符，这些运算符的工作方式和 stack 容器相同。

三、priority_queue<T>

1.基本介绍

不出所料，priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们自己。如果一个优先级队列记录的是医院里等待接受急救的病人，那么病人病情的严重性就是优先级。如果队列元素是银行的借贷业务，那么借记可能会优先于信贷。 priority_queue 模板有 3 个参数，其中两个有默认的参数；第一个参数是存储对象的类型，第二个参数是存储元素的底层容器，第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。因此模板类型是：

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

如你所见，priority_queue 实例默认有一个 vector 容器。函数对象类型 less<T> 是一个默认的排序断言，定义在头文件 function 中，决定了容器中最大的元素会排在队列前面。fonction 中定义了 greater<T>，用来作为模板的最后一个参数对元素排序，最小元素会排在队列前面。当然，如果指定模板的最巵一个参数，就必须提供另外的两个模板类型参数。

2.priority_queue 操作

对 priority_queue 进行操作有一些限制：

• push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。
• push(T&& obj)：将obj放到容器的适当位置，这通常会包含一个排序操作。
• emplace(T constructor a rgs...)：通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
• top()：返回优先级队列中第一个元素的引用。
• pop()：移除第一个元素。
• size()：返回队列中元素的个数。
• empty()：如果队列为空的话，返回true。
• swap(priority_queue<T>& other)：和参数的元素进行交换，所包含对象的类型必须相同。

priority_queue 也实现了赋值运算，可以将右操作数的元素赋给左操作数；同时也定义了拷贝和移动版的赋值运算符。需要注意的是，priority_queue 容器并没有定义比较运算符。因为需要保持元素的顺序，所以添加元素通常会很慢。稍后会在堆(heaps)一节讨论 priority_queue 的内部操作。