1.本周学习总结

本周学习了栈和队列两种数据结构，分别对应后进先出，先进先出两种数据操作

学会栈的特殊类型—共享栈，队列的特殊类型—循环队列的一系列操作

学会熟练使用栈和队列的STL容器,使代码简洁

2.PTA实验作业

2.1 在一个数组中实现两个堆栈

本题要求在一个数组中实现两个堆栈

2.1.1 设计思路

函数题省略

2.1.2 代码截图

2.1.3 PTA提交列表及说明

读主函数时没有注意到pop()函数返回值在后继有使用,直接省略了返回值，编译错误

没理解错误原因随便写了个return 0，答案错误

重新读了一遍主函数发现需返回出栈元素

2.2 另类循环队列

如果用一个循环数组表示队列，并且只设队列头指针Front，不设尾指针Rear，而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作

2.2.1 设计思路

函数题省略

2.2.2 代码截图

2.2.3 PTA提交列表及说明

一次过，这题主要考察循环队列没有尾指针的情况下的进栈方法，对以后的复习有帮助

2.3 报数游戏

报数游戏是这样的：有n个人围成一圈，按顺序从1到n编好号。从第一个人开始报数，报到m（m<n）的人退出圈子；下一个人从1开始报数，报到m的人退出圈子。如此下去，直到留下最后一个人。其中n是初始人数；m是游戏规定的退出位次（保证为小于n的正整数）。要求用队列结构完成。输出数字间以空格分隔，但结尾不能有多余空格。

2.3.1 设计思路

定义人数n，数字m

if (m>n) //不合法情况

    输出error!

    返回

if end

for i=1 to n

    1至n循环进队

for end

while(队列不为空)

    i++;

    if (i==m) //报到m,输出,出队

        输出队头

        i=0

    else //队列循环

        temp=队头

        队头出队

        temp进队

    if end

while end

2.3.2 代码截图

2.3.3 PTA提交列表及说明

一次过，在这题学到了使用队列STL实现循环队列，对以后的复习有帮助

2.4 符号配对

请编写程序检查C语言源程序中下列符号是否配对：/与/、(与)、[与]、{与}。

2.4.1 设计思路

while(1) //循环输入

    getline(cin, str); //一行代码读入str

    if str[1]=='.' //跳出循环

        break

    for i=0 to str[i]='\0' //遍历str

        if str[i] 是左符号

            进栈，str[i]=/*是进栈'a'

        else if str[i] 是右符号

            if 栈空

                输出?-右符号

            if 配对

                出栈

            else

                输出 栈顶-?

    for end

while end

if 栈不空

    输出 栈顶-?

else

    输出 yes

2.4.2 代码截图

2.4.3 PTA提交列表及说明

这题由于string不熟偷懒一直放着没去做，直到考试中奖

考试时现学了上一题的getline()函数做字符串输入，由于没注意getline()只能输入一行，各种错误

用循环输入解决了大部分问题，然而还有一个测试点不能通过(真的找不到了)

3.栈和队列上机考试

3.1 表达式求解

输入一个后缀表达式，程序求出表达式值

3.1.1 代码截图

3.1.2 错误分析

负数部分没有考虑进去

3.2 列车调度

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

3.2.1 代码截图

3.2.2 错误分析

这题在考试的时候完全没想出来要怎么用栈或队列的内容解决

看了晓淞同学的博客之后发现了STL中的set可以极快的解决这题，顺手学习了set的相关操作

PS:晓淞博客中没讲清楚的地方(我看代码看得一脸懵逼的地方)

晓淞博客原文

upper_bound()找不到对应值时返回的是end()

end()返回的是最后一个元素的后一个元素（不存在的值）而不是最后一个元素

实际演示：在测试end函数的用法时出现的情况

倒序输出set中的元素，然后输出时发现了个不对的东西

换成vs试了一下，直接崩了

查了一堆博客后终于找到原因

巴特西

DS博客作业03—栈和队列

1.本周学习总结

2.PTA实验作业

2.1 在一个数组中实现两个堆栈

2.1.1 设计思路

2.1.2 代码截图

2.1.3 PTA提交列表及说明

2.2 另类循环队列

2.2.1 设计思路

2.2.2 代码截图

2.2.3 PTA提交列表及说明

2.3 报数游戏

2.3.1 设计思路

2.3.2 代码截图

2.3.3 PTA提交列表及说明

2.4 符号配对

2.4.1 设计思路

2.4.2 代码截图

2.4.3 PTA提交列表及说明

3.栈和队列上机考试

3.1 表达式求解

3.1.1 代码截图

3.1.2 错误分析

3.2 列车调度

3.2.1 代码截图

3.2.2 错误分析

PS:晓淞博客中没讲清楚的地方(我看代码看得一脸懵逼的地方)

实际演示：在测试end函数的用法时出现的情况

最新文章

热门文章