【数据结构】栈和队列的应用（头歌习题）【合集】
第1关：括号是否匹配
任务描述
本关任务：给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。
相关知识
为了完成本关任务，你需要掌握：1.栈的基本特性和操作，2.C++ 标准模板库（STL）中的容器栈（stack）的基本操作。
1. 栈的基本特性和操作
本关提供一个顺序栈SqStack的基本运算及其实现，你可以调用其有关函数完成指定操作。各函数详细功能请参见代码目录中的sqstack.h头文件，基本操作如下：
//初始化顺序栈
void InitStack(SqStack *&s);
//判断栈空否
bool StackEmpty(SqStack *s);
//进栈
bool Push(SqStack *&s, ElemType e);
//出栈
bool Pop(SqStack *&s, ElemType &e);
//取栈顶元素
bool GetTop(SqStack *s, ElemType &e);
2. C++ STL中的栈（stack）
stack翻译为栈，是STL中一个后进先出（Last In First Out，LIFO）的一个容器。
如果要使用stack，需要添加stack头文件，#include 。除此之外，还需要在头文件下面加上一句：“using namespace std;”，这样就可以在代码中使用stack了。下面来看stack 的一些常用用法。
2.1 stack的定义
定义一个stack的语法如下，其中typename可以是任意基本数据类型或容器，stack_name为容器对象名称:
stack<typename> stack_name;
//例如：
stack<int> st1; //定义一个名称为st1存放int型数据的栈
stack<char> st2; //定义一个名称为st2存放char型数据的栈
stack<string> st3; //定义一个名称为st3存放string型数据的栈
2.2 stack容器内元素的访问
由于栈（stack）本身就是一种后进先出的数据结构，因此在STL中只能通过pop()来访问栈顶元素。
示例如下：
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
stack<int> st;
for (int i = 1; i <= 5; i++) {
st.push(i); //push(i)将元素入栈,因此1 2 3 4 5依次入栈
}
printf("%d\n", st.top()); //访问栈顶元素
return 0;
}
程序运行后，栈中元素如下图所示：
栈操作示例
程序输出结果：
5
2.3. stack常用函数实例解析
(1) push()
push(x)将x入栈，时间复杂度为O(1)。
(2) top()
top()获取栈顶元素，时间复杂度O(1)。
(3) pop()
pop()弹出栈顶元素，时间复杂度为O(1)。
示例如下：
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
stack<int> st;
for (int i = 1; i <= 5; i++) {
st.push(i); //将1 2 3 4 5依次入栈
}
for (int i = 1; i <= 3; i++) {
st.pop(); //连续三次将栈顶元素出栈,即5 4 3依次出栈
}
printf("%d\n", st.top()); //访问栈顶元素
return 0;
}
输出结果：
2
(4) empty()
empty()检测stack是否为空，为空则返回true，非空则返回false。复杂度为O(1)。
示例如下：
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
stack<int> st;
if (st.empty() == true) { //一开始栈内没有元素,所以是空
printf("Empty\n");
} else {
printf("Not empty\n");
}
st.push(1);
if (st.empty() == true) { //入栈“1”后,栈非空
printf("Empty\n");
} else {
printf("Not empty\n");
}
return 0;
}
输出结果：
Empty
Not empty
(5) size()
size()返回stack内元素的个数，复杂度为O(1)。
示例如下：
#include <stdio.h>
#include <stack>
using namespace std;
int main() {
stack<int> q;
for (int i = 1; i <= 5; i++) {
q.push(i); //push(i)用来将i入栈
}
printf("%d\n", q.size()); //栈中有5个元素
return 0;
}
输出结果：
5
2.4 stack的常见用途
栈用来模拟实现一些递归，防止程序对栈内存的限制而导致程序出错。一般来说，程序的栈内存空间很小，对有些题目来说，如果用普通的函数来进行递归，一旦递归层数过深（不同的机器不同，一般约几千至几万层），则会导致程序运行崩溃。如果用栈来模拟递归算法的实现，则可以避免这一方面的问题（不过这种应用较少出现）。
2.5 一个完整的stack程序示例
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int> st; //定义栈对象st
for (int i = 1; i <= 10; i++) {
st.push(i); //1 2 3 4 5 6 7 8 9 10依次入栈
}
//输出栈的元素个数
cout << st.size() << endl; //10
//输出栈顶元素
cout << st.top() << endl; //10
//输出栈的所有元素
while (!st.empty()) {
int tmp = st.top(); //取栈顶元素
cout << tmp << " "; //输出栈顶元素
st.pop(); //删除栈顶元素
}
cout << endl;
return 0;
}
输出结果：
10
10
10 9 8 7 6 5 4 3 2 1
编程要求
根据提示，在右侧编辑器补充完成函数bool is_valid(char* str)的代码，该函数的功能为判断传入的字符串str中包含的括号是否匹配，如果匹配函数返回true，否则返回false。
测试说明
平台会对你编写的代码进行测试：
测试输入：
sin(10+20)
预期输出：
yes
测试输入：
[ , { ( , . ) [,] } , , ]
预期输出：
yes
开始你的任务吧，祝你成功！
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <stack>
using namespace std;
#include "sqstack.h" //包含顺序栈基本运算
bool is_valid(char* str)
{
//请在下面编写代码
/*************************Begin*********************/
stack<char> st;
int n = strlen(str);
int i;
for(i=0; i<n; i++){
if(str[i]=='('){
st.push(')');
}else if(str[i]=='['){
st.push(']');
}else if(str[i]=='{'){
st.push('}');
}else if(str[i]==')'){
if(st.empty() || st.top()!=')'){
return false;
}else{
st.pop();
}
}else if(str[i]==']'){
if(st.empty() || st.top()!=']'){
return false;
}else{
st.pop();
}
}else if(str[i]=='}'){
if(st.empty() || st.top()!='}'){
return false;
}else{
st.pop();
}
}else{
continue;
}
}
return st.empty();
/**************************End**********************/
}
int main(int argc, char const *argv[])
{
char exp[1000];
fgets(exp, 1000, stdin);
bool flag = is_valid(exp);
if (flag)printf("yes\n");
else printf("no\n");
return 0;
}
第2关：算术表达式转换为后缀表达式
任务描述
本关任务：编写一个将算术表达式转换为后缀表达式的程序。
相关知识
为了完成本关任务，你需要掌握：1.算术表达式的表示方法，2.如何将算术表达式转换为后缀表达式。
算术表达式
1.中缀表达式
在算术表达式中，运算符位于两个操作数中间的表达式称为中缀表达式。例如，"1+2*3"就是一个中缀表达式。中缀表达式的运算规则：“先乘除，后加减，从左到右计算，先括号内，后括号外”。因此，中缀表达式不仅要依赖运算符优先级，而且还要处理括号。
2. 后缀表达式
算术表达式的另一种形式是后缀表达式或逆波兰表达式，就是在算术表达式中，运算符在操作数的后面。
如"1+2*3"的后缀表达式为"1 2 3 * +"。
后缀表达式特点：
没有括号，已考虑了运算符的优先级。
只有操作数和运算符，而且越放在前面的运算符来越优先执行。
3. 前缀表达式
在算术表达式中，如果运算符在操作数的前面，称为前缀表达式，如"1+2*3"的前缀表达式为"+ 1 * 2 3"。
算术表达式转换为后缀表达式
假定算术表达式用exp表示，后缀表达式用postexp表示，将算术表达式转为后缀表达式的一般转换规则如下：
顺序扫描算术表达式的每个字符：
数字字符直接放在postexp中
运算符通过一个栈来处理优先级
如果算术表达式没有括号，则
优先级相同：先进栈的先退栈即先执行,只有大于栈顶优先级才能直接进栈
exp扫描完毕，所有运算符退栈
如果算术表达式含有括号，则
开始时，任何运算符都进栈
扫描到 ( 时，表示一个子表达式开始，进栈
当栈顶为 ( 时任何运算符进栈
扫描到 ) 时，退栈，直到遇到（
只有大于栈顶的优先级，才进栈；否则退栈
伪代码
综合上述规则，可以得到如下的伪代码：
while (从exp读取字符ch，ch!='\0')
{ ch为数字：将后续的所有数字均依次存放到postexp中，
并以字符'#'标志数值串结束;
ch为左括号'('：将此括号进栈到Optr中;
ch为右括号')'：将Optr中出栈时遇到的第一个左括号'('以前的运算符依次出
栈并存放到postexp中，然后将左括号'('出栈;
ch为其他运算符：
if （栈空或者栈顶运算符为'('） 直接将ch进栈;
else if (ch的优先级高于栈顶运算符的优先级)
直接将ch进栈;
else
依次出栈并存入到postexp中，直到栈顶运算符优先级小于ch的
优先级，然后将ch进栈;
}
若exp扫描完毕，则将Optr中所有运算符依次出栈并存放到postexp中。
在上述转换过程中，需要用栈处理运算符的优先级。本关在sqstack.h文件中提供了一个顺序栈的基本运算及其实现，该文件可以通过代码窗口右上角的代码目录打开；本关也提供了C++ STL中的stack这种容器，你可以在程序中直接使用C++ STL中的stack容器。
在sqstack.h文件中提供的顺序栈的基本运算如下：
//初始化顺序栈
void InitStack(SqStack *&s);
//销毁顺序栈
void DestroyStack(SqStack *&s);
//判断栈空否
bool StackEmpty(SqStack *s);
//进栈
bool Push(SqStack *&s, ElemType e);
//出栈
bool Pop(SqStack *&s, ElemType &e);
//取栈顶元素
bool GetTop(SqStack *s, ElemType &e);
编程要求
根据提示，在右侧编辑器补充完成函数void trans(char *exp, char postexp[])的代码，该函数的功能是将传入的算术表达式（中缀表达式）exp转换为后缀表达式postexp。
测试说明
平台会对你编写的代码进行测试：
测试输入：
(56-20)/(4+2)
预期输出：
56#20#-4#2#+/
测试输入：
1+23
预期输出：
1#2#3#+
提示：
在后缀表达式中，两个操作数之间使用一个#进行分隔。
开始你的任务吧，祝你成功！
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string> //C++ STL之string字符串
#include <stack> //C++ STL之stack容器
using namespace std;
#include "sqstack.h" //包含顺序栈基本运算
void trans(char *exp, char postexp[]) //将算术表达式exp转换成后缀表达式postexp
{
//请在下面编写代码
/*************************Begin*********************/
char e;
SqStack *Optr; // 定义运算符栈
InitStack(Optr); // 初始化栈
int i=0;
while(*exp != '\0'){ // exp表达式未扫描完时
switch(*exp){
case '(':
Push(Optr, '(');
exp++;
break;
case ')':
Pop(Optr, e); // 出栈元素e
while(e != '('){
postexp[i++] = e;
Pop(Optr, e);
}
exp++;
break;
case '+':
case '-':
while(!StackEmpty(Optr)){ // 栈不为空
GetTop(Optr, e);
if(e!='('){
postexp[i++]=e;
Pop(Optr, e);
}else{
break;
}
}
Push(Optr, *exp); // 将+或-进栈
exp++;
break;
case '*':
case '/':
while(!StackEmpty(Optr)){
GetTop(Optr, e);
if(e=='*' || e=='/'){ // 将*或/出栈并存放到数组中
postexp[i++] = e;
Pop(Optr, e);
}else{
break;
}
}
Push(Optr, *exp); // 将将*或/进栈
exp++;
break;
default:
while(*exp>='0' && *exp<='9'){
postexp[i++] = *exp;
exp++;
}
postexp[i++] = '#'; //用标识符#表示数值串结束
}
}
while(!StackEmpty(Optr)){ // exp扫描完毕，栈不空时循环
Pop(Optr, e);
postexp[i++] = e;
}
postexp[i] = '\0'; // 给postexp添加结束标识
DestroyStack(Optr);
/**************************End**********************/
}
int main(int argc, char const *argv[])
{
char exp[1000];
char postexp[1000];
scanf("%s", exp); //输入算术表达式
trans(exp, postexp); //转换为后缀表达式
printf("%s\n", postexp);//输出转换后的后缀表达式
return 0;
}
第3关：逆波兰表达式求值
任务描述
本关任务：编写一个程序，请输出以逆波兰表达式输入的算式的计算结果。
逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面的描述程序（算式）的方法。举个例子，我们平常用中缀表示法描述的算式（1 + 2）*（5 + 4），改为逆波兰表示法之后则是1 2 + 5 4 + *。相较于中缀表示法，逆波兰表示法的优势在于不需要括号。
相关知识
为了完成本关任务，你需要掌握：1.如何求解逆波兰表达式的值，2.栈的使用。
求逆波兰表达式的值
假设逆波兰表达式存放在postexp中，求解过程如下：
从头到尾扫描postexp的所有字符：
数字字符：转换为数值并进栈。
运算符：退栈两个操作数，计算，将结果进栈。
伪代码
上述求解过程用伪代码可以表示如下：
while (从postexp读取字符ch，ch!='\0')
{ ch为'+'：从Opnd栈中出栈两个数值a和b，计算c=b+a;将c进栈;
ch为'-'：从Opnd栈中出栈两个数值a和b，计算c=b-a;将c进栈;
ch为'*'：从Opnd栈中出栈两个数值a和b，计算c=b*a;将c进栈;
ch为'/'：从Opnd栈中出栈两个数值a和b，若a不零，计算c=b/a;将c进栈;
ch为数字字符：将连续的数字串转换成数值d，将d进栈;
}
返回Opnd栈的栈顶操作数即后缀表达式的值;
栈的使用
在上述求解过程中，用到了栈。
本关在sqstack.h文件中提供了一个顺序栈的基本运算及其实现，该文件可以通过代码窗口右上角的代码目录打开；本关也提供了C++ STL中的stack这种容器，你可以在程序中直接使用C++ STL中的stack容器。
在sqstack.h文件中提供的顺序栈的基本运算如下：
//初始化顺序栈
void InitStack(SqStack *&s);
//销毁顺序栈
void DestroyStack(SqStack *&s);
//判断栈空否
bool StackEmpty(SqStack *s);
//进栈
bool Push(SqStack *&s, ElemType e);
//出栈
bool Pop(SqStack *&s, ElemType &e);
//取栈顶元素
bool GetTop(SqStack *s, ElemType &e);
编程要求
根据提示，在右侧编辑器补充完成函数int compvalue(char *postexp)的代码，计算并返回逆波兰表达式的值。
测试说明
平台会对你编写的代码进行测试：
输入格式
在一行中输入一个用逆波兰表达式表示的算式。其中每个操作数的后面用1个’#'隔开，运算符只包含±*/四种运算符。
测试输入：
3#2#+
预期输出：
5
测试输入：
56#20#-4#2#+/
预期输出：
6
提示：
2≤算式中操作数的总数≤100
1≤算式中运算符的总数≤99
运算符仅包括“+”、“-”、“*”、“/”，操作数、计算过程中的中间值以及最终的计算结果均在int范围内。
开始你的任务吧，祝你成功！
完整代码
#include <string.h>
#include <string> //C++ STL之string字符串
#include <stack> //C++ STL之stack容器
using namespace std;
#include "sqstack.h" //包含顺序栈基本运算
//计算后缀表达式的值并返回
int compvalue(char *postexp)
{
//请在下面编写代码
/*************************Begin*********************/
int d, a, b, c, e;
SqStack *Opnd; // 定义操作数栈
InitStack(Opnd); //初始化
while(*postexp != '\0') {
switch (*postexp){
case '+':
Pop(Opnd, a);
Pop(Opnd, b);
c = b+a;
Push(Opnd, c);
break;
case '-':
Pop(Opnd, a);
Pop(Opnd, b);
c = b-a;
Push(Opnd, c);
break;
case '*':
Pop(Opnd, a);
Pop(Opnd, b);
c = b*a;
Push(Opnd, c);
break;
case '/':
Pop(Opnd, a);
Pop(Opnd, b);
if(a!=0){
c = b/a;
Push(Opnd, c);
break;
}else{
printf("\n\t除零错误!\n");
exit(0);
}
break;
default:
d = 0;
while(*postexp >= '0' && *postexp <='9'){
d = 10*d + *postexp - '0';
postexp++;
}
Push(Opnd, d);
break;
}
postexp++; // 继续处理其他字符
}
GetTop(Opnd, e);
DestroyStack(Opnd);
return e;
/**************************End**********************/
}
int main()
{
char postexp[MaxSize];
scanf("%s", postexp); //输入逆波兰表达式
printf("%d\n", compvalue(postexp)); //求逆波兰表达式的值并打印输出
return 0;
}
第4关：利用栈实现整数的十进制转八进制
本关必读
栈是基础的数据结构，元素操作遵循后进先出的原理。本关卡基于数组存储实现了栈的基本操作。
该方案将栈存储在一片连续空间里，并通过data、top和max三个属性元素。组织成为一个结构：
- data: 给出栈存储空间的起始地址
- max: 指明栈存储空间最多可存储的数据元素个数
- top: 栈顶元素所处数组位置 为了讨论简化，我们假设每个数据元素是一个整数:
typedef int T; // 数据元素的数据类型
该栈的结构定义如下：
struct Stack{
T* data; // 数据元素存储空间的开始地址
int top; // 栈顶元素所处数组位置
int max; // 栈存储空间最多可存储的数据元素个数
};
只要创建一个Stack指针对象，就可对栈表进行操作。
对数据元素进行操作处理是一个数据结构的重要组成部分。栈涉及的主要操作如下：
- 创建栈：创建一个最多可存储max个数据元素的顺序存储的栈，初始状态设置为top=-1。该操作函数具体定义如下，其返回值为Stack指针： Stack* Stack_Create(int max)
- 释放栈存储空间：释放stk->data所指向的用于存储栈数据元素的存储空间。该操作函数具体定义如下： void Stack_Free(Stack* stk)
- 置空栈：将当前栈变为一个空栈，实现方法是将stk->top设置为-1。该操作函数具体定义如下： void Stack_MakeEmpty(Stack* stk)
- 判断栈是否为空：若当前栈是空栈，则返回true,否则返回false。该操作函数具体定义如下： bool Stack_IsEmpty(Stack* stk)
- 判断栈空间是否为满：若栈顶达到最大长度，则返回true,否则返回false。该操作函数具体定义如下： bool Stack_IsFull(Stack* stk)
- 返回栈顶元素：返回栈顶元素stk->data[stk->top]。该操作函数具体定义如下： T Stack_Top(Stack* stk)
- 将元素进栈： 将元素e压入栈顶。若栈满压入失败，返回异常，否则返回栈顶元素。该操作函数具体定义如下 T Stack_Push(Stack* stk, T e)
- 将元素出栈： 将栈顶元素出栈。若栈空出栈失败，返回异常，否则返回栈顶元素。该操作函数具体定义如下 T Stack_Pop(Stack* stk)
任务描述
本关任务：基于栈stack数据结构解决整数十进制转八进制的问题。
相关知识
为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作，3.进制转换。
创建栈
本例已基于数组存储结构实现了栈的创建，通过调用Stack* Stack_Create(int max)创建一个栈实例。
Stack *stk = Stack_Create(32);//创建一个栈实例
入栈和出栈操作
示例如下：
T e = 2018;
Stack_Push(stk, e);//入栈
e = Stack_Pop(stk);//出栈
进制转换
除K取余法，例如十进制数10转二进制：
编程要求
本关的编程任务是补全右侧代码片段Decimal_Conversion_Octal中Begin至End中间的代码，具体要求如下：
- 在Decimal_Conversion_Octal中，利用栈stack的基本操作实现整数的十进制转八进制，并输出八进制结果，末尾换行。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
样例一：
测试输入：71
预期输出：107
样例二：
测试输入：8
预期输出：10
开始你的任务吧，祝你成功！
完整代码
//
// stack_.cpp
// Stack
//
// Created by ljpc on 2018/4/17.
// Copyright ? 2018年 ljpc. All rights reserved.
//
#include "stack_.h"
// 栈操作实现文件
//
Stack* Stack_Create(int maxlen)
// 创建栈
{
Stack* stk = (Stack*)malloc(sizeof(Stack));
stk->data = (T*)malloc(sizeof(T)*maxlen);
stk->max = maxlen;
stk->top = -1;
return stk;
}
void Stack_Free(Stack* stk)
// 释放栈
{
free(stk->data);
free(stk);
}
void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
stk->top = -1;
}
bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
return -1 == stk->top;
}
bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
return stk->top == stk->max-1;
}
T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
return stk->data[stk->top];
}
T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
if(Stack_IsFull(stk)) {
printf("Stack_IsFull(): stack full error when push element to the stack!\n");
Stack_Free(stk);
exit(0);
}
else{
stk->top += 1;
stk->data[stk->top] = e;
return Stack_Top(stk);
}
}
T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
if(Stack_IsEmpty(stk)) {
printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
Stack_Free(stk);
exit(0);
}
else{
T topE = Stack_Top(stk);
stk->top -= 1;
return topE;
}
}
void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
if (Stack_IsEmpty(stk)) {
printf("The stack is empty.\n");
return;
}
//printf("The stack contains: ");
for (int i=stk->top; i>=0; i--) {
printf("%d", stk->data[i]);
}
printf("\n");
}
void Decimal_Conversion_Octal(T e)
// 利用stack栈实现整数的十进制转八进制
// 输入参数：十进制整数 e
// 打印e的八进制结果，末尾换行
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int a;
int b;
int k=8;
Stack *stk = Stack_Create(100);
while(e>0){
a = e / k;
b = e % k;
e = a;
Stack_Push(stk, b);
}
Stack_Print(stk);
Stack_Free(stk);
/********** End **********/
}
//
// stack_.h
// Stack
//
// Created by ljpc on 2018/4/17.
// Copyright ? 2018年 ljpc. All rights reserved.
//
#ifndef stack__h
#define stack__h
#include <stdio.h>
#include <stdlib.h>
typedef int T; // 数据元素的数据类型
struct Stack{
T* data; // 数据元素存储空间的开始地址
int top; // 栈顶的位置
int max; // 栈的最大长度
};
Stack* Stack_Create(int maxlen);
// 创建栈
void Stack_Free(Stack* stk);
// 释放栈
void Stack_MakeEmpty(Stack* stk);
// 置为空栈
bool Stack_IsEmpty(Stack* stk);
// 判断栈是否空
bool Stack_IsFull(Stack* stk);
// 判断栈是否满
T Stack_Top(Stack* stk);
// 返回栈顶元素
T Stack_Push(Stack* stk, T e);
// 将元素e压入栈顶
// 返回栈顶点元素
T Stack_Pop(Stack* stk);
// 将栈顶元素出栈
// 返回栈顶元素
void Stack_Print(Stack* stk);
// 打印栈顶到栈低的元素
void Decimal_Conversion_Octal(T e);
// 利用stack栈实现整数的十进制转八进制
// 输入参数：十进制整数 e
// 打印结果，末尾换行
#endif /* stack__h */
第5关：利用栈判断字符串是否为回文串
任务描述
本关任务：基于栈stack数据结构判断字符串是否为“回文串”。
相关知识
为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作，3.“回文串”概念。
- 创建栈、入栈和出栈操作请参考第1关
回文串
简单来说，“回文串”是一个正读和反读都一样的字符串：
noon是回文串
moon不是回文串
编程要求
本关的编程任务是补全右侧代码片段Palindrome中Begin至End中间的代码，具体要求如下：
- 在Palindrome中，利用栈stack判断字符串是否为回文串， 若是回文串输出YES，否则输出NO，末尾换行。
测试说明
平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
以下是平台的测试样例：
样例一：
测试输入：
4
1221
预期输出：
YES
样例二：
测试输入：
7
abababa
预期输出：
YES
开始你的任务吧，祝你成功！
完整代码
//
// stack_.cpp
// Palindrome
//
// Created by ljpc on 2018/4/18.
// Copyright ? 2018年 ljpc. All rights reserved.
//
#include "stack_.h"
// 栈表操作实现文件
//
Stack* Stack_Create(int maxlen)
// 创建栈
{
Stack* stk = (Stack*)malloc(sizeof(Stack));
stk->data = (T*)malloc(sizeof(T)*maxlen);
stk->max = maxlen;
stk->top = -1;
return stk;
}
void Stack_Free(Stack* stk)
// 释放栈
{
free(stk->data);
free(stk);
}
void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
stk->top = -1;
}
bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
return -1 == stk->top;
}
bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
return stk->top == stk->max-1;
}
T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
return stk->data[stk->top];
}
T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
if(Stack_IsFull(stk)) {
printf("Stack_IsFull(): stack full error when push element to the stack!\n");
Stack_Free(stk);
exit(0);
}
else{
stk->top += 1;
stk->data[stk->top] = e;
return Stack_Top(stk);
}
}
T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
if(Stack_IsEmpty(stk)) {
printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
Stack_Free(stk);
exit(0);
}
else{
T topE = Stack_Top(stk);
stk->top -= 1;
return topE;
}
}
void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
if (Stack_IsEmpty(stk)) {
printf("The stack is empty.\n");
return;
}
//printf("The stack contains: ");
for (int i=stk->top; i>=0; i--) {
printf("%d", stk->data[i]);
}
printf("\n");
}
void Palindrome(T* str, int len)
// 利用stack栈判断字符串是否为回文串
// 输入参数：字符串序列，字符串长度
// 若是回文串输出YES，否则输出NO，末尾换行
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
Stack* stk = Stack_Create(len);
for(int i=0; i<len/2; i++){
Stack_Push(stk, str[i]);
}
int p=(len&1)?(len/2+1):(len/2); // 判断奇偶
for (int i=p; i<len; i++) {
if(str[i]!=Stack_Top(stk)) {
printf("NO\n");
return;
}else{
Stack_Pop(stk);
}
}
printf("YES\n");
/********** End **********/
}
//
// stack_.h
// Palindrome
//
// Created by ljpc on 2018/4/18.
// Copyright ? 2018年 ljpc. All rights reserved.
//
#ifndef stack__h
#define stack__h
#include <stdio.h>
#include <stdlib.h>
typedef char T; // 数据元素的数据类型
struct Stack{
T* data; // 数据元素存储空间的开始地址
int top; // 栈表的当前位置
int max; // 栈表的最大长度
};
Stack* Stack_Create(int maxlen);
// 创建栈
void Stack_Free(Stack* stk);
// 释放栈
void Stack_MakeEmpty(Stack* stk);
// 置为空栈
bool Stack_IsEmpty(Stack* stk);
// 判断栈是否空
bool Stack_IsFull(Stack* stk);
// 判断栈是否满
T Stack_Top(Stack* stk);
// 获取当前栈顶元素
T Stack_Push(Stack* stk, T e);
// 将元素e压入栈顶
// 返回栈顶点元素
T Stack_Pop(Stack* stk);
// 将栈顶元素出栈
// 返回栈顶元素
void Stack_Print(Stack* stk);
// 打印栈顶到栈低的元素
void Palindrome(T* str, int len);
// 利用stack栈判断字符串是否为回文串
// 输入参数：字符串序列，字符串长度
// 若是回文串输出YES，否则输出NO，末尾换行
#endif /* stack__h */
第6关：循环调度法
任务描述
本关任务：编写一个模拟CPU处理任务的循环调度法的程序。
本关要求您设计一个队列或者使用C++ STL的队列容器（queue）完成给定任务（见后面的编程要求）。
相关知识
为了完成本关任务，你需要掌握：1.如何设计和实现一个队列，2.如何使用C++ STL的队列容器queue。
1. 如何设计一个队列
略。
2. C++ STL的队列容器queue
queue翻译为队列，在STL中主要用来实现一个先进先出（First In First Out，FIFO）的容器。
如果要使用queue, 需要添加queue头文件，#include 。除此之外，还需要在头文件下面加上一句：“using namespace std;”，这样就可以在代码中使用queue 了。下面来看queue 的一些常用用法。
2.1 queue的定义
定义一个queue的语法如下，其中T可以是任意基本数据类型或容器:
queue<T> queue_name;
2.2 queue容器内元素的访问
由于队列（queue）本身即是一种先进先出的限制性的数据结构，因此在STL中只能通过front()来访问队首元素，通过back()来访问队尾元素。
示例如下：
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for (int i = 1; i <= 5; i++) {
q.push(i); //push(i)用来将i入队列,即依次入队列1 2 3 4 5
}
printf("%d %d\n", q.front(), q.back());//输出结果是1 5
return 0;
}
输出结果：
1 5
2.3 queue常用函数实例解析
(1) push()： push(x)将x入队列，时间复杂度为O(1)。
(2) front()、back()： front()和back()分别获得队首元素和队尾元素，时间复杂度O(1)。
(3) pop()： pop()令队首元素出队列，时间复杂度为O(1)。
示例如下：
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for (int i = 1; i <= 5; i++) {
q.push(i); //push(i)用来将i入队列,即依次入队列1 2 3 4 5
}
for (int i = 1; i <= 3; i++) {
q.pop(); //出队首元素三次(即依次出队1 2 3)
}
printf("%d\n", q.front()); //此时队首元素是4，因此输出结果是4
return 0;
}
输出结果：
4
(4) empty() empty()检测queue是否为空，为空则返回true，非空则返回false。复杂度为O(1)。
示例如下：
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
if (q.empty() == true) { //一开始队列内没有元素,所以是空
printf("Empty\n");
} else {
printf("Not empty\n");
}
q.push(1); //1入队列
if (q.empty() == true) { //在入队列“1”后,队列非空
printf("Empty\n");
} else {
printf("Not empty\n");
}
return 0;
}
输出结果：
Empty
Not empty
(5) size()： size()返回queue内元素的个数，复杂度为O(1)。
示例如下：
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for (int i = 1; i <= 5; i++) {
q.push(i); //push(i)用来将i入队列
}
printf("%d\n", q.size()); //队列中有5个元素
return 0;
}
输出结果：
5
2.4 queue的注意事项
当需要实现广度优先搜索（BFS）时，可以不用自己动手实现一个队列，而是用queue作为代替，以提高程序的准确性。
另外有一点需要注意的是，使用front()和pop()函数前，必须使用empty()函数先判断队列是否为空，否则可能因为队列空而出现错误。
STL的容器中还有两种容器跟队列有关，分别是双端队列（deque）和优先队列（priority_queue），前者是首尾两端都可以插入和删除的队列，后者是使用堆实现的默认将当前队列最大元素置于队首的容器（相当于大顶堆、大根堆）。在求解哈夫曼树和哈夫曼编码时就可以使用优先队列（priority_queue）。
2.5 一个完整的队列程序示例
#include<iostream>
#include<queue>
using namespace std;
int main()
{
queue<int> q; //定义队列对象q
for (int i = 1; i <= 10; i++) {
q.push(i); //1 2 3 4 5 6 7 8 9 10依次入队列
}
//输出队列的元素个数
cout << q.size() << endl; //10
//输出队首元素
cout << q.front() << endl; //1
//输出队尾元素
cout << q.back() << endl; //10
//输出队列的所有元素
while (!q.empty()) {
int tmp = q.front(); //取队首元素
cout << tmp << " "; //输出队首元素
q.pop(); //删除队首元素
}
cout << endl;
return 0;
}
输出结果：
10
1
10
1 2 3 4 5 6 7 8 9 10
编程要求
现有名称为 namei 且处理时间为 timei 的n个任务按顺序排成一列，CPU通过循环调度法逐一处理这些任务，每个任务最多处理q ms (这个时间称为时间片)。如果q ms 之后任务尚未处理完毕，那么该任务将被移动至队列最末尾，CPU随即开始处理下一个任务。
举个例子，假设q是100，然后有如下任务队列。
A(150) - B(80) - C(200) - D(200)
首先A被处理100 ms，然后带着剩余的50 ms移动至队尾。
B(80) - C(200) - D(200) - A(50)
随后B被处理80 ms，在总计第180 ms时完成处理，从队列中消失。
C(200) - D(200) - A(50)
接下来C被处理100 ms，然后带着剩余的100 ms移动至队尾。
D(200) - A(50) - C(100)
之后同理，一直循环到处理完所有任务。
请编写一个程序，模拟CPU循环调度法。
输入:
输出:
按照任务完成的先后顺序输出各任务名以及结束时间，任务名与对应结束时间用空格隔开，每一对任务名与结束时间占1行。
限制:
-
1 ≤ n ≤ 100000
-
1 ≤ q ≤ 1000
-
1 ≤ timei ≤ 50000
-
1 ≤ namei 的长度 ≤ 10
-
1 ≤ timei 总和 ≤ 1000000
开始你的任务吧，祝你成功！
完整代码
#include <bits/stdc++.h>
using namespace std;
//队列最大容量
#define maxSize 100005
typedef struct MISSION{
char name[100];
int t;
}P;
P Q[maxSize];
int head, tail, n;
//入队列
void enqueue(P X) {
Q[tail] = X;
tail = (tail+1) % maxSize;
}
// 出队列
P dequeue() {
P X = Q[head];
head = (head+1) % maxSize;
return X;
}
// 求最小值
int min(int a, int b) {
return a<b?a:b;
}
int main(int argc, char const *argv[]) {
int elaps = 0, c;
int i, q;
P u;
scanf("%d %d", &n, &q); // 输入任务数量n和时间片q
// 按顺序将所有任务添加至队列中
for(i=1; i<=n; i++) {
scanf("%s", Q[i].name);
scanf("%d", &Q[i].t);
}
head = 1;
tail = n+1;
while(head!=tail) {
u = dequeue();
c = min(q, u.t);
u.t -= c; // 剩余时间
elaps += c; // 累计已经经过的时间
if(u.t>0){
enqueue(u); // 如果处理未结束，则重新添加至队列
}else{
printf("%s %d\n", u.name, elaps);
}
}
return 0;
}
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！