栈与队列

栈(stack)是一种特殊的线性表，只能从一端进行插入或者删除操作。这一端被称为栈顶，另一端被称为栈底，栈的特点是后进先出（Last In First Out）

栈操作

stack<int> sta;//定义一个栈

sta.push(x);//向栈顶放入一个 x

cout<<sta.top();//查看栈顶

sta.pop();//丢出栈顶

cout<<sta.size();//查看栈的大小

cout<<sta.empty();//查看栈是否为空

//以上操作复杂度均为O(1)

使用数组模拟栈

int sta[1000],int top=0;

sta[++top]=x;//入栈

cout<<sta[top];//查看栈顶
z
top--;//出栈

cout<<top;//查看栈的大小
//以上操作复杂度均为O(1)

习题：

B.小鱼的数字

C.括号匹配问题

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		stack<char> sta;
		cin>>s;
		bool flag=1;//初始1：可以匹配    变成0 ：不匹配 
		for(int j=0;j<s.length();j++){
			if(s[j]=='('||s[j]=='['){
				//直接入栈 
			}
			else{
				if(sta.size()!=0&&sta.top()=='('&&s[j]==')'||sta.size()!=0&&sta.top()=='['&&s[j]==']'){
				//栈顶出栈 
				}
				else{
				//标记序列不匹配 
				}
			}
		}
		if(sta.size()==0&&flag==1) cout<<"Yes\n";
		else cout<<"No\n";
	}
} 

队列

queue

和栈不同，队列是只能从一端进入，从另一端出去的数据结构

队列操作

queue<int> que;//定义一个存储int类型的队列 名字叫 que

que.push(x);//在队列中加入一个数字

que.front();//返回队列最前面的数字

que.pop();//丢掉队列最前面的数字

que.size();//返回队列里的大小

que.empty();//返回布尔值，是否为空
//以上操作复杂度均为O(1)

除了只有一端能进入，一端能出去的队列，还有两端都能进出的队列

双端队列

deque

deque<int> dq;//定义

dq.push_back(x);//在队尾操作
dq.pop_back();

dq.push_front(x);//在队首操作
dq.pop_front();

dq.size();//查询队列大小
dq.empty();
//以上操作复杂度均为O(1)

习题

D.周末舞会

#include<bits/stdc++.h>
using namespace std;
int main(){
	queue<int> a,b;
	int n,m;cin>>n>>m;
	int k;cin>>k;
	for(int i=1;i<=n;i++){
		a.push(i);
	}
	for(int j=1;j<=m;j++){
		b.push(j);
	}
	for(int i=1;i<=k;i++){
		int pa=a.front();
		int pb=b.front();
		cout<<pa<<" "<<pb<<"\n";
		a.pop();
		b.pop();
		a.push(pa);
		b.push(pb) ;
	}
}

E.约瑟夫问题

优先队列

priority_queue

优先队列是一种特殊的队列，它的本质是一个大顶堆

priority_queue<int> que;

que.push(x);

que.top();
que.pop();

que.size();

习题

F.合并果子