浅谈STL-栈（stack）及其应用

· · 个人记录

一、什么是栈？

C++中STL库中的数据类型。栈是一种特殊的数组，可以用来存储某种类型的数据，能从数组的同一端增加和删除数据。

如图

二、手写栈的写法

#include <iostream>
#define MAXLEN 1000
using namespace std;
struct Stack {
    int tp;
    int s[MAXLEN];
    void init() {
        tp=0;
    }
    bool push(int e) {
        if(tp>=MAXLEN) return false;
        s[tp] = e;
        tp ++;
        return true;
    }
    bool pop() {
        if(tp<=0) return false;
        tp -- ;
        return true ;
    }
    bool empty() {
        return tp==0;
    }
    int top() {
        return s[tp-1];
    }
    int size() {
        return tp;
    }
};  //此代码摘自kdt讲义

三、stl库中的栈使用

头文件: #include <stack> 
定义栈: stack<type> s;
入栈: s.push(e);
出栈: s.pop();
栈中元素个数: s.size();
判断栈空: s.empty();
取栈顶元素: s.top();

四、经典问题：括号匹配

#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include <stack>
using namespace std;
stack<char> s;
string a;
int main(){
//  freopen("AC.in","r",stdin);
//  freopen("AC.out","w",stdout);
    cin>>a;
    int k=a.size();
    for(int i=0;i<k;i++){
        if(a[i]=='@') break;
        else if(a[i]=='('){
            s.push(a[i]); 
        }
        else if(a[i]==')'){
                if(s.empty()){
                cout<<"NO";
                return 0;
            }
                else s.pop();
            }
        }

    if(!s.empty()) cout<<"NO";

    else cout<<"YES";
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}   //kdt2065

五、个人心得

学习栈的过程，是在学习STL中非常重要的部分。重在理解。虽说理解很重要，但是，记忆也是必不可少的一部分：栈必备的函数等一定要记熟，合理使用。

完结撒花✿✿ヽ(°▽°)ノ✿