若是让你手写个栈和队列，你还会写吗？
欢迎添加华为云小助手微信（微信号：HWCloud002 或 HWCloud003），验证经过后，输入关键字“加群”，加入华为云线上技术讨论群；输入关键字“最新活动”，获取华为云最新特惠促销。华为云诸多技术大咖、特惠活动等你来撩！javascript
昨天跟一个CSDN上的朋友聊天，他说如今若是让他本身手写一个栈或者队列，估计都要写蛮久的，平时虽然都在用，可是都是别人封装好的集合。java
确实，经典的数据结构，包括排序算法，虽然咱们平时不用手写了，可是这些内功，做为开发人员来讲是必需要掌握的。受此启发，我打算更一下经典数据结构和算法的系列文章。今天先从栈和队列提及。程序员
这些东西，挤地铁时，吃饭排队时，等公交时，能够拿来看看，或者，就把它看成个下午茶吧~面试
咱们知道，在数组中，若知道数据项的下标，即可当即访问该数据项，或者经过顺序搜索数据项，访问到数组中的各个数据项。可是栈和队列不一样，它们的访问是受限制的，即在特定时刻只有一个数据项能够被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里再也不赘述。算法
栈的主要机制能够用数组来实现，也能够用链表来实现，下面用数组来实现栈的基本操做：数组
数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操做所消耗的时间不依赖于栈中数据项的个数，所以操做时间很短。栈不须要比较和移动操做。微信
队列也能够用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，可是数组前面因为已经删除队列头的数据了，致使空。因此队列咱们能够用循环数组来实现，见下面的代码：数据结构
和栈同样，队列中插入数据项和删除数据项的时间复杂度均为O(1)。数据结构和算法
还有个优先级队列，优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比，主要区别在于队列中的元素是有序的，关键字最小（或者最大）的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现能够用数组或者一种特别的树——堆来实现。.net
这里实现的优先级队列中，插入操做须要 O(N) 的时间，而删除操做则须要 O(1) 的时间。
做者：华为云云享专家倪升武
欢迎添加华为云小助手微信（微信号：HWCloud002 或 HWCloud003），验证经过后，输入关键字“加群”，加入华为云线上技术讨论群；输入关键字“最新活动”，获取华为云最新特惠促销。华为云诸多技术大咖、特惠活动等你来撩！
往期文章精选
javascript基础修炼(13)——记一道有趣的JS脑洞练习题