内容简介：作者:数组是万能的，那是不能的；因为他万能的时候名字不叫数组了。这篇文章涉及的源代码可以全部免费获得，在公众号中回复“万能数组”可以获得。
作者: tiankonguse | 更新日期:
数组是万能的，那是不能的；因为他万能的时候名字不叫数组了。
这篇文章涉及的源代码可以全部免费获得，在公众号中回复“万能数组”可以获得。
一、背景
大家好，我是tiankonguse。
由于某些原因，经常有人想学习算法但之前又没有相关经验，不知道从何做起。 我思考了许久，计划写一个系列来分享如何入门学习算法。
之前已经分享了《 认识算法 》、《 了解套路长啥样 》、《 排序算法 》、《 二分查找 》，这是第五篇《万能数组》。
考虑到很多人不是科班出身的，或者当初没好好学习，很多基础知识都忘记了。
还有上次说的交接给我的一个项目，其中的关键逻辑就是使用数组实现的，没想到O(n)复杂度的操作到处都是，真实惨不忍睹。
所以这篇文章来给大家普及下数组上的知识点，大家使用的时候对于复杂度高的操作应该尽量避免，不然后面就是一个瓶颈点。
以后这些问题即使解决了，性能翻了几倍，也没什么好炫耀的，因为这些本来就是基础，最初实现的时候就应该避免。
一、基础知识
C语言中的数组，使用的时候被当做一个定长的连续的空间。
我们可以通过下标在O(1)的时间上直接读取或者修改对应位置的值。
所以数组在很多时候是一种最常见高效的数据结构（姑且算数据结构）。
但是使用数组的时候也会遇到一些问题。
比如数组的空间不管我们有没有使用，长度都是那么多，不知道用了多少。
如果数组满了，想继续加元素，就会数组越界。
如果数组前面想删除，涉及到后面的元素copy到前面，时间复杂度是O(n)。
所以我们希望对数组进行一个封装，名字就叫做万能数组，可以实现任何我们想操作的事情。
为了代码简单点，这里不使用模板，直接以整数为例。
二、自动扩展数组
使用数据时经常会发现空间不够了，所以能够自动扩大空间就好了。
自动扩展的基本思想是追加数据的时候，先判断空间是不是用完了，如果用完了，申请一个更大的内存，旧数据copy过去，旧内存释放，新数据赋值即可。
三、栈
栈是一种很常用的数据结构，特点就是后进先出。
可以想象你们一排车开进死胡同了，最先进去的在最里面，最后进去的在最外面。
那大家想出来，肯定是最外面的先出来，也就是最后进去的先出来（后进先出）。
栈的使用场景有：序列反选、逆序输出、括号匹配、DFS等。
四、队列
队列是一种先进先出的数据结构。
最常见的例子就是排队吃饭，先打饭的肯定是队首的那个人。
由于队列涉及到删除数组前面的元素，这里可以使用一个标记来标记前面删除了多少个元素。
对于内存扩展时，数据从头对齐问题，这里暂时不处理。
五、双向队列
栈大家都听过，队列大家也都听过，那双向队列听过的人就不多了吧。
双向队列，顾名思义，就是两边都可以进也都可以出的队列，也就是栈和队列的合体了。
不过这里会有一个问题，队首也可以插入数据了，有可能前面的空间用完不够用了。
所以，我们到了不得不面对队首空间的问题了，下一小节分享一个比较实用的方法。
六、循环队列
在队列和双向队列小节里，我们发现了两个问题。
问题1：队列的队尾没空间了，队首可能还有空间，我们没办法用起来，只能直接扩大内存。
问题2：双向队列的队首没空间了，队尾可能有空间，我们也没用起来，不但需要扩大内存，还要对数据进行偏移，好给队首预留一些位置来。
我们要做的是，在还有空间时，尽量利用已有的空间。
比如队尾的空间用完了，队首还有，那入队就放在队首那一头。
直到确实没有空间了，我们才去扩展空间。
双向循环队列与循环队列的思想是类似的，这里以循环队列为例来看看实现吧。
七、其他操作
上面对于数组只进行了简单的操作，即首尾增删数据。
实际情况是可能在中间插入数据，也可能删除中间的数据，还需要使用下标定位。
这个时候如果粗暴的实现的话，会发现复杂度是O(n)的。
比如删除数组的第一个元素，那么数组后面所有的元素都需要前移一下（通过循环队列可以不移动）。
而在中间插入或删除一个元素，操作位置后面的空间依旧需要移动，这个时候循环队列就没辙了。
面对这个问题该怎么办呢？
后续的文章慢慢介绍一些方法来。
这篇文章涉及的源代码可以全部免费获得，在公众号中回复“万能数组”可以获得。
本文首发于公众号：天空的代码世界，微信号：tiankonguse-code。
推荐阅读：
今天长按识别上面的二维码，在公众号中回复“ ACM模板 ”，你将免费获得我大学耗时四年整理的《ACM算法模板》。
回复“ 算法的世界 ”，或点击 阅读原文 加入“tiankonguse的朋友们”，已有三百多个小伙伴加入。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 菜鸡的算法修炼：数组（旋转数组的最小数字）
- 算法-计算小数组在大数组中的索引
- 数组查询算法（JavaScript）
- JavaScript数组-排序算法
- 算法面试：数组编码面试问题
- 数据结构与算法: 数组
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
