【数据结构】栈和队列的应用（头歌习题）【合集】

第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

测试输入：
{}{
预期输出：
no

测试输入：
[ , { ( , . ) [,] } , , ]
预期输出：
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

编程要求

现有名称为 name_i 且处理时间为 time_i 的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 ≤ time_i ≤ 50000

• 1 ≤ name_i 的长度 ≤ 10

• 1 ≤ time_i 总和 ≤ 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;
}