其实以前学过了，但是感觉不熟悉，考前再系统学习一遍。
建议搭配 2022年8月学习记录 - STL 一起使用。
我的学习资料
NOI官网：队列、栈及其应用
队列
队列的概念及基本术语
队头、队尾、入队、出队：与栈一样，队列(Queue)也是一种运算受限的特殊线性表。但它与栈“在同一端（栈顶）进进出出”不同，队列是从表的一端（队尾rear)入队，从表的另一端（队头front)出队。
栈让元素“先进后出”，而队列则让元素“先进先出”。假设有队列Q(al,a2,a3,…,an),则队列Q中的元素是按al,a2,a3,an的顺序依次入队，也只能按照al,a2,a3,…,an的顺序依次出队。因此，队列也被称作先进先出线性表(FIFO-First In First Out)。
在入队、出队的过程中，队列呈现如下几种状态：
同栈的顺序存储结构一样，队列也可以用数组表示，并设置两个指针：队头指针front:和队尾指针rear。为简化操作，通常约定front指向队头元素的前一个位置，rear就指向队尾元素（也有front就指向队头元素，rear指向队尾元素的后一个位置)
循环队列
1
2
3
4
5
6
7
8
9
|
if(rear+1==M) rear=0;
q[rear]=x;
rear=(rear+1)%M;
x=q[front];
front=(front+1)%M;
|
栈
栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶(op),相应地，表头端称为栈底(bottom)。
栈的特征：
栈的存储：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
datatype s[n];
int top;
bool sempty(int top){
return top==0;
}
bool sfull(int top){
return top==n;
}
top=0;
for(!sfull(top)){
top++;
s[top]=x;
}else{
cout<<"overflow"<<endl;
}
if(!sempty(top)){
x=s[top];
top--;
}else{
cout<<"underfloe"<<endl;
}
if(!sempty(top)){
x=s[top];
}else{
cout<<"underfloe"<<endl;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<iostream>
using namespace std;
int main(){
int m=0,n=0,k=0;
cin>>m>>n>>k;
int a[m+2],b[n+2];
for(int i=1;i<=m;i++) a[i]=i;
for(int i=1;i<=n;i++) b[i]=i;
int f1=1,r1=m,f2=1,r2=n;
while(k>0){
cout<<a[f1]<<" "<<b[f2]<<endl;
r1++; a[r1]=a[f1]; f1++;
r2++; b[r2]=b[f2]; f2++;
k--;
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
| #include<iostream>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<k;i++){
cout<<(i%n+1)<<" "<<(i%m+1)<<endl;
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
using namespace std;
int a[10000010];
int main(){
int n=0;
cin>>n;
if(n<1||n>10000000){
cout<<-1<<endl;
return 0;
}
for(int i=0;i<n;i++){
a[i]=i+1;
}
int front=0,rear=n;
while(front!=rear){
front=(front+1)%(n+1);
a[rear]=a[front];
front=(front+1)%(n+1);
rear=(rear+1)%(n+1);
}
cout<<a[(front-2)%(n+1)]<<endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<iostream>
using namespace std;
const int MAXN = 100010;
int a[MAXN];
int result[MAXN];
int main(){
int K=0, N=0, P=0;
cin >> N >> K >> P;
if(P<1 || P>10 || N<2 || N>100 || K<N || K> 100000){
cout<<-1<<endl;
return 0;
}
int front = 1,rear = K;
for (int i = 1; i <= K; i++) a[i] = i;
int x = 0;
for (int i = 1; i <= K; i++){
x++;
if (x % N == 0) result[a[front]] = a[front];
a[front] = NULL;
front = (front + 1) % MAXN;
if (front == rear + 1)break;
for (int j = 1; j <= P; j++){
rear = (rear + 1) % MAXN;
a[rear] = a[front];
a[front] = NULL;
front = (front + 1) % MAXN;
}
}
for (int i = 1; i <= K; i++) {
if(result[i]) cout<<result[i]<<endl;
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<iostream>
using namespace std;
int main(){
int n=0,j=1;
cin>>n;
if(n<=0){
cout<<-1<<endl;
return 0;
}
int a[n+2]={0,1};
for(int i=2;i<=n;i++){
int p=i;
if(i>n/2&&i<n)p=(i+1)%(n-i+1)-1;
if(p!=-1)for(int k=0;k<=p;k++){
do{
j++;
if(j>n)j=1;
}while(a[j]!=0);
}
if(p==-1){
do{
j--;
if(j<1)j=n;
}while(a[j]!=0);
}
a[j]=i;
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<iostream>
using namespace std;
int m=0,n=0,top=0;
char s[1002];
string str="";
int main(){
while(getline(cin,str)){
top=0;
for(int i=0;i<str.size();i++){
switch(str[i]){
case '#':{
if(top==0){
break;
}
top--;
break;
}
case '@':{
top=0;
break;
}
default:{
top++;
s[top]=str[i];
break;
}
}
}
for(int i=1;i<=top;i++){
cout<<s[i];
}
cout<<endl;
}
return 0;
}
|
微信
