C++ 中 Stack(栈) 的使用方法与基本操作

2023-07-08
四川
本文字数：1157 字
阅读完需：约 4 分钟

Stack 是一种常见的数据结构，常常被用来解决递归问题、括号匹配问题、函数调用栈等等。

一、stack 概述

Stack（栈）是一种线性数据结构，它具有"先进后出“（Last In First Out，简称 LIFO）的特点，即新元素进栈后只能位于栈顶，元素出栈时也只能从栈顶开始。

在 C++中，stack 通常是通过 STL（Standard Template Library）库中的 stack 模板实现的。STL stack 是基于 deque（双端队列）实现的，通过 deque 模板我们可以实现 stack 的一些操作。

二、stack 的基本操作

1、头文件

在使用 STL 中 stack 模板之前，我们需要包括头文件#include<stack>。

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

复制代码

2、stack 创建方式

在 C++中，我们使用类模板 stack 来实现 stack。其中 T 是存储元素的类型。stack 通过调用默认构造函数生成一个空 stack。

stack<int>a;   // 创建一个空stack

复制代码

3、栈顶和栈底操作

在 stack 中，我们可以分别通过 stack::top()和 stack::back()来访问栈顶和栈底元素。

stack<int>a;
a.push(1);a.push(2);
cout << a.top() << endl;   // 输出2cout << a.back() << endl;  // 输出1

复制代码

4、元素添加和删除

在 stack 中，我们通过 push()函数向栈顶添加一个元素。同时，我们也可以使用 pop()函数来从栈顶删除一个元素。

stack<int>a;
a.push(1);   // 数组变成[1]a.push(2);   // 数组变成[1,2]
cout << a.top() << endl;   // 输出2
a.pop();                  // 弹出2cout << a.top() << endl;  // 输出1

复制代码

5、栈的大小操作

我们可以通过 stack::size()函数获取当前栈中的元素数量。

stack<int>a;
a.push(1);   // 数组变成[1]a.push(2);   // 数组变成[1,2]a.push(3);   // 数组变成[1,2,3]
cout << a.size() << endl;  // 输出3

复制代码

6、判断栈是否为空

通过 stack::empty()函数可以判断当前的栈是否为空。如果栈为空则返回值为 true，否则为 false。

stack<int>a;
cout << a.empty() << endl;  // 输出1，表示为空
a.push(1);   // 数组变成[1]a.push(2);   // 数组变成[1,2]
cout << a.empty() << endl;  // 输出0，表示不为空

复制代码

三、stack 的实际应用

stack 在数学中经常被用来解决数学表达式中的括号匹配问题。在这个问题中，我们需要使用 stack 来匹配左右括号，以确保所输入的算式结果是正确的

假设我们有一个算式"( a + b ) / ( c - d )"，那么我们可以像下面的代码一样用 stack 来检查该算式中是否存在括号匹配问题。

#include <iostream>   #include <stack>  
using namespace std;  
int main(){  stack<char>s;  string str = "( a + b ) / ( c - d )";  for(int i=0;i<str.length();i++){    if(str[i]=='(') s.push(str[i]);    else if(str[i]==')') s.pop();  }    if(s.empty()){    cout<<"括号匹配成功"<<endl;  }  else{    cout<<"括号匹配失败"<<endl;  }  return 0;}