DS博客作业03--栈和队列

爱被打了一巴掌 2021-12-22 03:09 288阅读 0赞

# 1.本周学习总结 ![1476101-20190309202403056-34355844.jpg][] #

> 栈是一种只能在一端进行插入或删除操作的线性表，特点是“后进先出”；而队列只允许在表的一端进行插入操作，在表的另一端进行删除操作，特点是“先进先出”。  
> 这几周学习了栈和队列，相比较之前的链表学习，这章的内容相对于链表的学习较易于理解。平时做作业的时候觉得自己掌握的差不多了，但是通过这次的考试，发现自己在栈和队列这部分掌握的其实还差很多，在一些条件的判断上还需要更加谨慎鸭，还需要加油呀?

# 2.PTA实验作业 ![1476101-20190309202340995-2116737649.jpg][] #

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

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

### 2.1.1 代码截图 ###

![1476101-20190421101355060-668581039.png][]  
![1476101-20190421101423119-364895081.png][]

### 2.1.2 PTA提交列表说明 ###

![1476101-20190421165947330-734675722.png][]

*  1-2 没有注意编译器，学习了C++语法后，总是习惯性的使用C++语法，导致编译错误
 *  3 ![1476101-20190421164153079-1331787394.png][] 疏忽写成 S->Top2==S->MaxSize-1 导致错误
 *  4 ![1476101-20190421164339324-389609134.png][] 和上面类似没有认真思考两者的关系，写成 if(S->Top1==S->Top2) 导致错误

## 2.2 jmu-ds-舞伴问题 ##

> 假设在周末舞会上，男士和女士们分别进入舞厅，各自排成一队。跳舞开始，依次从男队和女队队头各出一人配成舞伴，若两队初始人数不同，则较长那一队未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 你需要用队列操作实现上述算法。

### 2.2.1 代码截图 ###

![1476101-20190421165420667-500715828.png][]  
![1476101-20190421165505724-978680821.png][]

### 2.2.2 PTA提交列表说明。 ###

![1476101-20190421172215393-1410816321.png][]

*  1 开始没有认真阅读主函数，函数中多写了输出剩余人数的部分，导致答案错误
 *  2-3 没有意识到男性和女性名字间有两个空格，就一直不知道哪里格式错误，直到问了同学......

## 2.3 jmu-ds-符号配对 ##

> 假设表达式中允许包含3种括号：圆括号、方括号和大括号。即(,\[,'\{'。编写一个算法判断表达式中的括号是否正确配对， 要求利用栈的结构实现。

### 2.3.1 设计思路 ###

*  首先遍历数组，遇到左符号则存入栈中，遇到右符号则判断栈内的情况，栈空配对失败，若配对成功则出栈左符号；遍历结束，若栈空则配对成功，不空则配对失败。

### 2.3.2 代码截图 ###

![1476101-20190422164907360-588389381.png][]  
![1476101-20190422164932265-1473619635.png][]

### 2.3.3 PTA提交列表说明。 ###

![1476101-20190422165702155-133851775.png][]

*  以为不配对只要输出no就好，然后仔细阅读了输出样例发现了如果栈不为空时还要输出剩下的

## 2.4 jmu-报数游戏 ##

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

### 2.4.1 设计思路 ###

*  设一个变量count模拟数数，然后对m进行求余，当结果等于0时，就出队输出并出队，不等于0就移至最后，直到数字全部输出

### 2.4.2 代码截图 ###

![1476101-20190422162901866-570778182.png][]  
![1476101-20190422162918097-1181412502.png][]

### 2.4.3 PTA提交列表说明。 ###

![1476101-20190422163356330-1607688985.png][]

*  上课时讲过简易版的，所以做这道题时比较顺利，编译器上改了一两个小错误就完成了

# 3.栈和队列上机考试 ![1476101-20190309202432995-718470712.jpg][] #

![1476101-20190422150354312-866576215.png][]

> 平时做作业的时候觉得自己掌握的差不多了，但是通过这次的考试，发现自己在栈和队列这部分掌握的其实还差很多。

## 3.1 另类循环队列 ##

*  错误：  
    ![1476101-20190422151942447-778607399.png][]
 *  正确：  
    ![1476101-20190422153103710-2069628650.png][]

> 可以因为开始在选择题上花了很多时间，然后就有点慌了，也出现许多平时或之前考试没有出现的错误，在做这道题的时候出现了许多错误，比如输出没有换行，忘记 return d; 等等，截图中展示的是因为忽略循环队列的特点，导致缺少一步 Q->Front %= Q->MaxSize ，也因为函数题不好调试，以上种种导致没有拿到这题的分数。

## 3.2 ##

*  错误：  
    ![1476101-20190422153817093-606307400.png][]
 *  正确：  
    ![1476101-20190422153929362-450285640.png][]

> 考试的时候没有把情况考虑完全，忽略了如果A队列为空，首先输出的是B队列的情况，导致多输出了一个空格，导致最后一个测试点没过

转载于:https://www.cnblogs.com/qq1191834402/p/10743933.html

[1476101-20190309202403056-34355844.jpg]: /images/20211220/ce8bde33ff7442268bd01fc390ec4548.png
[1476101-20190309202340995-2116737649.jpg]: /images/20211220/45862600f4e7429fa4c4954de6bd2020.png
[1476101-20190421101355060-668581039.png]: /images/20211220/83888fb5ecc64e24b54f67bfde33b0ca.png
[1476101-20190421101423119-364895081.png]: /images/20211220/462b4ecc2c50478fa6be1ebec192c6ac.png
[1476101-20190421165947330-734675722.png]: /images/20211220/c30d7a974f61447d93809a92e4bfd24b.png
[1476101-20190421164153079-1331787394.png]: /images/20211220/73dc1f4991114dde853f934d703f5498.png
[1476101-20190421164339324-389609134.png]: /images/20211220/5b0b4dc7f5d24ff786ebd35194260f6d.png
[1476101-20190421165420667-500715828.png]: /images/20211220/43874f9cfae2440eb345fabe3a74bb4c.png
[1476101-20190421165505724-978680821.png]: /images/20211220/0843f9ba74804bb4a37e73d2052498e8.png
[1476101-20190421172215393-1410816321.png]: /images/20211220/01b2b82b2a41460bac76072399a75f6d.png
[1476101-20190422164907360-588389381.png]: /images/20211220/a71bef95ee3d4eb692a731003ea64c7e.png
[1476101-20190422164932265-1473619635.png]: /images/20211220/0847dd60eeb14533bd10fada8dc9f4b4.png
[1476101-20190422165702155-133851775.png]: /images/20211220/d223e04dfaee40b3804b91bf05ad9519.png
[1476101-20190422162901866-570778182.png]: /images/20211220/9c96a42458cd435190ee54061d8c41a1.png
[1476101-20190422162918097-1181412502.png]: /images/20211220/f79e39ed411748c3adb2ab106f5ec121.png
[1476101-20190422163356330-1607688985.png]: /images/20211220/981b7f66739e4ec298b4107772d37ecf.png
[1476101-20190309202432995-718470712.jpg]: /images/20211220/1f4fb8f4796e4e8da6473531377f0638.png
[1476101-20190422150354312-866576215.png]: /images/20211220/bb4b7951c9354e83aa7aae0361d54c5d.png
[1476101-20190422151942447-778607399.png]: /images/20211220/e5652a4cbd2d4abd8f1be48924d4a696.png
[1476101-20190422153103710-2069628650.png]: /images/20211220/11a645a4b65340a996e8db90d9ce5564.png
[1476101-20190422153817093-606307400.png]: /images/20211220/71223e41d9b8469e997f809ce9f23ab0.png
[1476101-20190422153929362-450285640.png]: /images/20211220/5676e8b4810645a3b4e4fa9136be0120.png