数据结构--【栈与队列】笔记

发布于:2025-03-14 ⋅ 阅读:(26) ⋅ 点赞:(0)

栈的应用【实验题】

使用栈实现后缀表达式计算,其中,在后缀表达式中,输入的数字为整数,且为正数,数字、符号之间用空格隔开,整个后缀表达式用“#”表示结束。其中,整个后缀表达式长度不超过200,每个数字位数不超过10。

提示:读取数据的过程中,可以利用栈处理每个数字。

输入样例:

11 2 3 + * #(注:对应的中缀表达式是11*(2+3))

6 2 3 + * 5 / 7 - #(注:对应的中缀表达式是6*(2+3)/5-7)

输出样例:

55

-1

#include<iostream>
#include<string>
using namespace std;
struct stack
{
	int a[300];
	int index = -1;
	void instack(int x)  //入栈操作
	{
		a[++index] = x;
	}
	void calculate(char k)  //k是运算符
	{
		int sum = 0;
		int k1, k2;
		k1 = showtop(); outstack();
		k2 = showtop(); outstack();
		if (k == '+')
		{
			sum = k1 + k2;
		}
		else if (k == '-')
		{
			sum = k2 - k1;
		}
		else if (k == '*')
		{
			sum = k1 * k2;
		}
		else if (k == '/')
		{
			sum = k2 / k1;
		}
		instack(sum);
	}
	void outstack() //出栈
	{
		index--;
	}
	int showtop()  //显示栈顶字符
	{
		return a[index];
	}
};
int main()
{
	stack f;
	string b;
	while (cin >> b && b != "#")
	{
		if (b == "+" || b == "-" || b == "*" || b == "/")
		{
			f.calculate(b[0]);
		}
		else
		{
			int num = stoi(b);
			f.instack(num);
		}
	}
	cout << f.showtop() << endl;
	return 0;
}

整体还是很简单的,主要操作步骤如下

1.写一个栈的结构,这里面设置栈结构(a[]数组),index索引指向目前栈顶,并包含入栈、出栈、显示栈顶字符操作

2.输入字符

3.写运算calculate函数

要注意的问题是cin可以隔断输入的string b,此时比如单个输入的"11"就是要给字符串b

string b;
	while (cin >> b && b != "#")
	{
		if (b == "+" || b == "-" || b == "*" || b == "/")
		{
			f.calculate(b[0]);
		}
		else
		{
			int num = stoi(b);
			f.instack(num);
		}
	}

同时calculate()也可以用switch写,更简洁一些

 void calculate(char k) {
        int right = a[index--]; // 右操作数(栈顶)
        int left = a[index--];  // 左操作数(次栈顶)
        int sum = 0;
        switch(k) {
            case '+': sum = left + right; break;
            case '-': sum = left - right; break;
            case '*': sum = left * right; break;
            case '/': sum = left / right; break; // 修正为 left / right
        }
        a[++index] = sum; // 结果入栈
    }

单调栈

这是种特殊的栈结构,其元素按照单调递增或单调递减的顺序排列

普通暴力方法是 O(n²) ,这个可以优化至 O(n)。

典型例题:

P5788 【模板】单调栈 - 洛谷

题目描述

给出项数为 n 的整数数列 a1…n​。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai​ 的元素的下标,即 f(i)=mini<j≤n,aj​>ai​​{j}。若不存在,则 f(i)=0。

试求出 f(1…n)。

输入格式

第一行一个正整数 n。

第二行 n 个正整数 a1…n​。

输出格式

一行 n 个整数表示 f(1),f(2),…,f(n) 的值。

输入输出样例

输入 

5
1 4 2 3 5

输出 

2 5 4 5 0

说明/提示

【数据规模与约定】

对于 30% 的数据,n≤100;

对于 60% 的数据,n≤5×103 ;

对于 100% 的数据,1≤n≤3×106,1≤ai​≤109。

整体做法就是,用栈来存储索引值,先从前往后遍历数列,遇到第 i 个元素 x ,让它和栈顶元素比较

  • 如果栈顶元素小于它,就把栈顶元素踢出去,索引值 i 成为栈顶,此时栈顶索引对应的那个第一个比它大的索引就是 i 。
  • 如果栈顶元素大于等于它,保存原来栈顶那个元素,把 i 直接加进来。

这样就形成了一个单调递减的栈,遍历每一个元素,后面的元素如果比它前面那个小就会进去待命,反正前面那个大数的结果不是后面那个小数,它只会在遇到比它大的数的时候才会找到答案,此时前面那堆小的答案也是那个新遇到的大数,所以就叽里咕噜全跑出栈来了。

还有一个比较形象的例子,这个题就好像是很多人同时向右看,求看到第一个比自己高的人的那个位置

为什么可以将复杂度降到 O(n)?

我想这是一个一边遍历数组一边比大小的过程,因为在遍历数组的同时本身就形成了一个递减的顺序,所以能够同时遍历数组 + 比大小,高

#include<iostream>
using namespace std;
int res[3000000]; //盛放答案  res[1]的值是第一个大于首元素的元素索引
int st[3000000];  //盛放索引,索引对应的值从大到小排列
int num[3000000]; //盛放原先的数列
int p = 0;  //指针,首元素是1
int main()
{
	int n,x;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		num[i] = x;
	}
	for (int i = 1; i <= n; i++)
	{
		while (p && num[i] > num[st[p]])
//num[st[p]]:表示当前st栈中栈顶元素(索引)对应的那个数值
		{
			int j = st[p];  //设一个整数j存索引值
			p--;
			res[j] = i;//该索引值第一个比它大的索引是i
		}
		p++;
		st[p] = i;  //不管num[i]是大是小都要入栈
	}
	for (int i = 1; i <= n; i++)
		cout << res[i] << " ";
	return 0;
}

出栈顺序判断

P4387 【深基15.习9】验证栈序列 - 洛谷

题目描述

给出两个序列 pushed 和 poped 两个序列,其取值从 1 到 n(n≤100000)。已知入栈序列是 pushed,如果出栈序列有可能是 poped,则输出 Yes,否则输出 No。为了防止骗分,每个测试点有多组数据,不超过 5 组。

输入格式

第一行一个整数 q,询问次数。

接下来 q 个询问,对于每个询问:

第一行一个整数 n 表示序列长度;

第二行 n 个整数表示入栈序列;

第三行 n 个整数表示出栈序列;

输出格式

对于每个询问输出答案。

输入输出样例

输入 

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

输出 

Yes
No

其实是一个模拟出栈过程的题 

#include<iostream>
#include<string.h>
using namespace std;
int push[100000];
int pop[100000];
int q, n;
struct stack 
{
     int st[100000];
	 int ttop = -1;  //top指向当前栈顶元素
	 void popp() { ttop--; }
	 void pushh(int x) { ttop++; st[ttop] = x; }
	 bool isempty() { return ttop == -1 ? 1 : 0; }
	 int top() { return st[ttop]; }
};
bool check()   //模拟出栈过程
{
	int cnt = 0;  //表示pop[]的索引
	stack s;
	for (int i = 0; i < n; i++)
	{
		s.pushh(push[i]);  //入栈
		while (s.top() == pop[cnt])  //当栈顶元素等于pop[cnt]的时候出栈
		{
			cnt++;    //pop[]顺便往后移
			s.popp();   //出栈
			if (s.isempty())   
//如果出完栈以后栈空了,就直接退出,因为原来那个s.top()不会判断栈有没有空,会出现错误
			{
				break;
			}
		}
	}
	if (s.isempty()) return true;
	else return false;
	while (!s.isempty())  //清空栈
	{
		s.popp();
	}

}
int main()
{
	for (cin>>q; q; q--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)  cin >> push[i];
		for (int i = 0; i < n; i++)  cin >> pop[i];
		if (check()) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

 


网站公告

今日签到

点亮在社区的每一天
去签到