20172305 2018-2019-1 《Java软件结构与数据结构》第三周学习总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了20172305 2018-2019-1 《Java软件结构与数据结构》第三周学习总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6433字，纯文字阅读大概需要10分钟。
内容图文
20172305 2018-2019-1 《Java软件结构与数据结构》第三周学习总结
教材学习内容总结
本周内容主要为书第五章内容：
- 队列
- 线性集合(元素从一端加入，另一端删除)
- 先进先出(FIFO)
- 队列前端(front)、队列末端(rear)
- 队列与栈的不同：
- 1.队列(FIFO)是先进先出，栈(LIFO)是后进先出。
- 2.处理方式：在栈中，只在栈的某一端进行；在队列中，可在队列的两端进行。
- 3.栈的作用是颠倒顺序，队列的作用是保持顺序。
- 4.常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。
- 队列与栈的相同：
- 1.
enqueue与push、dequeue与pop、first与peek的操作效果相似。 - 2.不存在直接让用户查看队列或是栈的中部。
- 3.不存在重组或是删除多个元素。
- 4.插入与删除的时间复杂度都是O(1)，在空间复杂度上两者也一样。
- 1.
非环形数组实现的元素移位会产生O(n)的复杂度，环形数组可以避免元素移位的需要。
- Java API中的队列，并没有提供队列类，而是提供一个Queue接口。
- Queue接口提供了两个方法add和offer，往队列中添加元素。add操作可以确保队列中含有给定的元素，如果给定元素没有添加到队列中，该操作将抛出异常；offer操作把给定元素插入到队列中，如果插入成功，返回true，否则返回false。
- Queue接口提供了两个方法poll和remove，从队列中删除元素。当试图从一个空队列中删除一个元素时，发生异常；如果队列为空，poll方法返回null，remove方法抛出一个异常。
用于实现数组集合的数据结构与集合本身的匹配是非常重要的。固定数组实现策略对栈是高效的，是因为所有的活动(添加和删除元素)都是在集合的一端进行的，因而也是数组在数组的一端进行的。而对于队列，是在其两端进行操作的，而顺序也就无关紧要的了。
- 双端队列
- 双端队列是一种具有队列和栈的性质的数据结构。
- 双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
- 双端队列与栈或队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列两种功能。
教材学习中的问题和解决过程
- 问题1:环形数组实现过程中front引用和rear引用的相等问题？与队列的容量问题？如何判断队列已满？
问题1解决方案：整形变量front和整形变量rear是从数组两端开始的索引值，当元素出队列，front的值要递减；当元素入队列，rear的值要递增。但是，在数组的最后一个单元时，该元素被删除后front的值重新回到0；填充该元素后rear的值重新回到0。所以，当该队列为空时均为0；该队列全满时均为最大容量。
- 环形数组与普通数组一样在容量达到最满时需要扩容来添加新的元素
- 一个队列的初始状态，front和rear都指向初始位置（索引为0处）。front永远指向该队列的队头元素，rear则指向该队列最后一个元素的下一位置。
- 当元素入队时在队末进行添加，rear的值逐渐增大，front的值保持不变。
- 当元素出队时在队前进行删除，front的值逐渐增大，rear的值保持不变。
- 判断队满和队空的条件：
(rear + 1) % array.length = front，我们就认为队满;front = rear - rear指向了队尾的后一个位置，也就是新元素将要被插入的位置，如果该位置和front相等了，那么必然说明当前状态已经不能容纳一个元素入队（间接的说明队满）。因为这种情况是和队空的判断条件是一样的，所以我们选择舍弃一个节点位置，rear指向下一个元素的位置，我们使用rear + 1判断下一个元素插入之后，是否还能再加入一个元素，如果不能了说明队列满，不能容纳当前元素入队（其实还剩下一个空位置），rear通过取模，回归到初始位置，我们判断rear + 1是否等于front，如果等于说明队满，不允许入队操作，当然这是牺牲了一个节点位置来实现和判断队空的条件进行区分。
代码学习中的问题和解决过程
- 问题1：enqueue、dequeue、first、isEmpty、size、toString方法的实现
问题1的解决方案：链表实现的队列需要一个头结点，一个尾结点，以及计数的变量。数组实现的队列需要三个整型变量。
- enqueue：向队列末端添加一个元素
- 数组：先判断环形数组是否已满，未满的情况下可以直接插在下一个可用位置，满的条件下可以进行扩容，在插入可用位置即可。与普通数组不同的是，在索引值最大时尾部整型变量必须为零。
rear = (rear + 1) % queue.length通过求余回到0。 - 链表：先判断队列是否为空，如果队列为空头结点也要指向添加元素；如果队列不为空，把原链表末尾的结点指向新元素，新元素的位置作为尾结点。
- dequeue：从队列前端删除一个元素
- 数组：判断环形数组是否为空，如果为空则抛出异常；如果不为空则从索引数最小的开始输出。与enqueue方法类似，在索引值最大的被删除后头部整形变量必须为零。
- 链表：判断环形数组是否为空，如果为空则抛出异常；如果不为空则调出头结点的内容，然后让头结点的下一个作为头结点。
- first:考察队列前端的那个元素
- 数组：直接输出环形数组的头部整形变量索引值的内容。
- 链表：直接输出链表的头结点的内容。
- dequeue与first的区别就是在于队列前端元素的移除和查看。
- isEmpty：判定队列是否为空
- 数组：判断头部整形变量和尾部整形变量是否相等，相等为空。
- 链表：判断栈的元素计数器count变量是否为0，
count = 0为空。
- toString:
- 数组：从头部整形变量开始输出至尾部整形变量。
- 链表：从链表的头部开始往尾部进行不断输出。
- 问题2：PP5.1和PP5.2
- 问题3解决方案：ArrayQueue与LinkedQueue的编写其实很简单，dequeue和enqueue两个比较难的方法书上已经给出，比较麻烦的是ArrayQueue的toString方法，输出的全是删除的内容，本该显示的内容却一个也没显示。错误的把环形数组的头看成是零，忽略了环形数组的头部也是在动的。整形变量front是环形数组的头，应该从数组的front索引值处开始。
- 修改前：
- 修改后：
- 修改前：
- 问题3：PP5.7
- 问题3解决方案：这个编程项目和之前的两个很像，所以在5.1的基础上进行改写的。与队列不同的是两端的都可以添加或是删除，所以我在测试之后发现，当链表内元素仅有一个的时候，尾部的删除没有用。因为我用两个暂时结点进行循环达到链表尾部倒第一和倒第二的内容，但是链表元素仅为一个的时候，一个节点的下一个为空，还有一个结点根本没有实际意义。所以，我添加一个追踪次数的暂时变量，直接越过循环的那种(就是链表元素仅剩一个的时候)，来确定在哪个展示节点后面进行改写。
- 代码如下：
- 代码如下：
代码托管
上周考试错题总结
本周没有错题......
结对与互评
点评(王禹涵)
- 博客中值得学习的或问题：
- 博客中对于链表的内容的解释插入图片进行理解。
- 代码中值得学习的或问题：
- 合作探讨代码问题。
- 基于评分标准，我给本博客打分：7分。
- 得分情况如下：
- 正确使用Markdown语法（加1分）
- 模板中的要素齐全（加1分）
- 教材学习中的问题和解决过程, 一个问题加1分
- 代码调试中的问题和解决过程, 二个问题加2分
- 感想，体会不假大空的加1分
- 点评认真，能指出博客和代码中的问题的加1分
点评(方艺雯)
- 博客中值得学习的或问题：
- 图片运用恰当，很清晰的解释了问题和相关内容，第三章和第四章总结的特别详细
- 基于评分标准，我给本博客打分：8分。
- 得分情况如下：
- 正确使用Markdown语法（加1分）
- 模板中的要素齐全（加1分）
- 教材学习中的问题和解决过程, 二个问题加2分
- 代码调试中的问题和解决过程, 二个问题加2分
- 感想，体会不假大空的加1分
- 点评认真，能指出博客和代码中的问题的加1分
互评对象
本周结对学习情况
20172314方艺雯
20172323王禹涵结对学习内容：链表和数组实现队列
感悟
第五章的内容相对三四章的知识点要少很多，学起来不是很难。所以，中秋节玩的很开心(? ??_??)?!！但是老师说的双向链表和把两个链表合在一起的的相关代码还没有尝试。算是偷懒了...以后抽时间补上吧！
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 0/0 | 1/1 | 15/15 | |
| 第二周 | 703/703 | 1/2 | 20/35 | |
| 第三周 | 762/1465 | 1/3 | 20/55 |
参考资料
内容总结
以上是互联网集市为您收集整理的20172305 2018-2019-1 《Java软件结构与数据结构》第三周学习总结全部内容，希望文章能够帮你解决20172305 2018-2019-1 《Java软件结构与数据结构》第三周学习总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。