当前位置：首页 > article >正文

C++初阶——stack

article 2024/11/16 7:15:22

一、什么是stack

栈是一种容器适配器，专门设计用于在后进先出（LIFO，Last In First Out）的上下文中操作，在这个上下文中，元素仅从容器的一端插入和提取。栈被实现为容器适配器，这些类使用一个特定容器类的封装对象作为其底层容器，并提供一组特定的成员函数来访问其元素。元素从特定容器的“后端”被推入/弹出，这被称为栈的顶部。底层容器可以是任何标准容器类模板或一些特别设计的容器类。

二、stack的定义及初始化

2.1stack的定义

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    stack<内置类型>s1; //定义一个储存数据类型为内置类型的stack容器s1 
    stack<自定义类型>s2; //定义一个储存数据类型为自定义类型的stack容器s2
    stack<int> s3[N]; //定义一个储存数据类型为int的stack容器数组,N为大小 
}

2.2stack的初始化

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1,2,4 };
    stack<int,vector<int>> s1(v);//用另一个容器进行初始化，第二个参数为用来初始化的容器类型
}

三、stack成员函数

3.1empty函数

bool empty() const;//函数原型

返回栈是否为空：即其大小是否为零。这个成员函数实际上调用了底层容器对象的empty成员函数。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1,2,4 };
    stack<int,vector<int>> s1(v);
    stack<int> s2;
    cout << s1.empty() << endl;//s1不为空，所以返回值为0
    cout << s2.empty() << endl;//s2是一个空栈，返回值是1
}

3.2size函数

size_type size() const;

返回栈中的元素数量。这个成员函数实际上调用了底层容器对象的size成员函数。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1,2,4 };
    stack<int,vector<int>> s1(v);
    stack<int> s2;
    cout << s1.size() << endl;
    cout << s2.size() << endl;
}

3.3top函数

reference top();
const_reference top() const;

返回对栈顶元素的引用。由于栈是后进先出（LIFO）容器，栈顶元素是最后插入到栈中的元素。这个成员函数实际上调用了底层容器对象的back成员函数。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1,2,4 };
    stack<int,vector<int>> s1(v);
    cout << s1.top();
}

3.4push函数

void push (const value_type& val);
void push (value_type&& val);

在栈的顶部插入一个新元素，位于当前顶部元素的上方。这个新元素的内容被初始化为val一个副本。这个成员函数实际上调用了底层容器对象的push_back成员函数。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1,2,4 };
    stack<int,vector<int>> s1(v);
    s1.push(10);
    cout << s1.top() << endl;
    cout << s1.size() << endl;
}

3.5pop函数

void pop();

移除栈顶元素从栈中移除位于顶部的元素，有效地将其大小减少一。被移除的元素是最近插入到栈中的元素，其值可以通过调用成员函数top来检索。这会调用被移除元素的析构函数。这个成员函数实际上调用了底层容器对象的pop_back成员函数。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = { 1,2,4 };
    stack<int,vector<int>> s1(v);
    s1.push(10);
    cout << s1.top() << endl;
    cout << s1.size() << endl;
    s1.pop();
    cout << s1.top() << endl;
    cout << s1.size() << endl;
}

3.6emplace函数

template <class... Args> void emplace (Args&&... args);

在栈的顶部添加一个新元素，位于当前顶部元素的上方。这个新元素是就地构造的，而不是先构造一个临时对象然后再复制或移动到容器中，将args作为其构造函数的参数。这个成员函数实际上调用了底层容器的emplace_back成员函数，并将args转发给它。

emplace不属于匿名对象的用法。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

class A
{
public:
    int _a;
    int _b;
    A(int a = 0,int b = 0)
        :_a(a),_b(b)
    {}
};

int main() {
    stack<A> s1;
    A a;
    s1.push(a);
    s1.emplace(10, 10);
    cout << s1.top()._a << endl;
    s1.pop();
    cout << s1.top()._a << endl;
}

3.7swap函数

void swap (stack& x) noexcept(/*see below*/);

这里的注释/*see below*/指的是noexcept后面的表达式，它用于指定该函数是否可能抛出异常。在stack的swap函数中，这个表达式依赖于底层容器的swap函数是否可能抛出异常。

swap函数交换两个stack对象的内容。这是通过交换底层容器实现的，因为stack是一个容器适配器，它不直接存储元素，而是依赖于一个底层容器。

#include <stack>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v1 = { 1,2,3 };
    vector<int> v2 = { 4,5,6 };
    stack<int,vector<int>> s1(v1);
    stack<int, vector<int>> s2(v2);
    cout << s1.top() << endl;
    cout << s2.top() << endl;
    s1.swap(s2);
    cout << s1.top() << endl;
    cout << s2.top() << endl;
}

当然，也可以通过标准库里的模板swap函数进行交换。

#include <stack>
#include <vector>
#include <iostream>
#include<algorithm>
using namespace std;

int main() {
    vector<int> v1 = { 1,2,3 };
    vector<int> v2 = { 4,5,6 };
    stack<int,vector<int>> s1(v1);
    stack<int, vector<int>> s2(v2);
    cout << s1.top() << endl;
    cout << s2.top() << endl;
    swap(s1, s2);
    cout << s1.top() << endl;
    cout << s2.top() << endl;
}

四、运算符重载

bool operator==(const stack& lhs, const stack& rhs);
bool operator!=(const stack& lhs, const stack& rhs);
bool operator<(const stack& lhs, const stack& rhs);
bool operator>(const stack& lhs, const stack& rhs);
bool operator<=(const stack& lhs, const stack& rhs);
bool operator>=(const stack& lhs, const stack& rhs);

工作原理