这套队列堆栈专题试卷做的我很心累，我感觉我开学的蓝桥杯比赛很悬，我现在就是非常后悔，非常非常后悔，嗐，没有抓紧时间刷题。⊙﹏⊙
悟已往之不谏，知来者之可追。好好刷题，不当炮灰！(ง •_•)ง
1、力扣（LeetCode）仅仅反转字母(15分)
原题链接
给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
示例 1：
输入："ab-cd"
输出："dc-ba"
示例 2：
输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"
示例 3：
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"
提示：
S.length <= 100
33 <= S[i].ASCIIcode <= 122
S 中不包含 \ or "
不太熟悉力扣的提交方式，好像是只需补充函数，主函数不需要写，评判机会自动调用自定义函数。1w点暴击，简单面试题对我来说也不简单。。
题解链接
题解代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string reverseOnlyLetters(string S) {
stack<char> s;
for(int i = 0; i < S.length(); i++)
{
if(isalpha(S[i]))
{
s.push(S[i]);
}
}
string ans;
for(int i = 0; i < S.length(); i++)
{
if(isalpha(S[i]))
{
ans += s.top();
s.pop();
}
else ans += S[i];
}
return ans;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
string str;
getline(cin,str);
Solution s;
cout << s.reverseOnlyLetters(str) << endl;
return 0;
} 2.蓝桥杯 算法提高 队列操作（15分）
原题链接
问题描述
队列操作题。根据输入的操作命令，操作队列（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。
输入格式
第一行一个数字N。下面N行，每行第一个数字为操作命令（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。
输出格式
若干行每行显示一个2或3命令的输出结果。注意：2.出队命令可能会出现空队出队（下溢），请输出“no”，并退出。
样例输入
7 1 19 1 56 2 3 2 3 2
样例输出
19 1 56 0 no
数据规模和约定
1<=N<=50
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
queue<int> q;
int n;
cin >> n;
for(int i = 0;i<n;i++){
int k;
cin >> k;
if(k==1){
int m;
cin >> m;
q.push(m);
continue;
}else if(k==2){
if(!q.empty()){
cout << q.front() <<endl;
q.pop();
}else{
printf("no\n");
return 0;
}
continue;
}else{
cout << q.size() << endl;
}
}
} 3.C语言网 问题 1733: 堆栈的使用（15分）
原题链接
题目描述
堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。Push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。
输入
对于每组测试数据，第一行是一个正整数 n，0<n<=10000(n=0 结束)。而后的 n行，每行的第一个字符可能是'P’或者'O’或者'A’；如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O’，表示将栈顶的值pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是'A’，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空。
输出
对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A’操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E’。当每组测试数据完成后，输出一个空行。
样例输入
5 P 75 O O P 60 A 7 A O P 73 P 49 A O P 3 0
样例输出
60 E 49
这题我拉低了正确率，提交了很多次，出现了很多种错误，最后一种错误是格式错误，也没找到问题在哪，嗐，我太难了，好累啊啊啊啊啊啊啊啊
大佬的AC代码如下：
#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i < b; i++)
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;
while(cin >> n && n)
{
stack<int> s;
while(n--)
{
char ch;
cin >> ch;
if(ch == 'P')
{
int _;
cin >> _;
s.push(_);
}
else if(ch == 'O')
{
if(!s.empty()) s.pop();
else continue;
}
else if(ch == 'A')
{
if(!s.empty()) cout << s.top() << endl;
else cout << "E" << endl;
}
}
cout << endl;
}
return 0;
} 4、团体程序设计天梯赛-练习集 倒数第N个字符串(15分)
原题链接
给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。例如当
L 为 3 时，序列为 { aaa, aab, aac, ..., aaz, aba, abb, ..., abz, ..., zzz
}。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。
输入格式：
输入在一行中给出两个正整数 L（2 ≤ L ≤ 6）和 N（≤1e5）。
输出格式：
在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。
输入样例：
3 7417
输出样例：
pat
这题真的毫无思绪，大佬曰：这题实际上是进制转换，把L位数看成L个由26进制组成的数字，则最后一个数字的十进制表示为pow（26，L）-1，倒数N个数的十进制表示为pow（26，L）-N。这里用到了“后进先出”的栈，从pow（26，L）-N开始递减，把每个数字推入栈中，最后在栈顶的元素一定会是pow（26，L）-1，然后把所求的结果转换成26进制还原即可。若还原成26进制时位数不足L个，则需要在前面补上'a'。
题解链接
题解代码如下
#include <bits/stdc++.h>
using namespace std;
int main()
{
int L,N;
cin >> L >> N;
stack<int> s; //利用栈的“先进先出”
int num = pow(26,L)-N;
while(num)
{
s.push(num%26);
num /= 26;
}
for(int i = 0; i < L-s.size(); i++) //补a
{
cout << "a";
}
while(!s.empty()) //***大甩卖
{
cout << (char)('a' + s.top());
s.pop();
}
return 0;
} 5、PAT (Basic Level) Practice 1009 说反话 (20分)
原题链接
给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。
输入格式：
测试输入包含一个测试用例，在一行内给出总长度不超过 80
的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1
个空格分开，输入保证句子末尾没有多余的空格。
输出格式：
每个测试用例的输出占一行，输出倒序后的句子。
输入样例：
Hello World Here I Come
输出样例：
Come I Here World Hello
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
string str;
stack<string> st;
while(cin >> str){
st.push(str);
}
int cnt = 0;
while(!st.empty()){
if(!cnt){
cout << st.top();
cnt++;
}else{
cout << " " <<st.top();
}
st.pop();
}
} 6、PAT (Basic Level) Practice 1069 微博转发抽奖 (20分)
原题链接
小明 PAT 考了满分，高兴之余决定发起微博转发抽奖活动，从转发的网友中按顺序每隔 N 个人就发出一个红包。请你编写程序帮助他确定中奖名单。
输入格式：
输入第一行给出三个正整数 M（≤ 1000）、N 和 S，分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号（编号从 1
开始）。随后 M 行，顺序给出转发微博的网友的昵称（不超过 20 个字符、不包含空格回车的非空字符串）。
注意：可能有人转发多次，但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖，则跳过他顺次取下一位。
输出格式：
按照输入的顺序输出中奖名单，每个昵称占一行。如果没有人中奖，则输出 Keep going...。
输入样例 1：
9 3 2 Imgonnawin! PickMe PickMeMeMeee LookHere Imgonnawin! TryAgainAgain TryAgainAgain Imgonnawin! TryAgainAgain
输出样例 1：
PickMe Imgonnawin! TryAgainAgain
输入样例 2：
2 3 5 Imgonnawin! PickMe
输出样例 2：
Keep going...
这题又不会处理，只知道要用队列，却不知如何实现，大佬曰：建立一个字符串队列queue用来存入中奖者的昵称，建立一个中奖者名单map，这个操作看上去是重复的，写到后面才会发现这两者的用处。立一个flag用来记录是否有人中奖，true为没人中奖。用for循环遍历，如果这是中奖者，先判断他在不在map里，若不在map里，就把他放入map同时入队，若在map里，就跳过他顺次取下一位（S++;continue）。每次抽完中奖者之后，中奖序号需要加上一个中奖间隔。最后把队列从队首开始根据“先进先出”的规则进行输出。如果flag依然为真，说明没人中奖，输出"Keep going..."
题解链接
题解代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int M,N,S; //M为转发的总量,N为小明决定的中奖间隔,S是第一位中奖者的序号
cin >> M >> N >> S;
queue<string> q; //字符串型队列
map<string, int> m;
bool flag = true; //flag用来记录是否有人中奖,true为没人中奖
for (int i = 1; i <= M; i++)
{
string temp;
cin >> temp;
if(i==S) //中奖者
{
flag = false;
if(m[temp]==0)
{
m[temp]++;
q.push(temp);
}
else
{
S++;
continue;
}
S += N;
}
}
while(!q.empty()) //***大甩卖
{
cout << q.front() << endl;
q.pop();
}
if(flag)
{
cout << "Keep going..." << endl;
}
return 0;
} 
京公网安备 11010502036488号