给我十分钟带你了解栈及其简单应用_队列中的数据元素遵守”先进后出"(first in last out)的原则,简称filo结构

你还在为还没学过数据结构而苦恼 ？

你还在遇到关于“栈”的题茫然失措而苦恼 ？

你还在只听闻“栈”的大名而不知其谁而苦恼 ?

…

别苦恼，苦恼不能解决问题~

接下来让我带你认识什么是栈以及一些简单的应用例子。

好了废话不多说，进入正题

一、栈的概念

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

~~划重点： 栈的特点是先进后出/后进先出

二、栈的用法

用法：
stack<元素基类型> 类名;
如：
stack<char> stk//建立一个存储字符的名为stk的栈
stack<int> num//建立一个存储int型的名为num的栈
stack<double> dou//建立一个存储double型的名为dou的栈
1
2
3
4
5
6

接下来看一个栈（stack）的class类代码

/*说明：stk.push(n)表面上是将n压入stk中，实际上是将n
压入stk中包含的a数组内*/
template<typename T>class stack{
    T a[100001];
    int tail;
    public:
        void push(T n){//压入数据
            a[tail++]=n;
        }
        void pop(){//弹出栈顶元素
            tail--;
        }
        T top(){//返回栈顶元素
            return a[tail-1];
        }
        int size(){//返回栈内元素的个数
            return tail;
        }
        bool empty(){//判断栈是否为空
            return tail==0;
        }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、应用例子

1.后缀表达式求值

题目描述
所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：3*(5–2)+7对应的后缀表达式为：3．5．2．-*7．+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。

输入格式
输入：后缀表达式

输出格式
输出：表达式的值

输入输出样例
输入 #1

3.5.2.-*7.+@

输出 #1

16

说明/提示
字符串长度，1000内。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1001;
char a[MAXN];
int sum,k;
stack <int> stk;
int main(){
    gets(a);
	for(int i=0;a[i]!='@';i++)
	{
		if(a[i]=='.')
		{
			sum=0,k=1;
			//将数据转换后存入栈中
			for(int j=i-1;j>=0&&a[j]>='0'&&a[j]<='9';j--){
                sum=sum+(a[j]-'0')*k;
                k*=10;
			}
			stk.push(sum);
			continue;
		}
		if(a[i]>='0' && a[i]<='9')
            continue;
		sum=stk.top();//栈顶元素
		stk.pop();//弹出栈顶元素
		if(a[i]=='+') sum=stk.top()+sum;
		if(a[i]=='-') sum=stk.top()-sum;
		if(a[i]=='*') sum=stk.top()*sum;
		if(a[i]=='/') sum=stk.top()/sum;
		stk.pop();
		stk.push(sum);//将sum压入栈中
    }
	cout<<sum<<endl;
	return 0;
}

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

思路 ：先定义一个来存放int型的栈，然后将输入的数据转换后存入栈中，但是以运算符号为分割，先进第一个数，再进第二个数，接着将后进的数先抛出，此时先进的数就是栈顶元素了，然后将这两个数做运算后再将第一个数抛出以及将运算结果sum压入栈中，以此循环即可。其实这道题除了上述解法之外，还可以用STL来解决，这里就不多阐述了。

2.中缀表达式求值

题目描述
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入格式
一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“×”，且没有括号，所有参与运算的数字均为 0到2^31 − 1之间的整数。

输入数据保证这一行只有0 − 9、+、×这 12种字符。

输出格式
一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。

输入输出样例
输入 #1

1+1*3+4

输出 #1

8

输入 #2

1+1234567890*1

输出 #2

7891

输入 #3

1+1000000003*1

输出 #3

4

说明/提示
对于 30%的数据，0 ≤ 表达式中加法运算符和乘法运算符的总数 ≤ 100；
对于 80%的数据，0 ≤ 表达式中加法运算符和乘法运算符的总数 ≤ 1000；
对于 100%的数据，0 ≤ 表达式中加法运算符和乘法运算符的总数 ≤ 100000。

#include<bits/stdc++.h>
using namespace std;
stack<int> num;//操作数
stack<char> a;//运算符
string str;
int sum=0,t,t1,t2;//t,t1,t2均为临时变量
int main()
{
    cin>>str;
    for(int i = 0;i < str.length();i++)
    {
        //转换数据后存入int型栈中
        if(str[i] >= '0' && str[i] <= '9')
        {
            if(str[i+1] >= '0' && str[i+1] <= '9')
                sum=sum*10+str[i]-'0';
            else
            {
                sum=(sum*10+str[i]-'0')%10000;   //取后四位即可
                num.push(sum);
                sum=0;
            }
        }
        //将运算符存入char型栈中
        if(str[i] < '0')
        {
            if(a.empty())
                a.push(str[i]);
            else
            {
                if(str[i] < a.top())//*小，+大（考虑到运算符的优先级,同级也不行）
                    a.push(str[i]);
                else
                {
                    t1=num.top();num.pop();
                    t2=num.top();num.pop();
                    if(a.top()=='*')
                        t=(t1*t2)%10000;
                    else
                        t=(t1+t2)%10000;
                    a.pop();
                    a.push(str[i]);
                    num.push(t);
                }
            }
        }
    }
    while(!a.empty())
    {
        t1=num.top();num.pop();
        t2=num.top();num.pop();
        char x=a.top();a.pop();
        if(x=='+')
        {
            t=(t1+t2)%10000;
            num.push(t);
        }
        else
        {
            t=(t1*t2)%10000;
            num.push(t);
        }
    }
    cout<<num.top()<<endl;
    return 0;
}

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

思路：先定义一个int型的栈和一个char型的栈分别来存放操作数和运算符，然后将输入的数据转换后存入int型栈中，将运算符存入char型栈中，若是空栈则可直接push，非空的话要考虑运算符的优先级，(‘*’的ASCII码为74，‘+’的ASCII码为75，且乘号的优先级更大一点，所以若是加号先进栈则乘号可以进栈，反之不行)，接着就是将int型栈中的操作数抛出最后进去的两个然后进行运算，再将运算符号和运算结果push到栈里，以此循环来遍历输入的字符串；往下就是对非空栈进行pop，运算和push，最后输出栈顶元素即可。

看完之后，你是否对栈有了一定的了解？

一切关于栈的苦恼便随风消散，你走你的世界，我走有代码的世界！

不要忘了点赞加关注噢！