猫史档案馆

我们上一节中已经学习了最基础的vector容器，这一章，我们将了解一些其它的容器，它们是为了实现某些数据结构而出现的，如：队列，栈等。

P.S.list，map，set和multimap，multiset将放到第三四章讲解

第一节：队列

队列（queue）是一种先进先出的数组，你可以认为是现实生活中的排队——第一个排队的人第一个出去，而最后进入队伍的最后一个出去。

队列的操作比vector要严格的多，它只能在整个容器的首尾操作，可能你会疑惑：这种限制多多的容器，为什么不用vector呢？

实际上queue在部分应用场景下比vector的效率要高，且因为它不支持对中间元素的访问，对数据也有了很好的保护，同时，我们也不必自行编写一个queue的实现！（这就是STL的初衷）

我们首先需要引用queue头文件（一般来说各种容器都会有一个自己的头文件，名字就是容器名）

#include <queue>

接着，使用如下代码定义一个queue对象a，类型为int：

#include <iostream>
#include <cstdlib>
#include <queue>

int main(){
    std::queue<int> a;
    return 0;
}

queue的成员如下：

a.front();// 返回 a 第一个元素引用，如果 a 为空，则返回值将因编译环境而异
a.back();// 返回 a 最后一个元素引用，如果 a 为空，则返回值将因编译环境而异
a.push(const T& obj);// 在 a 的尾部添加元素obj。
a.push(T&& obj);// 以移动语义的方式在 a 的尾部添加元素obj。
a.pop();// 删除 a 中的第一个元素。
a.size();// 返回 a 中元素的个数。
a.empty();// 如果 a 无元素则返回true，否则false
a.emplace();// 在 a 的末尾添加一个空对象（调用该类型的默认构造函数）

我们通过一个实际应用来了解如何运用这些方法：

#include <cstdlib>
#include <iostream>
#include <queue>

int main(){
    std::queue<int> a;
    int n;
    std::cout << "输入: ";
    std::cin >> n;
    for(int i = 0;i < n;++i){
        int t;
        std::cin >> t;
        a.push(t);
    }// 加入n个数字
    while(!a.empty()){
        std::cout << "当前最后一个元素: " << a.back() << std::endl;
        std::cout << "当前第一个元素: " << a.front() << std::endl;
        a.pop();// 清除第一个元素
    }// 因为a.empty()在a被清空前始终为false，可以用这个来作为始终循环的条件
    return 0;
}

下面是输出：

输入: 5
1 2 3 4 5
当前最后一个元素: 5
当前第一个元素: 1
当前最后一个元素: 5
当前第一个元素: 2
当前最后一个元素: 5
当前第一个元素: 3
当前最后一个元素: 5
当前第一个元素: 4
当前最后一个元素: 5
当前第一个元素: 5

可以看到，最后一个元素将最后一个被删除。

这里提供一份遍历queue的模板代码：

std::queue<T> q;
while(!q.empty()){
    std::cout << q.front() << " ";
    q.pop();
}

第二节：栈

前面我们提到了队列，它遵循FIFO原则（First In First Out，第一个进第一个出），而栈（stack）与之相反，遵循LIFO原则（Last In First Out，最后一个进第一个出），栈比队列的限制更为严格——它只能够在栈的开头操作（也称栈顶）。

栈可以理解为一个烤串：把烤肉挨个串到签子上，最后一个放的烤肉会第一个被抽出来吃掉，而第一个放进去的烤肉会在最后被吃掉。

栈的头文件如下：

#include <stack>

栈的成员则如下：

a.top();// 返回 a 第一个元素引用，如果 a 为空，会抛出一个错误
a.push(const T& obj);// 在 a 的尾部添加元素obj。
a.pop();// 删除 a 的栈顶（第一个）元素。
a.size();// 返回 a 元素的个数。
a.empty();// 如果 a 无元素则返回true，否则false
a.emplace();// 在 a 的顶部添加一个空对象（调用该类型的默认构造函数）

我们还是用前面的代码观察stack的特性：

#include <cstdlib>
#include <iostream>
#include <stack>

int main(){
    std::stack<int> a;
    int n;
    std::cout << "输入: ";
    std::cin >> n;
    for(int i = 0;i < n;++i){
        int t;
        std::cin >> t;
        a.push(t);
    }// 加入n个数字
    while(!a.empty()){
        std::cout << "当前第一个元素: " << a.top() << std::endl;
        a.pop();// 清除第一个元素
    }
    return 0;
}

以下为输出：

输入: 5
1 2 3 4 5
当前第一个元素: 5
当前第一个元素: 4
当前第一个元素: 3
当前第一个元素: 2
当前第一个元素: 1

可以看到最后放入的5第一个被输出，第一个放入的1最后被输出。

遍历栈的模板化代码如下：

std::stack<T> s;
while(!s.empty()){
    std::cout << s.top() << " ";
    s.pop();
}

作业

1.栈和队列最大的区别在什么？

2.相较于vector，栈和队列的限制在哪里？

3.写出两种容器的遍历代码

猫史档案馆

【C++进阶】拥抱STL！第二章：特殊容器精讲

回复