c++基础数据结构之栈、队列、链表

c++基础数据结构之栈、队列、链表

队列

1
2
3
4
5
6
7
queue<int>q //queue<定义类型>定义名称
q.pop()//出队
q.push()//入队
q.front()//队首
q.rear()//队尾
q.size()//队长(队长可以为0)
q.empty()//是否为空队(若是则返回1)

栈

1
2
3
4
5
6
stack<int>st
st.pop()//出栈
st.push()//入栈
st.top()//栈顶
st.size()//栈长
st.empty()//判断是否为空栈

1.单链表(注意结构体写法)

题目描述

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

https://www.ixigua.com/7241418740699824643

输入格式

第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令可能为以下几种：

(1) “H x”，表示向链表头插入一个数x。

(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。

(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例 复制

1
2
3
4
5
6
7
8
9
10
11
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例 复制

1
6 4 6 5

题解

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
using namespace std;
struct node { //建立了一个对象
    int num; //节点值
    int time; //第几次插入
    node* next; //定义下一个节点的指针位置
};
node* head = new node();//创建一个新对象叫head
void headin(int n,int i){
    node* p=new node();//创建一个新节点
    p->num=n;//把值输入节点中，箭头写法表示对象的属性
    p->time=i;//这是次数

    //下面就是插入模板操作
    p->next=head->next;
    head->next=p;
}
void de(int t){
    node* p, * q;//定义两个节点
    p=head->next;//p为指向head的下一个节点
    if(!t){
        head->next=p->next;//head指的是头，里面没值，所以实际的链表头是p
        delete(p);//p是实际头节点
    }
    else{
        while(p){//找到第t次插入的数
            if(p->time==t)break;
            p=p->next;
        }
        q=p->next;//让q在p的前面，辅助删除p后面的节点
        p->next=q->next;
        delete(q);//删除q
    }
}
void insert(int t,int n,int i){
    node* p=head->next; //让p指针指向head的下一个，然后用p节点找欲插入的值
    //下面三行是创建新节点然后给其赋值的操作
    node* q=new node();
    q->num=n;
    q->time=i;
    //从链表头开始找
    while(p){
        if(p->time == t)break;//找第t次插入的数
        p=p->next;
    }
    //把q节点插到第t次插入的数后面
    q->next=p->next;
    p->next=q;
}

int main(){
    head->next=NULL;//开始时链表没有值
    int m,i,x,k;
    char op;
    i=1;
    cin>>m;
    while(m--){
        cin>>op;
        if(op=='H'){
            cin>>x;
            headin(x,i);
            i++;
        }
        if(op=='D'){
            cin>>k;
            de(k);
        }
        if(op=='I'){
            cin>>k>>x;
            insert(k,x,i);
            i++;//因为题目是记录第几次插入的数，所以要用i计数
        }            
    }
    node* p = head->next;//让p指向实际头节点
    while(p){
        cout<< p->num << ' ';
        p=p->next;
    }
}

2.简单计算器

题目描述

读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

https://www.ixigua.com/7213692123635024436

输入格式

每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。

100 * 2 + 100 / 2 - 100 * 2 - 4 / 2

输出格式

对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

输入样例 复制

1
4 + 2 * 5 - 7 / 11

输出样例 复制

1
13.36

题解

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<stack>
using namespace std;
stack<double>d_st;
stack<char>op_st;

int level(char a){
    if(a=='+'||a=='-')return 1;
    if(a=='*'||a=='/')return 2;
}
void cal(){
    char c=op_st.top();op_st.pop();
    double a,b;
    a=d_st.top();
    d_st.pop();
    b=d_st.top();
    d_st.pop();
    if(c=='+')d_st.push(b+a);
    if(c=='-')d_st.push(b-a);
    if(c=='*')d_st.push(b*a);
    if(c=='/')d_st.push(b/a);
}
int main(){
    string str;
    double x;
    getline(cin,str);
    int len=str.size();
    for(int i=0;i<len;i++){
        if(str[i]>='0' && str[i]<='9'){//如果是数字
            x=str[i]-'0'; 
            while(str[i+1]>='0' && str[i+1]<='9'){
                x=x*10+str[i+1]-'0';
                i++;
            }
            d_st.push(x);//把字符串数字转化为整型并推入栈
        }
        else if(str[i]=='+' || str[i]=='-' || str[i]=='*' || str[i]=='/'){
            if(op_st.empty()||level(str[i])>level(op_st.top())){//只有优先级高于栈顶的情况才能入栈
                op_st.push(str[i]);
            }
            else if(!op_st.empty() && level(str[i])<=level(op_st.top())){
                while(!op_st.empty() && level(str[i])<=level(op_st.top())){//拿栈顶前两个计算
                    cal();
                }
                op_st.push(str[i]);           
            }
        }
    }
    while(!op_st.empty()){
        cal();
    }
    printf("%.2lf",d_st.top());
}

3.约瑟夫环(队列解法)

题目描述

有ｎ(n<100)个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出列的顺序。

输入格式

n和m。

输入样例

1
4 17

输出样例

1
1 3 4 2

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<queue>
using namespace std;
int main(){
    queue<int>qe;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        qe.push(i);
    }
    while(!qe.empty()){
        int x;
        for(int i=1;i<=m-1;i++){
            x=qe.front();
            qe.pop();qe.push(x);//把队头放到对尾
        }
        x=qe.front();qe.pop();//数到的数彻底出队
        cout<<x<<" ";
    }
}

4.走出迷宫(bfs)

题目描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。

视频讲解：https://www.ixigua.com/7166253132702450212

输入格式

第一行是两个整数n和m(1≤n,m≤100)，表示迷宫的行数和列数。

接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。

输出格式

输出从起点到出口最少需要走的步数。

输入样例

1
2
3
4
3 3
S#T
.#.
...

输出样例

1
6

题解

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
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<queue>
using namespace std;
char a[105][105];
int vis[105][105];
int n,m;
struct node{
    int r,c;
    int step;
};

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void bfs(int sr,int sc,int er,int ec){
    queue<node>qe;//注意定义方式
    node q,t;//t用来记录q的一圈4个方向
    q.r=sr,q.c=sc;
    q.step=0;
    qe.push(q);
    vis[q.r][q.c]=1;
    while(!qe.empty()){
        q=qe.front();
        qe.pop();
        if(q.r==er && q.c==ec){
            cout<<q.step;
            break;
        }
        for(int i=0;i<4;i++){
            t.r=q.r+dir[i][0];
            t.c=q.c+dir[i][1];
            if(a[t.r][t.c]=='.' && vis[t.r][t.c]==0 && t.r>=1&&t.r<=n && t.c>=1&&t.c<=n){
                t.step=q.step+1;
                vis[t.r][t.c]=1;
                qe.push(t);
            }
        }
    }
}

int main(){
    int sr,sc,er,ec;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
        if(a[i][j]=='S')sr=i,sc=j;
        if(a[i][j]=='T')er=i,ec=j,a[i][j]='.';
    }
    bfs(sr,sc,er,ec);
}

5.出入栈判断

题目描述

现有 a∼z 26 个小球模拟出入栈操作，小球按照 a∼z 的顺序压入栈，在栈顶的元素可以随时被取出，在游戏开始前给出任意 26 个字母的一些排列，问是否能够由出栈顺序得到这个排列。

输入格式

输入第一行表示一个整数n, n<=100

接下来输入n行，每行表示一个a~z的排列。

输出格式

每组数据输出一行结果，如果能够由出栈顺序得到给定排列，则输出 yes，否则输出 no。

输入样例 复制

1
2
3
2
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxy

输出样例 复制

1
2
yes
no

数据范围与提示

5
abcdegfhijklnmopqrstuvwxyz
abcdegfhijklnmopqrstzyxwvu
dcbaegfhijklnmopqrstuvwxyz
abcdegfhijkwxyzlnmopqrstuv
abcdegfhijklnmouvwxyztsrqp

yes
yes
yes
no
yes

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int main(){
    stack <char> st;
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        int len=s.size(),j=0;
        for(int i=0;i<len;i++){
            char ch=i+'a';
            st.push(ch);
            while(!st.empty() && st.top()==s[j]){
                st.pop(),j++;
            }
 
        }
        if(j==len)cout<<"yes\n";
        else cout<<"no\n";
    }
}
#算法
c++基础数据结构之栈、队列、链表
https://bayeeaa.github.io/2024/04/18/c-基础数据结构之栈、队列/
Author
Ye
Posted on
April 18, 2024
Licensed under