泉州暑假集训Day 2

c++

编程语言学习记录 c++

发布日期: 2023-07-24

文章字数: 1.4k

阅读次数:

PS: This is a note.

栈

数据结构(DS)

高效的组织数据的一种方式

数组

最简单的数据结构是数组(array): int n[101];

数组属于数据结构中的用顺序结构实现的线性表

注: 线性表是一维的，可以用顺序结构和链式结构实现

栈的使用

栈是一种基本的顺序结构，属于特殊的线性表(操作受限，特性: 后进先出————只能在一端插入和删除)

我们通常把元素插入栈叫做进栈(PUSH),删除栈内元素叫出栈(POP)

栈中可以插入和删除的一段叫栈顶
另一端叫做栈底
用一个指针TOP指向栈顶，若TOP=0，表示栈空，TOP=N时栈满，进栈时TOP加1，退栈时TOP减1。栈指针在运算中永远指向栈顶

实现栈的常用方法

数组模拟栈

STL模拟栈

栈例题

e.g. 后缀表达式求值(洛谷P1449)

#include <bits/stdc++.h>
using namespace std;
stack<int> sta;
//运用STL中的栈可能超时，当遇到过大的元素时应用数组
string s;
int main()
{
	int temp=0,x,y;
	cin>>s;
	for(int i=0; i<s.size(); i++) {
		if(s[i]>='0'&&s[i]<='9') {
			temp=temp*10+s[i]-'0';
		}
		if(s[i]=='@')
		{
			break;
		}
		else if(s[i]=='.') {
			sta.push(temp),temp=0;
		}
		if(s[i]=='+') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y+x);
		}
		if(s[i]=='-') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y-x);
		}
		if(s[i]=='*') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y*x);
		}
		if(s[i]=='/') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y/x);
		}
	}
	cout<<sta.top();
	return 0;
}

e.g. 中缀表达式转后缀表达式

解法: 稀土掘金

队列(queue)

1. 定义

队列(queue)属于线性表,是一种容器转换器模板,调用#include <queue>即可使用队列类

2.初始化

queue<Type, Container> (<数据类型，容器类型>)

初始化时必须要有数据类型，容器类型可省略，省略时则默认为deque 类型

初始化示例

queue<int>q1;
queue<double>q2;  
queue＜char＞q3；
//默认用deque容器实现的queue；

queue＜char, list＜char＞＞q1；
//用list容器实现的queue 

queue＜int, deque＜int＞＞q2；
 //用deque容器实现的queue

注意：不能用vector容器初始化queue
因为queue转换器要求容器支持front()、back()、push_back()及pop_front(),说明queue的数据从容器后端入栈而从前端出栈。所以可以使用deque和list对queue初始化，而vector由于缺少pop_front(),不能用于queue。