数据结构01 栈及其应用

数据结构

数据结构是一种在程序中系统化管理数据集合的形式。它通常由以下3个概念组合而成：

• 数据集合：通过对象数据的本体（例如数组和结构体）保存数据集合
• 规则：保证数据集合按照一定规矩进行正确操作、管理和保存的规则（例如按照顺序取出数据）
• 操作：增、删、改、查等对数据集合的操作

我们今天主要讲解的是栈（Stack）的操作

栈及其特点

栈是一种线性数据结构，栈的特征是数据的插入和删除只能通过一端来实现，这一端称为“栈顶”，相应的另一端称为“栈底”。

栈及其特点

用一个简单的例子来说，栈就像一个放乒乓球的圆筒，底部是封住的，如果你想拿出乒乓球，只能从顶部拿。同样的，如果你想再将乒乓球放回去，也只能从顶部放入其中。当然生活中还有很多这样的例子，再比如食堂中的一叠盘子，我们只能从顶端一个一个的取。放盘子也只能放在最上方。

总结栈的特点为：先入后出(Last In First Out->LIFO)，即先入栈的元素要在之后入栈的元素取出来之后才能取出来。

STL模板中栈的基本使用

对于栈的使用，我们可以直接利用STL模板来实现，STL模板库中栈的基本操作如下：

头文件：#include<stack>

创建一个存放int类型数据的空栈s：stack<int> s;

s.empty():  判断栈是否为空，为空返回true，否则返回false；

s.size():  返回栈中元素的个数；

s.top():  获取栈顶元素的值；

s.push(k):   向栈中添加新的元素k；

s.pop():    删除栈s的栈顶元素。

s.push(k):   向栈中添加新的元素k；

s.pop():    删除栈s的栈顶元素。

训练：逆波兰表达式

逆波兰表达式，又称后缀表达式，后缀表达式不包含括号，运算符(包括'+''-''*''/')放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将后缀表达式的结果计算出。

【输入描述】输入一个逆波兰表达式，字符之间用空格隔开

【输出描述】输出算式结果

【输入样例】2 1 + 3 *

【输出样例】9

参考程序

#include<iostream>
#include<stack>
using namespace std;
int main(){
  int t,k;
  char c;
  stack<int> s;
  while(cin>>c){
        if(c>='0'&&c<='9')
            s.push(c-'0');  //是数字就入栈
        if(c=='+'){
            t=s.top(); //获取栈顶数字
            s.pop();   //出栈
            k=s.top(); //获取新的栈顶
            s.pop();     //出栈
            s.push(t+k);   //相加的和入栈
        }
        if(c=='-'){
            t=s.top();   //获取栈顶
            s.pop();     //出栈
            k=s.top();  //获取新的栈顶
            s.pop();     //出栈
            s.push(k-t); //相减结果入栈，注意顺序
        }
        if(c=='*'){
            t=s.top();
            s.pop();
            k=s.top();
            s.pop();
            s.push(t*k);   //相乘的积入栈
        }
        if(c=='/'){
            t=s.top();
            s.pop();
            k=s.top();
            s.pop();
            s.push(k/t); //相除结果入栈注意顺序
        }
    }
    cout<<s.top();
    return 0;
}

训练：括号匹配

给定一个字符串，里边可能包含“()”、“[]”、“{}”三种括号，请编写程序检查该字符串的括号是否匹配出现,匹配说明嵌套关系正确，例如 {[()]}() 是匹配的,而)({)[}]( 则不匹配。匹配则输出YES，否则输出NO。）

【输入描述】输入一个字符串 例如(1+2)/(0.5+1)

【输出描述】如果字符串匹配则输出YES，否则输出NO

【输入样例】(1+2)/[(0.5+1)*2]

【输出样例】YES

参考程序

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

bool isMatch(char open, char close) {
    if (open == '(' && close == ')') return true;
    if (open == '[' && close == ']') return true;
    if (open == '{' && close == '}') return true;
    return false;
}

int main() {
    stack<char> s;
    string a;
    cin >> a;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '(' || a[i] == '[' || a[i] == '{') {
            s.push(a[i]); // 左括号入栈
        } else if (a[i] == ')' || a[i] == ']' || a[i] == '}') {
            if (s.empty() ||!isMatch(s.top(), a[i])) { 
                cout << "NO" << endl; 
                return 0;
            }
            s.pop();
        }
    }
    if (s.empty()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}