学习了队列，栈，链表等数据结构，本质上都是线性表的一种，那么还需要例题来巩固知识点，在此选了5个题。题目地址
题目地址
大概意思：输入一个后缀表达式，然后计算出结果。那么这就是典型的栈的运用，加上一点模拟。
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
stack< int > q;
int x, y, s;
char c;
int main()
{
while (c = getchar()){
switch (c)
{
//遇到运算符就是提取前两位数加减乘除,注意X,Y次序
case‘+‘:x = q.top(); q.pop(); y = q.top(); q.pop(); q.push(y+x);break;
case‘-‘:x = q.top(); q.pop(); y = q.top(); q.pop(); q.push(y-x);break;
case‘*‘:x = q.top(); q.pop(); y = q.top(); q.pop(); q.push(y*x);break;
case‘/‘:x = q.top(); q.pop(); y = q.top(); q.pop(); q.push(y/x);break;
case‘.‘:q.push(s); s = 0; break;
default:s = s * 10 + c - ‘0‘; break;
}
if (c == ‘@‘)
break;
}
cout << q.top() << endl;
}
题目地址
大概意思：n 个人围成一圈，从第一个人开始报数,数到 mmm 的人出列，再由下一个人重新从 111 开始报数，数到 mmm 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
思路：可以想象成一个队列，一个人报完数后，判断他所报的数是不是出局的数，如果是，直接弹出，但若不是，将其移动至队尾。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue< int > q;
int main()
{
int n, outnum, nownum=1;
cin >> n >> outnum;
for (int i = 1; i <= n; i++)
q.push(i);
cout << endl;
while (!q.empty()) {
if (nownum == outnum)
{
cout << q.front() << " ";
nownum = 1;
q.pop();
}
else
{
nownum++;
q.push(q.front());//队首先插到队尾
q.pop();//弹出队首
}
}
cout << endl;
}
题目地址
思路：我们可以设计一个双向链表的数组，用于记录第i个位置上的同学左边和右边的编号，数组本身的编号就是学生编号。
#include<iostream>
#include<cstdio>
using namespace std;
struct student {
int r, l;
}s[100010];
int vis[100010];//判断是否被删除
int main()
{
s[0].l = s[0].r = 1;//0号不会被用到，当作首
s[1].l = s[1].r = 0;
int n, m;
cin >> n;
for (int i = 2; i <= n; i++)
{
int k, p;
//k为操作序号，p为位置
cin >> k >> p;
if (p == 0)//左边插入,注意次序
{
s[s[k].l].r = i;//k左边的右边的元素的右指针指向要插入的学生
s[i].l = s[k].l;//要插入的学生的左指针指向k学生原来的右边
s[k].l = i;//k的左指针指向要插入的学生
s[i].r = k;//要插入的学生的右指针指向k
}
else//反过来即可
{
s[s[k].r].l = i;
s[i].r = s[k].r;
s[k].r = i;
s[i].l = k;
}
}
cin >> m;
for (int i = 1; i <= m; i++)
{
int p;
cin >> p;
if (vis[p] == 1)continue;
else
{
vis[p] = 1;
s[s[p].l].r = s[p].r;//p位置的左边的右边变成原来p的右边
s[s[p].r].l = s[p].l;
}
}
int t = 0;
for (int i = 1; i <= n; i++)
{
if (s[t].r != 0)
{
cout << s[t].r << " ";
t = s[t].r;
}
else
break;
}
}
题目链接
思路：使用vector可以方便解题，依次读如数据，判断是否在内存中（find）。如果不在，就需要查词典，然后加入内存、将答案 + 1。如果内存满了，就把最先进入内存的单词删掉。
或者可以开一个大数组定义一个头指针，查询，插入，头指针向后移。
STL解法
#include<iostream>
#include<cstdio>
#include <vector>
using namespace std;
vector < int > q;
int main()
{
int n, m, ans = 0;
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
if (find(q.begin(), q.end(), t) == q.end())
{
q.push_back(t);
ans++;
}
if (q.size() > m)
//满了将开头地删掉
q.erase(q.begin());
}
cout << ans << endl;
}
数组做法
#include<iostream>
#include<cstdio>
#include <vector>
using namespace std;
int a[100000];
int check(int r, int l, int t)
{
for (int i = r; i <= l; i++)
{
if (a[i] == t)
return 1;
}
return 0;
}
int main()
{
int n, m, ans = 0;
cin >> m >> n;
int head = 0,tail=0;
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
if (check(head, tail-1, t) == 0)
//需要将尾部减去1
{
a[tail] = t;
tail++;
ans++;
}
if ((tail - head) > m)
head++;
}
cout << ans << endl;
}
题目地址
思路：不能记录船，必定TLE。先读进人数，再读进每个人的国籍，把人到来的时间和国籍放进队列。用队列来计算，更新。
#include<iostream>
#include<cstdio>
#include <queue>
using namespace std;
int n, ton[100005], ans=0,t,m,l;
struct node
{
int s, t;//结构体存储国际与时间
}h;
queue < node > q;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> t >> m;//到达海港的时间和船上的乘客数
while (!q.empty())
{
h = q.front();
if(h.t<=t-86400)
{
ton[h.s]--;//这一国籍的人减一
if (ton[h.s] == 0) ans--;
//如果国籍中没有一个人就失去了答案
q.pop();//弹出
continue;//继续
}
else
break;//否则弹出(因为是严格递增的)
}
for (int i = 1; i <= m; i++)
{
cin >> l;//人的国籍
h.s = l;
h.t = t;
ton[l]++;
if (ton[l] == 1)
ans++;
q.push(h);
}
cout << ans << endl;
}
}
原文：https://www.cnblogs.com/lonely-ok/p/12828615.html