算法随笔（2）：信友队集训营--2--数据结构与STL

邹璟豪 · 2023 年7 月 13 日 06:01

算法随笔（2）：信友队集训营–2–数据结构与STL

超级干货，注意食用时配水，以防噎s
在c++中，有很多的数据结构需要自己来实现，such as:用数组模拟栈，用数组模拟队列等。

这些操作都过于繁琐且麻烦了，因此，c++推出了STL

栈

栈(stick)又称堆栈，是只能在一端插入和删除的特殊线性表。具有先进后出的特性

stack的定义

stack <typename> st;

for example:
stack <int> st;
stack <long long> st;
stack <double> st;

常用函数

push(x);//将x入栈，O（1）
pop();//将栈顶元素弹出，O（1）
top();//获取栈顶元素，O（1）
empty();//判断栈是否为空，注意返回值是bool类型的，true为空，false为非空O（1）
size();//返回栈内元素个数，O（1）

（典型例子）A case in point

验证栈序列

【题目描述】

给出pushed和popped两个序列，取值从一到$n(1≤n≤100000)$

已知入栈序列是pushed，如果出栈序列是popped，则输出Yes，否则No

【输入样例】

5
1 2 3 4 5
3 5 2 4 1

【输出样例】

No

【题目解析】

从左到右遍历，当出栈元素为3时，那么按照入栈序列，3之前的元素都入栈，然后判断此时栈顶的元素就是要出栈的元素3，正常出栈，以此类推。

【正确代码】

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
stack <long long> s;
long long n,a[N],b[N],t;
int main()
{
	cin>>t;
	for(long long u=1;u<=t;u++)
	{
		cin>>n;
		for(long long i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(long long i=1;i<=n;i++)
		{
			cin>>b[i];
		}
		long long uu=1,oo=1;
		bool b1=false;
		while(uu<=n)
		{
			while(s.empty() ||  (s.top()!=b[uu] && oo<=n))
			{
				s.push(a[oo]);
				oo++;
			}
			if(!s.empty() && s.top()==b[uu])
			{
				s.pop();
				uu++;
			}else
			{
				cout<<"No\n";
				b1=true;
				break;
			}
		}
		if(b1==false)
		{
			cout<<"Yes\n";
		}
	}
}

队列

队列（queue），遵循先进先出的原则，队列只能从表的一端进入队列，再从另一端弹出

queue的定义

queue <typename> q;

for example:
queeu <long long> q;
queue <int> q;
queue <uuu> q;
queue <double> q;
queue <float> q;

queue的函数

clear();//清空队列
push(x);//将元素x压入队列，O（1）
pop();//将队首出队，O（1）
front();//获得队首元素，O（1）
back();//获得队尾元素，O（1）
empty();判断队列是否为空，true为空，false为非空，O（1）
size();//返回队内元素个数

优先队列

优先队列与队列容器一样，都只能从队尾压入元素，从队首弹出

但是，优先队列有个特性，优先队列里的元素总是呈递增或递减的

就是说：

通过优先队列可以快速求极值（最大/最小）

优先队列的定义

priority_queue <int,vector<int>,greater<int> > q;//递增greater函数对象排序，通过q.top()可以访问到一个序列的最小值
priority_queue <int,vector<int>,less<int> > q;//递减less函数对象排序，通过q.top()可以访问到一个序列的最大值，等价于priority_queue <int> q;

优先队列重载运算符

优先队列中元素的比较默认按照从大到小，如果要改变规则需要重载运算符。

struct uuu{
    int x,y;
    friend bool operator < (uuu a,uuu b>
    {
      return a.x>b.x;
    }
};
priority_queue <uuu> q;

优先队列常用函数

push(x);//将x入队
pop();//将队首元素出队
top();//获得优先级最高的元素
empty();//判空，同队列
size();//返回队列内元素个数

双端队列

双端队列可以从队首插入元素也可以队尾插入元素，同时，也可以从队首弹出元素以及从队尾弹出元素

双端队列的定义

deque <typemane> dq;

for example:
deque <int> dq;
deque <long long> dq;
deque <double> dq;

双端队列常用函数

clear();//清空双端队列
push_front(x);//在双端队列的队首插入x
push_back(x);//在双端队列的队尾插入x
front();//获得队首元素
back();//获得队尾元素
pop_front();//将队首元素弹出
pop_back();//将队尾元素弹出
empty();//判断双端队列是否为空
insert(pos.x);//在下标为pos的地方插入x
size();//返回双端队列的元素个数

动态数组

动态数组(vector),就是长度可以根据需要而自动改变的数组

vector的定义

vector <typename> v;

for esample：
vector <int> v;
vector <double> v;
vector <vector<int> > v;//二维vector

vector容器内元素的访问

通过下标访问

for(long long i=0;i<v.size();i++)
{
    cout<<v[i]<<" ";
}

通过迭代器访问

vector <long long>::iterator it;
for(it=v.begin();it!=v.end();it++)
{
    cout<<*it<<" ";
}

vector常用函数

push_back(x);
pop_back(x);
size();
insert(it,x);
erase();
clear();

集合

集合(set)是c++STL中的一种关联式容器，它内部使用红黑树（一种自平衡二叉搜索树）来实现元素的有序存储

特点是：自动去重，自动排序，可以快速查找、插入和删除元素。

set的定义

set <typename> s;

for example:
set <int> s;
set <double> s;
set <set<int> > s;

set容器内元素的访问–迭代器

set <int>::iterator it;
for(it=s.begin();it!=s.end();it++)
{
    cout<<*it<<" ";
}

set常用函数

insert(x);//将x插入set容器中，O（logN）
find(x);//返回set对应值x的迭代器，没有则返回end()，O(logn)
erase(first,last);//删除一个区间内的所有元素，起始迭代器为first，末尾迭代器为last
clear();//清空set
lower_bound(x);//返回第一个大于等于x的元素的迭代器，不存在则返回end();
upper_bound(x);//返回第一个大于x的元素的迭代器，不存在则返回end();
size();//获取set的元素个数
empty();//判断set是否为空
count(x);//计算set中值为x的元素有多少个，因为set会去重，所以只能是0或1

扩展auto

在C++11中，auto关键字可以在声明变量的时候根据变量初始值的了类型自动为此变量选择匹配的类型，

这样，set::iterator it的声明就可以用auto it来代替

for example
set <long long> s{1,2,3,4,5};
for(set <long long>::iterator it=s.begin();it!=s.end();it++)
{
    cout<<*it<<" ";
}
就可以变成
for(suto it=s.begin();it!=s.end();it++)
{
    cout<<*it<<" ";
}
如果再加上for的优化呢
for(auto it:s)
{
    cout<<*it<<" ";
}

映射

map（映射）也是常用的STL容器，它可以将任何基本类型映射到任何基本类型，也就是可以建立string型到int型的映射。如果是int映射int，那就相当于是普通的int型数组。

map的定义

通过一个键来对应一个值。

for example
map <string,int> mp;

map容器内元素的访问–通过键来访问

map一板有两种访问方式：通过键访问或通过迭代器访问

因为map中的元素是键值对，因此可以根据建来调用到值

map容器内元素的访问–通过迭代器访问

map是有两个数据类型的，因此map的迭代器要同时访问键和值：it->first访问键it->second访问值

注意：map是会自动排序的

map常用函数

size();//用来获得map中元素个数，O（1）
find(key);//返回键为key的迭代器，O（logN）
erase();//删除单个元素的迭代器或映射的键
clear();//清空map中的所有元素，O（n）
begin();//map的起始迭代器
end();//map的终止迭代器

在你谷食用食用更佳（doge）

崩坏星穹铁道 · 2023 年8 月 24 日 01:43

我玩锣鼓怎么你了（doge

算法随笔（2）： 信友队集训营--2--数据结构与STL

算法随笔（2）： 信友队集训营–2–数据结构与STL

栈