写作业的时候看到有人用stack容器做题，试了下效率起飞，二话不说记录一下XD

[TOC]

1.基础知识

头文件

1
#include<stack>

常用操作

1
2
3
4
5
6
7
stack<int> q;	//以int型为例
int x;
q.push(x);		//将x压入栈顶
q.top();		//返回栈顶的元素
q.pop();		//删除栈顶的元素
q.size();		//返回栈中元素的个数
q.empty();		//检查栈是否为空,若为空返回true,否则返回false

stack对象的默认构造

stack对象的默认构造形式： stack stkT;

尖括号里面还可以设置指针或者其他数据类型。

1
2
3
4
5
6
stack <int> stkInt;            //一个存放int的stack容器。

stack <float> stkFloat;     //一个存放float的stack容器。

stack <string> stkString;     //一个存放string的stack容器。

stack的出栈和进栈

1
2
3
stack.push(elem);            //往栈头添加元素

stack.pop();                     //往栈头移除第一个元素

stack的拷贝构造与赋值

1
2
3
4
5
6
7
stack(const stack &stk);                  //拷贝构造函数

stack& operator = (const stack &stk);          //重载等号操作符

stack<int>stkIntB(stkIntA);            //拷贝构造
stack<int>stkIntC;
stkIntC = stkIntA;                     //赋值

stack的数据存取

1
stack.top();     //返回最后一个压入栈元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
stack<int> stkIntA;

stkIntA.push(1);

stkIntA.push(3);

stkIntA.push(5);

stkIntA.push(7);

stkIntA.push(9);

 

int iTop = stkIntA.top(); //9

stkIntA.top() = 19; //19

stack的大小

1
2
3
stack.empty();                    //判断堆栈是否为空

stack.size();                        //返回堆栈的大小

2.例题

7-2 括号匹配

给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。

输入格式:

输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。

输出格式:

如果括号配对，输出yes，否则输出no。

输入样例1:

1
sin(10+20)

输出样例1:

1
yes

输入样例2:

1
{[}]

输出样例2:

1
no

输入样例3:

1
(()())

输出样例3:

1
yes

代码实现

c/c++ strlen(str)和str.length()和str.size()都可以求字符串长度。
其中**str.length()和str.size()**是用于求string类对象的成员函数
**strlen(str)*是用于求字符数组的长度，其参数是char。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
using namespace std;
#include<stack> //stack头文件
int judge(string s){
    stack<char>stk;//设置一个存放char的stack容器
    for(int i=0;i<s.length();i++){
        switch(s[i]){
                case'(':
                   stk.push(s[i]);//左括号，进栈
                break;
                case'[':
                   stk.push(s[i]);
                break;
                case'{':
                   stk.push(s[i]);
                break;
                case')':
                   if(stk.empty()) return 0;//如果栈空，返回0
                   if (stk.top() == '(') stk.pop();
                   //如果栈顶是左括号，配对成功，将其出栈，进行下一步
                   else return 0;
                break;
                case']':
                   if(stk.empty()) return 0;
                   if (stk.top() == '[') stk.pop();
                   else return 0;
                break;
                case'}':
                   if(stk.empty()) return 0;
                   if (stk.top() == '{') stk.pop();
                   else return 0;
                break;
        }
    }
    return stk.empty();//最终若括号一一配对，栈空，返回1值
}
int main(){
    string s;
    getline(cin,s);
    if(judge(s)==1){
        cout<<"yes"<<endl;
    }else{
        cout<<"no"<<endl;
    }
    return 0;
}

7-3 回文判断

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。

若用C++，可借助STL的容器实现。

输入格式:

输入待判断的字符序列，按回车键结束，字符序列长度<20。

输出格式:

若字符序列是回文，输出“YES”；否则，输出“NO”。

输入样例:

1
abdba

输出样例:

1
YES

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstring>
using namespace std;
#include<stack>
int main(){
    string s;
    int flag;
    getline(cin,s);
    stack<char>stk;
    for(int i=0;i<s.length();i++){
        stk.push(s[i]);
    }
    

    for(int i=0;i<s.length()/2;i++){
        flag=0;
        if(s[i]==stk.top()){
            stk.pop();
        }else{
            cout<<"NO"<<endl;
            flag=1;
            break;}
    }
    if(flag==0) cout<<"YES"<<endl;
    return 0;

}