【数据结构】栈

博主： Fivk
发布时间：2021 年 07 月 11 日
974 次浏览
468字数
分类：数据结构

# 栈的基础介绍

栈只是能再某一端插入和删除的特殊线性表。

用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。

栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进站（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）。

一个栈可以用定长为n的数组s来表示，用一个栈指针top指向栈顶。若top=0，表示栈空，top=n时栈满。进栈时top加1，退栈时top减1。当top<0时为下溢。栈指针在运算中永远指向栈顶。

![](https://blog.fivk.cn/usr/uploads/2021/07/2645896254.png)

**1.进栈（PUSH）算法**

1. 若top>=n时，则会给出溢出信息，作出错误处理（进栈前首先检查栈是否已满，满则溢出;不满则操作2）;
2. top++（栈指针加1，指向进栈地址）;
3. s[top]=x，结束（x为新进栈的元素）。

**2.退栈（pop）算法**

1. 若top<=0，则给出下溢信息，作出错误处理（退栈前先检查是否已为空栈，空则下溢;不空则操作2）;
2. x=s[top]，（退栈后的元素赋给x）;
3. top--，结束（栈指针减1，指向栈顶）。

**进栈、出栈的C++实现过程程序：**

```cpp
#define n 100
void push(int s[],int *top,int *x)	//入栈
{
	if(*top==n)
		printf("overflow\n");
	else
	{
		(*top)++;
		s[*top]=*x;
	}

}

void pop(int s[],int *y,int *top)	//出栈
{
	if(*top==0)
		printf("underflow\n");
	else
	{
		*y=s[*top];
		(*top)--;
	}
}
```

对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来做为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。

**堆栈的数组模拟**

十进制数n和其他d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一种算法原理：

n=(n/d)*d+n%d

（其中/为整除运算，%为求余运算）。

</div>

例如：$(1348)_{10}=(2504)_{8}$运算过程如下：

| n    | n/8 | n%8 |
| ------ | ----- | ----- |
| 1348 | 168 | 4   |
| 168  | 21  | 0   |
| 21   | 2   | 5   |
| 2    | 0   | 2   |

**数制转化参考程序**

```cpp
#include<cstdlib>
#include<iostream>
using namespace std;
#define SIZE 100
int a[SIZE+1],n,d,i=0,j;

int main()
{
	cout<<"Please enter a number(N) base 10:";
	cin>>n;
	cout<<"Please enter a number(d):";
	cin>>d;

do{
		a[++i]=n%d;
		n/=d;

}while(n!=0);

for(j=i;j>=1;j--) cout<<a[j];

return 0;
}
```

![运行过程](https://blog.fivk.cn/usr/uploads/2021/07/1632824774.png)

# 经典例题

### 例1.1 括号的匹配(表达式的合法性检查)

【问题描述】

假设一个表达式由英文字母(小写)、运算符(+、一、* 、/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配，则返回“YES";否则返回“NO”。假设表达式长度小于255,左圆括号少于20个。

假设输入的字符串存储在c中(char c[256])。我们可以定义一个栈:

char s[ maxn＋1];

int top;

用它来存放表达式中从左往右的左圆括号(maxn=20)。
算法的思路为:顺序(从左往右)扫描表达式的每个字符c[i,若是“(”,则让它进栈;若遇到的是“)”,则让栈顶元素出栈;当栈发生下溢或当表达式处理完毕而栈非空时,都表示不匹配,返回“NO”;否则表示匹配,返回“YES”。

```cpp
#include<cstdio>
#include<cstdlib>
#define MAXN 20
using namespace std;
char c[256];

bool judge(char c[])
{
    int top = 0, i=1;
    while(c[i]!='@')
    {
        if(c[i]=='(') top++;
  
        if(c[i]==')')
        {
            if(top>0) top--;
            else return 0;
        }
        i++;
    }
    if(top!=0) return 0;    //检查栈是否为空。不空则说明有未匹配的括号
    else return 1;
}

int main()
{
    gets(c);
    if(judge(c)) printf("YES");
    else printf("NO");
    system("pause");
    return 0;
}
```

### 例1.2 编程求一个后缀表达式的值

【问题描述】

从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加(＋)、减(一)乘( * )、除(/)四种运算符。每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。以@作为结束标志。

后缀表达式的处理过程很简单,过程如下:扫描后缀表达式,凡遇操作数则将之压进堆栈,遇运算符则从堆栈中弹出两个操作数进行该运算,将运算结果压栈,然后继续扫描,直到后缀表达式被扫描完毕为止,此时栈底元素即为该后缀表达式的值。

比如,16-9 *(4＋3)转换成后缀表达式为:16⚪9⚪4⚪3⚪+ * -,在字符数组A中的形式为:

![](https://blog.fivk.cn/usr/uploads/2021/07/2004926767.png)

栈中的变化情况：

![](https://blog.fivk.cn/usr/uploads/2021/07/2734625845.png)

运行结果：-47

```in
16 9 4 3 +*-@
```

```cout
-47
```

书上参考代码：

```cpp
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
using namespace std;

int stack[101];
char s[256];

int comp(char s[])
{
    int i=0,top=0,x,y;

while(i<=strlen(s)-2)
    {
        switch(s[i])
        {
            case '+':stack[--top] += stack[top+1];break;
            case '-':stack[--top] -= stack[top+1];break;
            case '*':stack[--top] *= stack[top+1];break;
            case '/':stack[--top] /= stack[top+1];break;
            default:
            x=0;
            while(s[i]!=' ') x=x*10+s[i++]-'0';
            stack[++top]=x;
            break;
        }
        i++;
    }
    return stack[top];
}

int main()
{
    printf("input a string(@_over):");
    gets(s);
    printf("result=%d\n",comp(s));
    system("pause");
    return 0;
}
```

使用stack容器：

最后不用输入@

```cpp
#include<iostream>
#include<stack>
#include<string>
using namespace std;

stack<long long> s;
string str;

int main()
{
    getline(cin,str);

for(int i=0;i<str.length();i++)
    {
        if(str[i]=='+')
        {
            long long temp=s.top();
            s.pop();
            s.top()+=temp;
        }else if(str[i]=='-')
        {
            long long temp=s.top();
            s.pop();
            s.top()-=temp;
        }else if(str[i]=='*')
        {
            long long temp=s.top();
            s.pop();
            s.top()*=temp;
        }else  if(str[i]=='/')
        {
            long long temp=s.top();
            s.pop();
            s.top()/=temp;
        }else if(str[i]>='0'&&str[i]<='9')
        {
            long long x=0;
            while(str[i]!=' ')
            x=x*10+str[i++]-'0';
            s.push(x);
        }

}
    cout<<s.top()<<endl;
    system("pause");
    return 0;
}
```

### 例1.3车厢调度

【问题描述】

有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有n节(n<=1000),分别按照顺序编号为1,2,3,…,n。假定在进人车站前,每节车厢之间都不是连着的,并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C,它就不能再回到A方向的铁轨上了,并且一旦当它进入B方向的铁轨,它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使它以al，a2,…, an 的顺序从B方向驶出,请你来判断能否得到指定的车厢顺序。

![](https://blog.fivk.cn/usr/uploads/2021/07/3038377298.png)

【输入】

输入文件的第一行为一个整数n,其中n< =1000,表示有n节车厢,第二行为n个数字,表示指定的车厢顺序。
【输出】

如果可以得到指定的车厢顺序,则输出一个字符串”YES",否则输出”NO”(注意要大写,不包含引号)。

该题就是前面思考题的一部分。车站C相当于一个栈。我们用模拟法来做,假设我们已经处理了前i-1节从B方向驶出的车厢,我们现在要让ai驶出。若ai不在车站C中,我们就让若干车厢从A方向驶入车站C,直到 ai驶入,再将它从B方向驶出;若ai在车站C中,如果它是车站C中停在最前面的,则将它从B方向驶出,否则原问题无解。
如样例中,出栈序列是**35421**,模拟过程如下:

1. 一开始栈为空;
2. 由于3不在栈中,就需要把1,2,3依次进栈,再出栈,这样符合出栈序列第一个数是3,当前栈为{1,2};
3. 第2个出栈的是5,5不在栈中,就要把4,5压栈,再出栈就可以得到5,此时栈为{1，2,4};
4. 第3个出栈的是4,正好是栈顶元素,直接出栈,栈变为{1,2};
5. ⑤、第4个出栈的是2,正好是栈顶元素,直接出栈,栈变为{2};
6. 第5个出栈的是1,正好是栈顶元素,直接出栈,栈变为{得}。
   在模拟过程中没有碰到要出栈的数在栈中但不是栈顶元素的情况,所以该方案可行。

```in
3 5 4 2 1
```

```out
YES
```

书上参考代码：

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int stack[N],a[N];
int top,n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    top=0;
    for(int i=1,cur=1;i<=n;i++)
    {
        while(cur<=a[i])
        stack[++top]=cur++;
        if(stack[top]==a[i])
            top--;
        else{
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    system("pause");
    return 0;
}
```

使用stack容器：

换汤不换药

```cpp
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 1010;
int a[N];
stack<int> s;
int top,n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    top=0;
    for(int i=1,cur=1;i<=n;i++)
    {
        while(cur<=a[i])
        s.push(cur++);
        if(s.top()==a[i])
            s.pop();
        else{
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    system("pause");
    return 0;
}
```

最后修改：2021 年 09 月 12 日

如果觉得我的文章对你有用，请随意赞赏

【数据结构】栈

Fivk • 2021 年 07 月 11 日

# 栈的基础介绍

栈只是能再某一端插入和删除的特殊线性表。

用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。

![](https://blog.fivk.cn/usr/uploads/2021/07/2645896254.png)

**1.进栈（PUSH）算法**

**2.退栈（pop）算法**

**进栈、出栈的C++实现过程程序：**

```cpp
#define n 100
void push(int s[],int *top,int *x)	//入栈
{
	if(*top==n)
		printf("overflow\n");
	else
	{
		(*top)++;
		s[*top]=*x;
	}

}

void pop(int s[],int *y,int *top)	//出栈
{
	if(*top==0)
		printf("underflow\n");
	else
	{
		*y=s[*top];
		(*top)--;
	}
}
```

**堆栈的数组模拟**

十进制数n和其他d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一种算法原理：

n=(n/d)*d+n%d

（其中/为整除运算，%为求余运算）。

</div>

例如：$(1348)_{10}=(2504)_{8}$运算过程如下：

| n    | n/8 | n%8 |
| ------ | ----- | ----- |
| 1348 | 168 | 4   |
| 168  | 21  | 0   |
| 21   | 2   | 5   |
| 2    | 0   | 2   |

**数制转化参考程序**

```cpp
#include<cstdlib>
#include<iostream>
using namespace std;
#define SIZE 100
int a[SIZE+1],n,d,i=0,j;

int main()
{
	cout<<"Please enter a number(N) base 10:";
	cin>>n;
	cout<<"Please enter a number(d):";
	cin>>d;

do{
		a[++i]=n%d;
		n/=d;

}while(n!=0);

for(j=i;j>=1;j--) cout<<a[j];

return 0;
}
```

![运行过程](https://blog.fivk.cn/usr/uploads/2021/07/1632824774.png)

# 经典例题

### 例1.1 括号的匹配(表达式的合法性检查)

【问题描述】

假设输入的字符串存储在c中(char c[256])。我们可以定义一个栈:

char s[ maxn＋1];

int top;

```cpp
#include<cstdio>
#include<cstdlib>
#define MAXN 20
using namespace std;
char c[256];

int main()
{
    gets(c);
    if(judge(c)) printf("YES");
    else printf("NO");
    system("pause");
    return 0;
}
```

### 例1.2 编程求一个后缀表达式的值

【问题描述】

比如,16-9 *(4＋3)转换成后缀表达式为:16⚪9⚪4⚪3⚪+ * -,在字符数组A中的形式为:

![](https://blog.fivk.cn/usr/uploads/2021/07/2004926767.png)

栈中的变化情况：

![](https://blog.fivk.cn/usr/uploads/2021/07/2734625845.png)

运行结果：-47

```in
16 9 4 3 +*-@
```

```cout
-47
```

书上参考代码：

```cpp
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
using namespace std;

int stack[101];
char s[256];

int comp(char s[])
{
    int i=0,top=0,x,y;

int main()
{
    printf("input a string(@_over):");
    gets(s);
    printf("result=%d\n",comp(s));
    system("pause");
    return 0;
}
```

使用stack容器：

最后不用输入@

```cpp
#include<iostream>
#include<stack>
#include<string>
using namespace std;

stack<long long> s;
string str;

int main()
{
    getline(cin,str);

}
    cout<<s.top()<<endl;
    system("pause");
    return 0;
}
```

### 例1.3车厢调度

【问题描述】

![](https://blog.fivk.cn/usr/uploads/2021/07/3038377298.png)

【输入】

输入文件的第一行为一个整数n,其中n< =1000,表示有n节车厢,第二行为n个数字,表示指定的车厢顺序。
【输出】

如果可以得到指定的车厢顺序,则输出一个字符串”YES",否则输出”NO”(注意要大写,不包含引号)。

```in
3 5 4 2 1
```

```out
YES
```

书上参考代码：

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int stack[N],a[N];
int top,n;

使用stack容器：

换汤不换药

```cpp
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 1010;
int a[N];
stack<int> s;
int top,n;

【数据结构】栈

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【探花交友】Dubbo基础知识

【项目实战】瑞吉外卖-day06

【C】文件_文件块的读写( fwrite ，ferad)

[函数快查] ferror -- 检测文件的错误指示器是否被设置

【项目实战】小兔鲜儿Vue3企业级项目

【数据结构】栈