剑指信奥 | C++ 之 STL - stack & queue

剑指信奥｜ C++ 之 STL - stack & queue

LIFO 与 FIFO

在学习今天的内容之前，我们先看一张图：

LIFO vs. FIFO｜Interlakemecalux

我们看到了几辆叉车在仓库里工作，但如果仔细看，会发现左右两边货架是不一样的，左边的货架两侧都是开放的，右边的货架只有一侧是开放的。

由于这个区别，导致了两个货架存取货物方式的不同：

对于左侧货架，先放进去的货物，可以在另外一侧先取出来
对于右侧的货架，最先放进去的货物，只能在最后被取出来

这两种存取方式的不同，分别对应于两个缩写：

LIFO: Last-In, First-Out 后进先出
FIFO: First-In, Last-Out 先进后出

这两个缩写词最先就是用于库存管理的，但是恰好和我们今天要学的两个 STL 容器类有关联，那就是 stack 和 queue。

为什么这么说呢？我们来一探究竟。

stack

stack 模版类简称为栈，是一种容器类数据结构，它的特点就是容器的一端是封闭的，最先入栈的元素位于栈底，最后入栈的元素位于栈顶：

栈的结构｜ Hakerearth

对应于这种特有的结构，在 C++ STL 的 stack 中，有着对应的数据操作方法。

我们先来看一下 stack 的声明和初始化：

#include <iostream>
#include <stack>

using namespace std;

int main() {

    // 栈的声明
    stack<int> si;

    // 栈的 size
    cout << si.size() << endl;

    return 0;
}

/*
 output:
    0
 */

stack 也是泛型的模版类，在声明时要指定数据的类型，size() 函数输出了当前栈内元素的数目。

我们再来看向栈中存取数据的方法：

#include <iostream>
#include <stack>

using namespace std;

int main() {

    stack<int> si;
    
    // 向栈中存放数据
    si.push(3);
    si.push(2);
    si.push(1);

    cout << si.size() << endl;

    // 返回栈顶元素
    cout << si.top() << endl;

    return 0;
}

/*
 output:
    3
    1
 */

push() 函数是向栈中存放数据的方法，我们依次放入了 3，2，1 三个数字，按照栈的数据结构特点，3 位于栈底，1 位于栈顶，所以 top() 函数返回栈顶元素的结果就是 1。

再来看 stack 删除元素的方法：

#include <iostream>
#include <stack>

using namespace std;

int main() {

    stack<int> si;

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

    cout << "size 1: " << si.size() << endl;

    // 弹出栈顶元素
    si.pop();

    cout << "size 2: " << si.size() << endl;

    cout << si.top() << endl;

    return 0;
}

/*
 output:
    size 1: 3
    size 2: 2
    2
 */

pop() 函数是弹出栈顶元素的出栈操作，弹出后，栈的数据数量减 1，2 成为了栈顶元素。

以上就是 stack CRUD 的基本方法。

queue

queue 称为队列，是一种两端开放的容器类数据结构，最先存入的数据位于队列头部，最后存入数据位于队尾：

队列的结构｜ Hakerearth

我们先来看队列的声明：

#include <iostream>
#include <queue>

using namespace std;

int main() {

    // 队列的声明
    queue<int> qi;

    // 数据的 size
    cout << qi.size() << endl;

    return 0;
}

/*
 output:
    0
 */

队列的声明也是泛型的方式，同样的，size() 也是输出当前数据量的函数。

接着，我们来看 deque 存取数据的方法：

#include <iostream>
#include <queue>

using namespace std;

int main() {

    queue<int> qi;

    // 向队列中存放数据
    qi.push(3);
    qi.push(2);
    qi.push(1);

    // 返回队首元素
    cout << qi.front() << endl;

    // 返回队尾元素
    cout << qi.back() << endl;

    return 0;
}

/*
 output:
    3
    1
 */

push() 函数负责向队列存放数据的入队操作，front() 函数返回队首元素，back() 函数访问队尾元素。根据队列的数据结构，先进先出的原则，第 1 个放进队列的 3 是队首，最后一个放进队列的 1 是队尾。

最后，看一下队列删除数据的方法：

#include <iostream>
#include <queue>

using namespace std;

int main() {

    queue<int> qi;

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

    cout << "size 1: " << qi.size() << endl;

    // 弹出队首元素
    qi.pop();

    cout << "size 2: " << qi.size() << endl;
    
    return 0;
}

/*
 output:
    size 1: 3
    size 2: 2
 */

pop() 函数可以弹出队首元素。

信奥竞赛

系列